Subscribed unsubscribe Subscribe Subscribe

再帰のパターン

Haskell

Fun of Programming (Cornerstones of Computing)の3章「Origami programming」の冒頭にはこんな事が書かれている。

One style of functional programming is based purely on recursive equations. Such equations are easy to explain, and adequate for any computational purpose, but hard tu use well as programs get bigger and more complicated. In a sense, recursive equations are the 'assembly language' of functional programming, and direct recursion the goto.

簡単にまとめると、明示的な再帰を用いるプログラミングスタイルはよろしくないと言うこと。Haskellwikiにもそう書かれている。良い関数型プログラマは再帰を用いず再帰をパターン化した高階関数を使うのだそうだ。

The fun of programmingでは、paramorphismやhylomorphismなど理論的背景がありそうな、小難しい単語がたくさん出てくるが、例題ばかりでよくわからないので、ググってみつけたFunctional Programming with Bananas, Lenses, Envelopes and Barbed Wireという論文(PSファイル)を元にまとめてみる。redditのページにPDFもある。

この論文の2章では再帰のパターンとして、

  • catamorphisms
  • anamorphisms
  • hylomorphisms
  • paramorphisms

の4つが紹介されており、それぞれ数学の表記を用いて説明されているので、項目ごとにHaskellのコードに書き直し、最後にQuickCheckで挙動の正しさを確かめる。

リスト型

はじめに、リストA*を次のように定義する。

A* ::= Nil | Cons (A || A*)
Haskellでは

A*とは[a]のこと。型の表記で使われる||は直積を表しているみたい。

Catamorphisms

catamorphismとはリストから値を得ること。つまりfoldrのこと。リストに対するcatamorphism h ∈ A* → Bは次のように書ける。なお、はてなの仕様で演算子⊕がsuperpre記法中で実体参照に展開されてしまうようなので、関数表記とソースコード中に限り、代わりに<+>を用いる。

h Nil = b
h (Cons (a, as)) = a <+> h as

このような関数hをバナナブラケット(!)で表記する。

h = (|b, <+>|)

これを用いるとリストに対する関数length ∈ A* → Numと、filter p ∈ A* → A*(ただしp ∈ A → bool)は次のように書ける。

length   = (|0, <+>|) where a <+> n = 1 + n
filter p = (|Nil, <+>|)
           where a <+> as = Cons (a, as), p a
                          = as,           ¬p a
Haskellでは

catamorphismはfoldrと同じ。上の定義どおりに書くとこんな感じになる。

-- catamorphism
cata :: b -> (a -> b -> b) -> [a] -> b
cata b f []     = b
cata b f (a:as) = f a (cata b f as)

-- catamorphismを用いたlength
cataLength :: [a] -> Int
cataLength = cata 0 (<+>)
  where a <+> n = 1 + n

-- catamorphismを用いたfilter
cataFilter p = cata [] (<+>)
  where a <+> as
          | p a       = a:as
          | otherwise = as

Anamorphisms

anamorphismはcatamorphismの双対になっている。つまり値からリストを生成する。つまりunfoldr。

リストに対するanamorphism h ∈ B → A*は次の関数になる。ただし、p ∈ B → boolかつg ∈ B → A||Bとする。

h b = Nil,            p b
    = Cons (a, h b'), otherwise
      where (a, b') = g b

これはunfoldrにほぼ等しい。これのhは凹レンズ記号で表される。

h = [(g, p)]

多くの重要なリスト関数がanamorphismになっている。たとえばzip ∈ A*||B* → (A||B)*は次のように書ける。なお、⊕と同じ理由で論理和を表す⋁が化けるので、代わりに\/を用いる。

zip = [(g, p)]
p (as, bs) = (as = Nil) \/ (bs = Nil)
g (Cons (a, as), Cons (b, bs)) = ((a, b), (as, bs))

また、iterate fは次のように書ける。ここでも定数を表す後置単項演算子∙が化けるので、代わりにoを用いる。

iterate f = [(g, false o)] where g a = (a, f a)

また、f ∈ A → Bが与えられたとき、map関数f* ∈ A* → B*は次のように定義できる。

f* Nil            = Nil
f* (Cons (a, as)) = Cons (f a, f* as)

関数の型の両辺にリスト出てくるとき、その関数はcatamorphismとanamorphismで書けるのではないかと疑ってみるといい。今回の場合、どちらでも書ける。

catamorphismの場合、

f* = (|Nil, <+>|)
  where a <+> bs = Cons (f a, bs)

となるし、anamorphismなら

f* = [(g, p)]
  where p as             = (as = Nil)
        g (Cons (a, as)) = (f a, as)

となる。

Haskellでは
-- anamorphism
ana :: (b -> (a, b)) -> (b -> Bool) -> b -> [a]
ana g p b
  | p b       = []
  | otherwise = a:ana g p b'
  where (a, b') = g b

-- anamorphismを用いたzip
anaZip :: [a] -> [b] -> [(a, b)]
anaZip = curry (ana g p)
  where p ([], _) = True
        p (_, []) = True
        p _       = False
        g ((a:as), (b:bs)) = ((a, b), (as, bs))

-- anamorphsimを用いたiterate
anaIterate :: (a -> a) -> a -> [a]
anaIterate f = ana g (const False)
  where g a = (a, f a)

-- 明示的な再帰を用いたmap
map' :: (a -> b) -> [a] -> [b]
map' f []     = []
map' f (a:as) = f a:map' f as

-- catamorphismを用いたmap
cataMap :: (a -> b) -> [a] -> [b]
cataMap f = cata [] (<+>)
  where a <+> bs = (f a):bs

-- anamorphismを用いたmap
anaMap :: (a -> b) -> [a] -> [b]
anaMap f = ana g p
  where p []     = True
        p _      = False
        g (a:as) = (f a, as)

Hylomorphisms

consリストと同型の再帰関数h ∈ A → C、つまり線形再帰*1な関数をhylomorphismという。c ∈ C、<+> ∈ B||C → C、g ∈ A → B||Aかつp ∈ A → boolとすると、hylomorphism hはこう書ける。

h a = c,            p a
    = b <+> (h a'), otherwise
      where (b, a') = g a

これはanamorphismのNilをcに置き換えConsを<+>に置き換えたものと同じになる(つまりanamorphismより一般的)。このhを封筒記号(?)で表記する。

h = [[(c, <+>), (g, p)]]

hylomorphismはanamorhismで線形なデータ型を作り、catamorphismで集約するのと同じ(要するに関数合成で書ける)。つまりこう書き直せる。ここで関数合成を表す∘が化けるので代わりに.を用いる。

[[(c, <+>), (g, p)]] =  (|c, <+>|) . [(g, p)]

典型的なhylomorphismはfactorialである。

fac       = [[(c, ×), (g, p)]]
p n       = n = 0
g (1 + n) = (1 + n, n)
Haskellでは
-- hylomorphism
hylo c f g p a
  | p a       = c
  | otherwise = f b (hylo c f g p a')
  where (b, a') = g a

-- 明示的な再帰を用いたfactorial
fac :: Int -> Int
fac 0       = 1
fac (n + 1) = (n + 1) * fac n

-- hylomorphismを用いたfactorial
hyloFac :: Int -> Int
hyloFac = hylo 1 (*) g p
  where p n       = n == 0
        g (n + 1) = (1 + n, n)

論文の表記に合わせるために、factorialでn + kパターンマッチを使っている。このマッチではn + 1でないとうまく動かない。1 + nとするとコンパイラに怒られる。

Paramorphisms

hylomorphismによるfactorialの定義は、正しいが帰納的な定義でないため(?)、理論的には嬉しくない。問題は、factorialが引数を消費し、かつ次のステップの計算で引数自体を使うことが原因。ちょっとわかりにくい。このパターンはparamorphismと呼ばれる。

numに対するparamorphism hは

h 0       = b
h (1 + n) = n <+> (h n)

となり、リストに対するparamorphism hは

h Nil            = b
h (Cons (a, as)) = a <+> (as, h as)

と書ける。

paramorphismは有刺鉄線記号を使う。

h = <[b, <+>]>

これにより、factorialは

fac = <[1, <+>]>
  where n <+> m = (1 + n) × m

となる。

またtails ∈ A* → A**は次のようになる。

tails = <[Cons (Nil, Nil), <+>]>
  where a <+> (as, tls) = Cons (Cons (a, as), tls)
Haskellでは
-- 数に対するparamorphism
numPara b f 0       = b
numPara b f (n + 1) = f n (numPara b f n)

-- リストに対するparamorphism
listPara b f []     = b
listPara b f (a:as) = f a (as, listPara b f as)

-- paramorphismを用いたfactorial。hylomorphismより遙かに簡単になっている。
paraFac :: Int -> Int
paraFac = numPara 1 f
  where f n m = (1 + n) * m

-- paramorphismを用いたtails
paraTails :: [a] -> [[a]]
paraTails = listPara ([]:[]) f
  where f a (as, tls) = (a:as):tls

QuickCheckで確かめる

これまでHaskellで書いてきたコードについて、QuickCheckでランダムテストしてみる。QuickCheckを用いると、今回のように標準ライブラリに含まれる関数と、自分で定義した関数が同じ挙動をするのかどうかを簡単にテストすることができる。

テストの書き方は簡単。その関数が満たすべき性質(プロパティ)を、ランダム値を生成できる型に指定して並べるだけ。たとえばcataLengthはIntのリストに対して、lengthと同じ値を返すはず。だからlength xs == cataLength xsとなる。

prop_cataLength :: [Int] -> Bool
prop_cataLength xs = length xs == cataLength xs

関数名は、prop_を頭に付けるのが一般的。

同様に他の関数も定義する。

prop_cataFilter :: Int -> [Int] -> Bool
prop_cataFilter x xs = filter p xs == cataFilter p xs
  where p = (== x)
  
prop_anaZip :: [Int] -> [Int] -> Bool
prop_anaZip xs ys = zip xs ys == anaZip xs ys
  
prop_anaIterate :: Int -> Int -> Bool
prop_anaIterate x y = and $ take 100 $ zipWith (==) (iterate (+x) y) (anaIterate (+x) y)
  
prop_map' :: [Int] -> Int -> Bool
prop_map' xs y = and $ take 100 $ zipWith (==) (map (+y) xs) (map' (+y) xs)
  
prop_cataMap :: [Int] -> Int -> Bool
prop_cataMap xs y = and $ take 100 $ zipWith (==) (map (+y) xs) (cataMap (+y) xs) 
  
prop_anaMap :: [Int] -> Int -> Bool
prop_anaMap xs y = and $ take 100 $ zipWith (==) (map (+y) xs)  (anaMap (+y) xs)
  
prop_hyloFac :: NonNegative Int -> Bool
prop_hyloFac x = fac x' == hyloFac x'
  where NonNegative x' = x
  
prop_paraFac :: NonNegative Int -> Bool
prop_paraFac x = fac x' == paraFac x'
  where NonNegative x' = x
  
prop_paraTails :: [Int] -> Bool
prop_paraTails xs = tails xs == paraTails xs

上記テストを一度に走らせるため、バッチ処理を行う。QuickCheckでバッチ処理するには、Conal Elliottが作ったcheckersというライブラリを使うのが便利。

batch :: TestBatch
batch = ( "morphism tests"
        , [ ("catamorphism - length",  property $ prop_cataLength)
          , ("catamorphism - filter",  property $ prop_cataFilter)
          , ("anamorphism  - zip",     property $ prop_anaZip)
          , ("anamorphism  - iterate", property $ prop_anaIterate)
          , ("recursion    - map",     property $ prop_map')
          , ("catamorphism - map",     property $ prop_cataMap)
          , ("anamorphism  - map",     property $ prop_anaMap)
       -- , ("hylomorphism - fac",     property $ prop_hyloFac)
       -- , ("paramorphism - fac",     property $ prop_paraFac)
          , ("paramorphism - tails",   property $ prop_paraTails)
          ]
        )

実行にはquickBatchを用いる。

*Main> quickBatch batch

test:
  catamorphisms - length:  +++ OK, passed 500 tests.
  catamorphisms - filter:  +++ OK, passed 500 tests.
  anamorphisms  - zip:     +++ OK, passed 500 tests.
  anamorphisms  - iterate: +++ OK, passed 500 tests.
  paramorphisms - tails:   +++ OK, passed 500 tests.

ちゃんと動いていることがわかる。

ちなみに、factorialは大きな数を与えるとstack overflowしてしまう。正格な評価にすれば溢れなくなると思うが、問題はテストの書き方。実際にテストを正常に行うには、入力値を小さい値に制限する必要があるが、どうするのがよいのかわからないので、今回はコメントアウトしている。後で調べよう。

ソースコード

ソースコード全体はこちら。

*1:再帰箇所がひとつ