プログラミングHaskellのunfoldを３言語で

Haskell Clojure Python

プログラミングhaskell 7章の練習問題にある unfold について。
※Haskell 標準関数 unfoldr の話ではないです。

●まず haskellで

本で提示されてるコード

unfold p h t x | p x = []
               | otherwise = h x : unfold p h t (t x)

わかりにくいので、パラメータの意味に則した名前を付けてみる。

unfold finish nextElem nextSeed seed
    | finish seed = []
    | otherwise = nextElem seed : unfold finish nextElem nextSeed (nextSeed seed)

さらに再帰によって値が変化するパラメータと、固定値を切り分けてみる。

unfold finish nextElem nextSeed seed
    | finish seed = []
    | otherwise = nextElem seed : unfold' (nextSeed seed)
    where unfold' = unfold finish nextElem nextSeed

unfold' は、unfold の評価の過程で常に変ることのない３引数を部分適用で固定した関数。
再帰のたびに更新されるのは seed で次の seed は nextSeed により得られる。
(nextElem seed) が次のリスト要素を生成し、１階層下の unfold' 再帰評価の結果（であるところのリスト）に cons する。再帰は (finish seed) が真になったところで停止。

練習問題の解答 ４関数

int2bin = unfold (==0) (`mod` 2) (`div` 2)
chop8 = unfold null (take 8) (drop 8)
map' f = unfold null (f . head) tail
iterate' f = unfold (\_ -> False) id f

それぞれ、

-- 整数をビットパターンへ分解
int2bin 10 -- => [0,1,0,1]

-- リストを 8 要素ずつに分割
chop8 [1..20] -- => [[1,2,3,4,5,6,7,8],[9,10,11,12,13,14,15,16],[17,18,19,20]]

-- map と iterate の再実装
map' (*2) [1..5]         -- => [2,4,6,8,10]
take 5 (iterate' (*2) 1) -- => [1,2,4,8,16]

●Clojure でも書いてみる

unfold の実装。Haskell と違い cons は遅延評価ではないので、lazy-seq で遅延を明示。

(defn unfold [finish nextElem nextSeed seed]
  (letfn [(unfold- [seed]
                   (if (finish seed)
                     '()
                     (lazy-seq (cons (nextElem seed)
                                     (unfold- (nextSeed seed))))))]
    (unfold- seed)))
Clojure の unfold で関数実装 その１（int2bin, chop8)
(def int2bin (partial unfold zero? #(bit-and % 1) #(bit-shift-right % 1)))
(def chop8 (partial unfold empty? (partial take 8) (partial drop 8)))

bit-and, bit-shift-right は、２による剰余算と除算。
ロジックは Haskell 版と一緒だが、部分適用に partial を明記しなければならない分、煩雑になってしまう。
なお、chop8 は組み込み関数 partition-all を使うことで簡単に作れる。

(def chop8 (partial partition-all 8))
Clojure の unfold で関数実装 その２（my-map-1, my-map-2)
(def my-map-1 (fn [f coll] (unfold empty? (comp f first) rest coll)))
(def my-map-2 (fn [f] (partial unfold empty? (comp f first) rest)))

Haskell と違い関数がデフォルトでカリー化されるわけじゃないので、カリー化されてる版、されてない版で使い分けが必要(?)

(my-map-1 #(* % 2) (range 1 6))    ;=> (2 4 6 8 10)
((my-map-2 #(* % 2)) (range 1 6))  ;=> (2 4 6 8 10)
Clojure の unfold で関数実装 その３（my-iterate-1, my-iterate-2)

これも map の場合と同様。

(def my-iterate-1 (fn [f seed] (unfold (fn [_] false) identity f seed)))
(def my-iterate-2 (fn [f] (partial unfold (fn [_] false) identity f)))

(take 5 (my-iterate-1 (partial * 2) 1))    ;=> (1,2,4,8,16)
(take 5 ((my-iterate-2 (partial * 2)) 1))  ;=> (1,2,4,8,16)

iterate は無限シーケンスを生成するので、unfold 定義が lazy でないと、無限ループに陥って帰って来なくなる。

●Python では ... できなかった

ジェネレータや itertools 使えば作れるだろ、と思ったけどやってみたら一筋縄ではいかなかった。
以下それっぽく作った正格評価版。

from functools import partial

def unfold(finish, nextElem, nextSeed, seed):
    def unfold_ (seed):
        if finish(seed):
            return []
        else:
            return [nextElem(seed)] + unfold_(nextSeed(seed))
    return unfold_(seed)

int2bin = partial(unfold,
                  lambda n:n == 0,
                  lambda n:n & 1,
                  lambda n:n >> 1)

chop8 = partial(unfold,
                lambda xs:not bool(xs),
                lambda xs:xs[:8],
                lambda xs:xs[8:])

my_map = lambda f,xs: unfold(lambda xs: not bool(xs),
                             lambda xs: f(xs[0]),
                             lambda xs: xs[1:],
                             xs)

遅延評価ではないので、 iterate は無理。
unfold は再帰つかってるけど、スタック溢れ対策もしてない。