Paramorphismの練習
『関数プログラミングの楽しみ』.iconの3章の練習問題でParamorphismを使った書き直しがいくつか出てくるのでやってみてるが、割と難しい その上で、
なぜfoldrでは無理(あるいは複雑になる)で、paraでは書けるのか、ということを考える
また、それはさておき、paraを使って書く時の考え方、というのをメモる
まずparaの定義
code:hs
para :: (a -> (a, b) -> b) -> b -> a -> b para f z [] = z
para f z (x : xs) = f x (xs, para f z xs)
Data.List.insertの再実装
こんな感じで書ける
code:hs
insertWithPara :: Ord a => a -> a -> a insertWithPara v = para f []
where
f x (xs, ys)
| v <= x = v:x:xs
| otherwise = x:ys
このfがどういう関数なのか、というのを捉えるのがまず難しい
まずparaはfoldrの強化版であることをまず抑える
foldlではなくfoldrである
f x (xs, ys)の理解
ys
accumratorとなるリスト
fが呼ばれた時点でysは処理済になっている
x
currentとなる要素
xs
para特有のもの
x:xsとすることで、fが呼ばれた時点でのリストを再生できる
まだちゃんと捉えきれてない
あと、そもそもpara使わなくても以下のようにfoldrで書けるのでは
code:hs
insert' :: Ord a => a -> a -> a where
f x (y:ys)
| x <= y = x:y:ys
| otherwise = y:x:ys
foldrにできなくて、paraでのみできることって何だっけ？
そもそもfoldr自体に捉えが甘いのと、
というのはどうでしょう？
code:hs
deleteWithPara :: Ord a => a -> a -> a deleteWithPara v = para f []
where
f x (xs, ys)
| v == x = xs
| otherwise = x:ys
code:hs
delmin :: Ord a => a -> Maybe (a, a) delmin = para f Nothing
where
f x (xs, Nothing)
| null xs = Just (x, [])
| otherwise = Just (x, xs)
f x (xs, Just (min, ys))
| x <= min = Just (x, xs)
| otherwise = Just (min, x : ys)