The map function transforms each head and recursively processes the tail. A right fold combines a head with the result for its tail, whereas a left fold passes an updated accumulator into the recursive call. In Haskell:
import Prelude hiding (map, foldr, foldl, concat)
map f [] = []
map f (x:xs) = f x : map f xs
foldr op e [] = e
foldr op e (x:xs) = op x (foldr op e xs)
foldl op e [] = e
foldl op e (x:xs) = foldl op (op e x) xs
concat = foldr (++) []The last right fold uses list concatenation to replace each outer cons by appending its inner list. Thus
concat [xs,ys,zs] = xs ++ (ys ++ (zs ++ [])). Its right fold association matters: appending a list traverses its left spine, so these equations traverse each inner spine once on finite inputs. The concise answer is Articles by others on the same topic
There are currently no matching articles.