今朝流行ってた

fold.md

Haskell:

fold_left f i []      -> i
fold_left f i (x:xs') -> fold_left  f (f i x) xs'

fold_right f []      i = i
fold_right f (x:xs') i -> f x (fold_right f xs' i)

fold_right' f xs i = go id xs
  where
    go g [] = g i
    go g (x:xs') = go (g . (f x)) xs'
    -- go g (x:xs') = go (\i' -> g (f x i')) xs'

OCaml:

let rec fold_left  f i xs = match xs with
  | [] -> i 
  | x::xs' -> fold_left f (f i x) xs';;

let rec fold_right f xs i = match xs with
  | [] -> i
  | x::xs' -> f x (fold_right f xs' i);;

let fold_right' f xs i =
  let rec go g xs' = match xs' with
    | [] -> g i 
    | x::xs'' -> go (fun i' -> g (f x i')) xs'' 
  in go (fun j -> j) xs;;