Paramorphismの練習
Paramorphismは
foldr の強化版ということを捉えるのは大前提その上で、
なぜ
foldr では無理(あるいは複雑になる)で、 para では書けるのか、ということを考えるまた、それはさておき、
para を使って書く時の考え方、というのをメモるまずparaの定義
hspara :: (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 の再実装こんな感じで書ける
hsinsertWithPara :: 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で書けるのでは
hsinsert' :: Ord a => a -> [a] -> [a]
insert' v = foldr f [v]
where
f x (y:ys)
| x <= y = x:y:ys
| otherwise = y:x:ysfoldrにできなくて、paraでのみできることって何だっけ？
そもそもfoldr自体に捉えが甘いのと、
あるいはZygomorphismから取り組んでみる
というのはどうでしょう？
hsdeleteWithPara :: Ord a => a -> [a] -> [a]
deleteWithPara v = para f []
where
f x (xs, ys)
| v == x = xs
| otherwise = x:yshsdelmin :: 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)