假設折疊中的折疊函數是$f(x,y)$，要折疊$[1,2,3]$，初始值是$0$。
左折疊的精神如下：
$f(f(f(0 , 1) , 2) , 3)$
遞迴呼叫是發生在左邊的參數。
參數求值是從左到右的。因為一定要先遞迴到最深才能取得參數值，所以不能使用在無窮串列上。
右折疊的精神如下：
$f(1 , f(2 , f(3 , 0)))$
遞迴呼叫是發生在右邊的參數。
可以發現不用遞迴到最深就能取得參數，所以可以使用在無窮串列上。
用左折疊實現右折疊的方法就是，讓折疊函數回傳一個函數，折疊的結果是接收一個參數的函數，這樣就可以改變遞迴的位置了。
程式碼如下：
foldr' :: (b -> a -> a) -> a -> [b] -> a
foldr' f a bs = foldl (\g b x -> g (f b x)) id bs a
沒有留言:
張貼留言