用foldr（右起）声明foldl（左起）

Question

我有折叠：

let rec foldl f lst acc = match lst with
  | [] -> acc
  | hd::tl -> foldl f lst (f hd acc)

我有文件夹：

let rec foldr f lst acc = match lst with 
  | [] -> acc
  | hd::tl -> f hd (foldr f tl acc);;

我想使用foldr声明foldl。

这怎么办？

Answer 1

在伪代码中，

foldl (+) z [a,b,c,d] = ((((z+a)+b)+c)+d)
foldr (*) n [a,b,c,d] = (a*(b*(c*(d*n))))

所以我们需要

foldl (+) z [a,b,c,d] 
 = foldr (*) n [a,b,c,d] z
 = (a*(b*(c*(d*n)))) z
 =    (b*(c*(d*n))) (z+a)
 =       (c*(d*n)) ((z+a)+b)
 =      ...
 =             n ((((z+a)+b)+c)+d)
 =               ((((z+a)+b)+c)+d)

因此一定是

(a*r) z = r (z+a)
n     z = z

即

foldl plus z xs = foldr mult n xs z
  where
  n = { z => z }
  mult a r = { z => r (z+a) }

现在您可以在语法中编写此内容。