reynaldo f. tamayo for openphoto.net

### Origami programming

Gibbons さん曰く:

In this chapter we will look at folds and unfolds as abstractions. In a precise technical sense, folds and unfolds are the natural patterns of computation over recursive datatypes; unfolds generate data structures and folds consume them.

`foldLeft`4日目`Foldable` を使ったときにみたけど、unfold って何だろう?

The dual of folding is unfolding. The Haskell standard List library deﬁnes the function `unfoldr` for generating lists.

Hoogle には以下の例がある:

``````Prelude Data.List> unfoldr (\b -> if b == 0 then Nothing else Just (b, b-1)) 10
[10,9,8,7,6,5,4,3,2,1]
``````

### DList

`DList` というデータ構造があって、それは `DList.unfoldr` をサポートする。`DList` もしくは差分リスト (difference list) は定数時間での追加をサポートするデータ構造だ。

``````scala> DList.unfoldr(10, { (x: Int) => if (x == 0) none else (x, x - 1).some })
res50: scalaz.DList[Int] = scalaz.DListFunctions\$\$anon\$3@70627153

scala> res50.toList
res51: List[Int] = List(10, 9, 8, 7, 6, 5, 4, 3, 2, 1)
``````

### Stream の畳込み

Scalaz では `StreamFunctions` で定義されている `unfold``import Scalaz._` で導入される:

``````scala> unfold(10) { (x) => if (x == 0) none else (x, x - 1).some }
res36: Stream[Int] = Stream(10, ?)

scala> res36.toList
res37: List[Int] = List(10, 9, 8, 7, 6, 5, 4, 3, 2, 1)
``````

``````scala> def minimumS[A: Order](stream: Stream[A]) = stream match {
case x #:: xs => xs.foldLeft(x) {_ min _}
}
minimumS: [A](stream: Stream[A])(implicit evidence\$1: scalaz.Order[A])A

scala> def deleteS[A: Equal](y: A, stream: Stream[A]): Stream[A] = (y, stream) match {
case (_, Stream()) => Stream()
case (y, x #:: xs) =>
if (y === x) xs
else x #:: deleteS(y, xs)
}
deleteS: [A](y: A, stream: Stream[A])(implicit evidence\$1: scalaz.Equal[A])Stream[A]

scala> def delmin[A: Order](stream: Stream[A]): Option[(A, Stream[A])] = stream match {
case Stream() => none
case xs =>
val y = minimumS(xs)
(y, deleteS(y, xs)).some
}
delmin: [A](stream: Stream[A])(implicit evidence\$1: scalaz.Order[A])Option[(A, Stream[A])]

scala> def ssort[A: Order](stream: Stream[A]): Stream[A] = unfold(stream){delmin[A]}
ssort: [A](stream: Stream[A])(implicit evidence\$1: scalaz.Order[A])Stream[A]

scala> ssort(Stream(1, 3, 4, 2)).toList
res55: List[Int] = List(1, 2, 3, 4)
``````

これは `foldLeft``unfold` を使っているからおりがみ (origami) プログラミングということなんだろうか? これは The Fun of Programming (邦訳は関数プログラミングの楽しみ) の 1章として 2003年に書かれたけど、おりがみプログラミングがその後流行ったかどうかは僕は知らない。