Haskell - リスト - 畳み込み則(第3双対定理、foldr、融合定理、結合律、単位元、分配律)

関数プログラミング入門
原著

開発環境

• macOS Sierra - Apple (OS)
• Emacs (Text Editor)
• Haskell (プログラミング言語)
• Haskell Platform(ghci)(処理系)

関数プログラミング入門(Richard Bird (著)、山下伸夫 (翻訳)、オーム社)の第4章(リスト)、4.6(畳み込み則)、練習問題4.6.1、4.6.2、4.6.3、4.6.4、4.6.5、4.6.6、4.6.7、4.6.8、4.6.9、4.6.10を取り組んでみる。

練習問題4.6.1、4.6.2、4.6.3、4.6.4、4.6.5、4.6.6、4.6.7、4.6.8、4.6.9、4.6.10

コード(Emacs)

-- 4.6.1
-- foldr f e [] = e
-- foldl (flip f) e (reverse [])
-- = foldl (flip f) e []
-- = e

-- foldr f e (x:xs)
-- = f x (foldr f e xs)
-- = f x (foldl (flip f) e (reverse xs))

-- foldl (flip f) e (reverse (x:xs))
-- = foldl (flip f) e (reverse xs ++ [x])
-- = foldl (flip f) (foldl (flip f) e (reverse xs)) [x]
-- = (flip f) (foldl (flip f) e (reverse xs)) x
-- = f x (foldl (flip f) (e (reverse xs)))

-- foldr f e (x:xs) = foldl (flip f) e (reverse (x:xs))


-- 4.6.2
-- f . foldr g a []
-- = f (foldr g a [])
-- = f a
-- = b

-- foldr h b []
-- = b


-- f . foldr g a (x:xs)
-- = f (foldr g a (x:xs))
-- = f (g x (foldr g a xs))
-- = h x (f (foldr g a xs))
-- = h x (f . foldr g a xs)
-- = h x (foldr h b xs)
-- = foldr h b (x:xs)

-- 4.6.3
-- f (foldl g (g x y) [])
-- = f (g x y)
-- = h (f x) y

-- foldl h (h (f x) y) []
-- = h (f x) y

-- f (foldl g (g x y) (z:zs))
-- = f (foldl g (g (g x y) z) zs)
-- = foldl h (h (f (g x y)) z) zs
-- = foldl h (f (g x y)) (z:zs)

-- 融合定理
-- f . foldl g a []
-- = f (foldl g a [])
-- = f a
-- = b

-- foldl h b []
-- = b

-- f . foldl g a (x:xs)
-- = f (foldl g a (x:xs))
-- = f (foldl g (g a x) xs)
-- = foldl h (h (f a) x) xs
-- = foldl h (h b x) xs
-- = foldl h b (x:xs)

-- 4.6.4
-- foldr f a ([] ++ ys)
-- = foldr f a ys

-- foldr f (foldr f a ys) []
-- = foldr f a ys


-- foldr f a ((x:xs) ++ ys)
-- = foldr f a (x:(xs ++ ys))
-- = f x (foldr f a (xs ++ ys))
-- = f x (foldr f (foldr f a ys) xs)
-- = foldr f (foldr f a ys) (x:xs)


-- foldl f a ([] ++ ys)
-- = foldl f a ys

-- foldl f (foldl f a []) ys
-- = foldl f a ys

-- foldl f a ((x:xs) ++ ys)
-- = foldl f a (x:(xs ++ ys))
-- = foldl f (f a x) (xs ++ ys)
-- = foldl f (foldl f (f a x) xs) ys
-- = foldl f (foldl f a (x:xs)) ys

-- 4.6.5
-- scanl (x) e ys = foldr (\z zs -> e:(map ((x) z) zs)) [e] ys


-- scanl (x) e [] = [e]

-- foldr (\z zs -> e:(map ((x) z) zs)) [e] []
-- = [e]


-- scanl (x) e (y:ys)
-- = e:(scanl (x) ((x) e y) ys)
-- = e:(scanl (x) y ys)
-- = e:(map (foldl (x) y) (inits ys))

-- f = \z zs -> e:(map ((x) z) zs)
-- foldr f [e] (y:ys)
-- = f y (foldr f [e] ys)
-- = f y (scanl (x) e ys)
-- = e:(map ((x) y) (scanl (x) e ys))
-- = e:(map ((x) y) (map (foldl (x) e) (inits ys)))
-- = e:(map ((x) y) . (foldl (x) e) (inits ys))
-- = e:(map (foldl (x) y) (inits ys))

-- 4.6.6
-- foldr1 add . map (mul x) (y:[])
-- = foldr1 add (map (mul x) (y:[]))
-- = foldr1 add [(mul x y)]
-- = mul x y

-- (mul x) . foldr1 add (y:[])
-- = (mul x) (foldr1 add [y])
-- = (mul x) y
-- = mul x y


-- foldr1 add . map (mul x) (y:z:ys)
-- = foldr1 add (map (mul x) (y:z:ys))
-- = foldr1 add ((mul x y):(map (mul x) (z:ys)))
-- = add (mul x y) (foldr1 add (mul x) (z:ys))
-- = add (mul x y) (mul x (foldr1 add (z:ys)))
-- = mul x (add y (foldr1 add (z:ys)))
-- = mul x (foldr1 add (y:z:ys))


main :: IO ()
main = do
  print (scanl (*) 1 [1..10])
  print (foldr (\z zs -> 1:(map (z*) zs)) [1] [1..10])

入出力結果(Terminal, ghci, runghc)

$ runghc sample6.hs
[1,1,2,6,24,120,720,5040,40320,362880,3628800]
[1,1,2,6,24,120,720,5040,40320,362880,3628800]
$