「プログラミング Haskell」 読書メモ 7.3 畳込関数

プログラミング Haskell 7章 高階関数 7.3 畳込関数

reverse を foldr で作る例が面白いので写経。

-- 普通の reverse の定義
reverse :: [a] -> [a]
reverse []     = []
reverse (x:xs) = reverse xs　++ [x]

reverse [1,2,3]

を展開すると

reverse 1:(2:(3:[]))
(reverse (2:(3:[]))) ++ [1]
(reverse (3:[])) ++ [2] ++ [1]
(reverse []) ++ [3] ++ [2] ++ [1]
[] ++ [3] ++ [2] ++ [1]
[3,2,1]

のような動作となる。

cons と逆の関数 snoc を定義すると foldr で reverse 出来る。

snoc :: a -> [a] -> [a]
snoc x xs = xs ++ [x]

ghci> (:) 4 [1,2,3] -- cons
[4,1,2,3]

ghci> snoc 4 [1,2,3]
[1,2,3,4]

snoc の様子をトレース。

import Debug.Trace
snoc x xs = trace ("snoc "++show x++" "++show xs++" = "++ show xs ++" ++ ["++show x++"]")(xs ++ [x])

reverse' []     = trace ("reverse' = []") []
reverse' (x:xs) = trace ("reverse' = snoc "++ show x ++ " (reverse' "++show xs++")") (snoc x (reverse' xs))

ghci> snoc 4 [1,2,3]
snoc 4 [1,2,3] = [1,2,3] ++ [4]
[1,2,3,4]

ghci> reverse' [1,2,3]
reverse' = snoc 1 (reverse' [2,3])
reverse' = snoc 2 (reverse' [3])
reverse' = snoc 3 (reverse' [])
reverse' = []
snoc 3 [] = [] ++ [3]
snoc 2 [3] = [3] ++ [2]
snoc 1 [3,2] = [3,2] ++ [1]
[3,2,1]

ghci> foldr snoc [] [1,2,3]
snoc 3 [] = [] ++ [3]
snoc 2 [3] = [3] ++ [2]
snoc 1 [3,2] = [3,2] ++ [1]
[3,2,1]

snoc は初期値 を受け取り、右からリストの要素をひとつづつ 連結していく。

foldl だと初期値のに左から順に追加されていくので reverse される。

ghci> foldl (\xs x->x:xs) [] [1,2,3]
[3,2,1]

Prelude Debug.Trace> let cons xs x = trace ("cons "++show xs++" "++show x++" = "++ show x ++": "++show xs)(x:xs)
Prelude Debug.Trace> foldl cons [] [1,2,3]
[3,2,1]
cons [] 1 = 1: []
cons [1] 2 = 2: [1]
cons [2,1] 3 = 3: [2,1]