虽然在F#中使用Tail Recursion,但在什么时候使用？

Question

好的,只是在F#中,这就是我现在理解的方式:

• 有些问题本质上是递归的(构建或读出树结构只能命名一个)然后你使用递归.在这些情况下,您最好使用尾递归来使堆栈中断

• 有些语言是纯粹的功能,所以你必须使用递归而不是while循环,即使问题不是递归的

所以我的问题是:既然F#也支持命令式范式,你会在F#中使用尾递归来解决那些不是自然递归的问题吗？特别是因为我已经读过编译器重新认识尾递归并且只是在while循环中转换它？

如果是这样:为什么？

Answer 1

最好的答案是'既不'.:)

有一些丑陋与while循环和尾递归相关联.

虽然循环需要可变性和效果,虽然我没有反对使用它们,特别是当封装在本地函数的上下文中时,当你开始将效果仅仅引入循环时,你有时会感到混乱/丑化你的程序.

尾递归通常具有需要额外累加器参数或延续传递样式的缺点.这使程序与额外的样板杂乱,以按摩功能的启动条件.

最好的答案是既不使用while循环也不使用递归.高阶函数和lambdas是你的救星,特别是地图和折叠.当你可以将它们封装在可重用的库中然后只是简单地和声明性地陈述你的计算的本质时,为什么要使用凌乱的控制结构来进行循环呢？

如果您养成经常调用map/fold而不是使用循环/递归的习惯,以及提供折叠函数以及您引入的任何新的树结构数据类型,您将走得更远.:)

对于那些有兴趣了解F#折叠的人,为什么不查看关于该主题的系列中的前 三篇 博文？

Answer 2

按照首选项和一般编程风格,我将编写如下代码:

如果可用,则映射/折叠

let x = [1 .. 10] |> List.map ((*) 2)

它只是方便易用.

非尾递归函数

> let rec map f = function
    | x::xs -> f x::map f xs
    | [] -> [];;

val map : ('a -> 'b) -> 'a list -> 'b list

> [1 .. 10] |> map ((*) 2);;
val it : int list = [2; 4; 6; 8; 10; 12; 14; 16; 18; 20]

大多数算法最容易阅读和表达,没有尾递归.当你不需要过度递归时,这种方法特别有效,使其适用于许多排序算法和平衡数据结构上的大多数操作.

记住,log ₂(1,000,000,000,000,000)〜= 50,因此没有尾递归的log(n)操作根本不可怕.

使用累加器进行尾递归

> let rev l =
    let rec loop acc = function
        | [] -> acc
        | x::xs -> loop (x::acc) xs
    loop [] l

let map f l =
    let rec loop acc = function
        | [] -> rev acc
        | x::xs -> loop (f x::acc) xs
    loop [] l;;

val rev : 'a list -> 'a list
val map : ('a -> 'b) -> 'a list -> 'b list

> [1 .. 10] |> map ((*) 2);;
val it : int list = [2; 4; 6; 8; 10; 12; 14; 16; 18; 20]

它很有用,但是代码很笨拙,算法的优雅也略显模糊.上面的例子读起来并不算太糟糕,但是一旦你进入树状数据结构,它真的开始成为一场噩梦.

尾部递归,继续传递

> let rec map cont f = function
    | [] -> cont []
    | x::xs -> map (fun l -> cont <| f x::l) f xs;;

val map : ('a list -> 'b) -> ('c -> 'a) -> 'c list -> 'b

> [1 .. 10] |> map id ((*) 2);;
val it : int list = [2; 4; 6; 8; 10; 12; 14; 16; 18; 20]

每当我看到这样的代码时,我都会对自己说"现在这是一个巧妙的伎俩!".以可读性为代价,它保持了非递归函数的形状,并发现尾部递归插入二叉树非常有趣.

它可能是我的monad-phobia在这里讲的,或者也许我对Lisp的调用/ cc缺乏熟悉,但我认为CSP实际上简化算法的那些场合很少见.评论中欢迎反例.

while循环/ for循环

在我看来,除了序列理解之外,我从来没有在我的F#代码中使用while或for循环.在任何情况下...

> let map f l =
    let l' = ref l
    let acc = ref []
    while not <| List.isEmpty !l' do
        acc := (!l' |> List.hd |> f)::!acc
        l' := !l' |> List.tl
    !acc |> List.rev;;

val map : ('a -> 'b) -> 'a list -> 'b list

> [1 .. 10] |> map ((*) 2);;
val it : int list = [2; 4; 6; 8; 10; 12; 14; 16; 18; 20]

它实际上是对命令式编程的模仿.你可以通过声明来保持一点理智let mutable l' = l,但任何非平凡的功能都需要使用ref.

Answer 3

许多问题都具有递归性质,但长时间强制思考常常会阻止我们看到这一点.

一般来说,我会尽可能在函数式语言中使用函数技术 - 循环从不起作用,因为它们完全依赖于副作用.因此,在处理命令式代码或算法时,使用循环是足够的,但在功能上下文中,它们并不被认为是非常好的.

功能技术不仅意味着递归,还使用适当的高阶函数.

因此,在对列表求和时,既不是for-loop也不是递归函数,而是a fold是具有可理解代码而不重新发明轮子的解决方案.

Answer 4

老实说,你可以用循环解决的任何问题已经是一个自然递归的问题,因为你可以将两者都转化为(通常是有条件的)跳跃.

我相信在几乎所有必须编写显式循环的情况下,你应该坚持使用尾调用.它更加通用:

• while循环将您限制为一个循环体,而尾调用可以允许您在"循环"运行时在多个不同状态之间切换.
• while循环将你限制为一个条件来检查终止,尾递归你可以有一个任意复杂的匹配表达式,等待将控制流分流到其他地方.
• 您的尾调用都返回有用的值,并可能产生有用的类型错误.while循环不会返回任何内容,并依赖于副作用来完成其工作.
• 虽然循环不是第一类,而具有尾调用的函数(或其中的循环)是.可以检查本地范围内的递归绑定的类型.
• 尾递归函数可以很容易地分解为使用尾调用以所需顺序相互调用的部分.这可能会使事情更容易阅读,如果您发现想要在循环中开始,这将有所帮助.这不是一个while循环.

总而言之,F#中的循环只是值得,如果你真的要在函数体内处理可变状态,重复做同样的事情直到满足某个条件.如果循环通常有用或非常复杂,您可能希望将其分解为其他顶级绑定.如果数据类型本身是不可变的(许多.NET值类型都是),那么无论如何都可能从使用对它们的可变引用中获得很少.

我会说你应该只采用while循环来获取适合工作的时间循环,并且相对较短.在许多命令式编程语言中,while循环经常被扭曲成不自然的角色,比如在case语句中反复驱动东西.避免这些事情,看看你是否可以使用尾调用,或者更好的是更高阶函数,以达到同样的目的.