F# FoldBack 转换为尾递归函数

问题描述 投票:0回答:1

出于学习目的,我模仿了

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"
recursion f# tail-recursion fold tail
1个回答
0
投票

当然。我们只需先将其翻转一圈,然后再折回即可。在伪代码

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))

从内到外直接进行。

© www.soinside.com 2019 - 2024. All rights reserved.