出于学习目的,我模仿了
List.foldBack
。模拟版本是头递归的。
有没有一种优雅的方法将其转换为尾递归版本?
let li : int list = [1;2;3]
let rec foldBack f li initialValue =
match li with
| [] -> initialValue
| x::xs -> f x (foldBack f xs initialValue)
let resultFoldBack =
foldBack (fun x initValue -> x::initValue) li []
resultFoldBack |> printfn "Result for the emulated foldBack: %A"
当然。我们只需先将其翻转一圈,然后再折回即可。在伪代码,
中foldBack f li z0 = g1 li []
where
g1 [a;b;c;...;m] acc = g1 [b;c;...;m] (a::acc)
g1 [] acc = g2 acc z0
g2 [m;l;k;...;a] z0 = g2 [l;k;...;a] (f m z0)
g2 [] res = res
这实际上只是一个接一个的折叠两次,
foldBack f li z0 = fold f (fold g li []) z0
where
g x acc = x::acc
甚至只是立即
fold f (reverse li) z0
。 reverse
不在尾部位置,但这并不重要,因为调用堆栈的深度仅为 2。
有些人可能会建议“继续传递风格”,但这只是构建相同的反向列表,就在匿名函数的链而不是链表节点内:
foldBack f li z0 = g1 li ident
where
ident x = x
g1 [a;b;c;...;m] ret = g1 [b;c;...;m] (acc => ret (f a acc))
g1 [] ret = ret z0
举例来说,对于三元素列表,最终的
ret
应用程序将是
let ret1 := (acc => ret (f a acc)) (* a at the bottom *)
let ret2 := (acc => ret1 (f b acc))
let ret3 := (acc => ret2 (f c acc)) (* c at the top *)
ret3 z0
表达申请
(acc => (acc => (acc => ret (f a acc)) (* a at the bottom *)
(f b acc))
(f c acc)) z0 (* c at the top *)
这将导致计算
let acc := z0
let acc := f c acc
let acc := f b acc
let acc := f a acc
acc
这实际上相当于在第一个版本中使用
g2
展开堆栈,计算
f a (f b (f c z0))
从内到外直接进行。