real world haskell에 나온 예
myFoldl :: (a -> b -> a) -> a -> [b] -> a
myFoldl f z xs = foldr step id xs z
where step x g a = g (f a x)
책에 자세한 설명이 안 나와서 종이에 끄적여본 다음에 한 이해
위는 아래와 같이 다시 쓸 수 있음
myFoldl :: (a -> b -> a) -> a -> [b] -> a
myFoldl f z xs = foldr step id xs z
where step x g = g . flip f x
예를 이용해 이해해보면
xs = [0, 1, 2, 3]이라 치면
foldr step id [0, 1, 2, 3] z
foldr을 한단계만 전개하면
= foldr step (step 3 id) [0, 1, 2] z
= foldr step (id . flip f 3) [0, 1, 2] z
= foldr step (flip f 3) [0, 1, 2] z
foldr을 한단계 더 전개하면
= foldr step (step 2 (flip f 3)) [0, 1] z
= foldr step (flip f 3 . flip f 2) [0, 1] z
같은 식으로 계속 전개하면
= foldr step (flip f 3 . flip f 2 . flip f 1 . flip f 0) [] z
foldr 전개가 끝났으므로 다음과 같아짐
= (flip f 3 . flip f 2 . flip f 1 . flip f 0) z
= (flip f 3 . flip f 2 . flip f 1) (flip f 0 z)
= (flip f 3 . flip f 2 . flip f 1) (f z 0)
= (flip f 3 . flip f 2) (f (f z 0) 1)
= (flip f 3) (f (f (f z 0) 1) 2)
= f (f (f (f z 0) 1) 2) 3
결국 foldl 방식으로 환원됨
foldl과 foldr은 인자로 들어가는 순서가 반대이므로 flip이 들어가며
foldr에서 먼저 구해진 함수를 앞으로 빼서 차례로 합성해야 foldl처럼 된다는 식으로 대략 이해하면 됨
댓글 0