2017年7月27日 星期四

Haskell中用foldl實現foldr

假設折疊中的折疊函數是`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


沒有留言: