fold/unfoldの練習

fold/unfoldに慣れる

Haskellで書く

Foldableなら何でもいいが、ここでは特殊化してListを用いることにする

以下の3つの関数の内のいずれかを使う

foldr

code:hs

foldr f e [] = e

foldr f e (x : xs) = f x (foldr f e xs)

foldl

code:hs

foldl f e [] = e

foldl f e (x:xs) = foldl f (f e x) xs

unfoldr

code:hs

unfoldr f x = case f x of

Nothing -> []

Just (z,x') -> z : unfoldr f x'

考え方としては、

であるので、再実装したいモノの引数と返り値の型を確認してから、どれを使うのが良いかなというのを考えると良い

とも言えるので、それも考慮に入れると良いかもしれない

使用例は

code:hs

使用例は、

code:hs

ヒント

repeatとどこが違うかを考えてみる

見た目的には、repeatの解答とめちゃくちゃ似ている

sumの再実装をしよう

foldを使わない場合の定義

code:hs

sum' [] = 0

sum' (x : xs) = x + sum' xs

productの再実装をしよう

foldを使わない場合の定義

code:hs

product' [] = 1

product' (x : xs) = x * product' xs

mapの再実装をしよう

foldを使わない場合の定義

code:hs

map' f [] = []

map' f (x:xs) = f x: map' f xs

foldでもunfoldでも定義できるので両方やってみよう

ヒント

foldrを使う

こういうのを見ながらやるとイメージしやすい

code:hs

1 : (2 : (3 : []))) -- 通常のリスト

filterの再実装をしよう

foldを使わない場合の定義

code:hs

filter' _ [] = []

filter' p (x:xs) = if p x then x : filter p xs else filter p xs

ヒント

foldl, foldrのどちらを使ってもほぼほぼ同じだが、どちらかのほうがややきれいになる

foldを使わない場合の定義

code:hs

append' [] ys = ys

append' (x:xs) ys = x: append' xs ys

concatの再実装をしよう

foldを使わない場合の定義

code:hs

concat' [] = []

concat' (x:xs) = x ++ concat' xs

回答例

repeatの再実装

値からリストを作っているのでunfoldrを使う

code:hs

repeat' = unfoldr $ \x -> Just (x, x)

iterateの再実装

値からリストを作っているのでunfoldrを使う

code:hs

iterate' f = unfoldr $ \x -> Just (x, f x)

sumの再実装

code:hs

sum' = foldr (+) 0

productの再実装

code:hs

product' = foldr (*) 1

mapの再実装

foldrを使った場合

code:hs

map' f = foldr ((:) . f) []

もう少し親切に書いたもの

code:hs

map' f xs = foldr' (\x acc -> (f x) : acc) [] xs

逆にわかりにくいか？

unfoldrを使った場合

code:hs

map f = unfoldr $ \case

[] -> Nothing

x:xs -> Just (f x, xs)

filterの再実装

code:hs

filter' p = foldr (\x acc -> if p x then x:acc else acc) []

foldlを使った場合

code:hs

appendの再実装

code:hs

append' = flip $ foldr (:)

もう少し親切に書いたもの

code:hs

append' xs ys = foldr (:) ys xs

concatの再実装

code:hs

concat' = foldr (++) []