17

好的，仅在 F# 中，这就是我现在的理解：

  • 有些问题本质上是递归的（构建或读出树结构仅举一个例子），然后您使用递归。在这些情况下，您最好使用尾递归来中断堆栈

  • 有些语言是纯函数式的，所以你必须使用递归而不是 while 循环，即使问题本质上不是递归的

所以我的问题是：既然 F# 也支持命令式范式，你会在 F# 中使用尾递归来解决那些不是自然递归的问题吗？特别是因为我已经阅读了编译器 recongnizes tail recursion 并且只是在 while 循环中转换它？

如果是这样：为什么？

4

5 回答 5

32

最好的答案是“都不是”。:)

while 循环和尾递归都有一些丑陋。

虽然循环需要可变性和效果，尽管我并不反对适度使用它们，尤其是在封装在本地函数的上下文中时，但当您开始引入效果时，您有时会觉得自己在混乱/丑化您的程序只是为了循环.

尾递归通常具有需要额外的累加器参数或继续传递样式的缺点。这会使程序杂乱无章，带有额外的样板来按摩函数的启动条件。

最好的答案是既不使用 while 循环也不使用递归。高阶函数和 lambda 是你的救星，尤其是映射和折叠。当您可以将这些控制结构封装在可重用的库中，然后简单地声明您的计算的本质时，为什么还要使用凌乱的循环控制结构呢？

如果您习惯于经常调用 map/fold 而不是使用循环/递归，并且提供 fold 函数以及您引入的任何新的树形结构数据类型，那么您将走得更远。:)

对于那些有兴趣了解 F# 中折叠的更多信息的人，为什么不查看我在该主题系列中的前 三篇 博客文章？

于 2009-11-25T14:35:37.213 回答
21

按照偏好和一般编程风格，我将编写如下代码：

地图/折叠（如果可用）

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 2 (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 的 call/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.

于 2009-11-25T16:02:25.167 回答
6

老实说，任何可以用循环解决的问题已经是一个自然递归的问题，因为你可以最终将两者都转换为（通常是有条件的）跳转。

我相信在几乎所有必须编写显式循环的情况下，您都应该坚持使用尾调用。它只是更通用：

  • while 循环将您限制在一个循环体中，而尾调用可以让您在“循环”运行时在许多不同的状态之间切换。
  • while 循环将您限制为一个条件来检查终止，通过尾递归，您可以有一个任意复杂的匹配表达式等待将控制流分流到其他地方。
  • 您的尾部调用都返回有用的值，并可能产生有用的类型错误。while 循环不返回任何内容，而是依靠副作用来完成其工作。
  • While 循环不是一流的，而带有尾调用（或其中的 while 循环）的函数是。可以检查本地范围内的递归绑定的类型。
  • 尾递归函数可以很容易地分解为使用尾调用以所需顺序相互调用的部分。这可能会使事情更容易阅读，并且如果您发现要从循环中间开始，这将有所帮助。对于 while 循环，情况并非如此。

总而言之，F# 中的 while 循环只有在您真的要在函数体内使用可变状态、重复执行相同操作直到满足某个条件时才值得。如果循环通常有用或非常复杂，您可能希望将其分解到其他一些顶级绑定中。如果数据类型本身是不可变的（很多 .NET 值类型是），那么无论如何使用对它们的可变引用可能收获甚微。

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

于 2011-03-31T09:59:36.587 回答
5

许多问题具有递归的性质，但是长时间的强制思考常常使我们看不到这一点。

一般来说，我会尽可能在函数式语言中使用函数式技术——循环永远不会起作用，因为它们完全依赖于副作用。因此，在处理命令式代码或算法时，使用循环就足够了，但在函数式上下文中，它们被认为不是很好。

函数式技术不仅意味着递归，还意味着使用适当的高阶函数。

因此，在对列表求和时，既不是 for 循环也不是递归函数，而是 afold是无需重新发明轮子就能获得可理解代码的解决方案。

于 2009-11-25T14:42:12.843 回答
2

对于不是自然递归的问题..无论如何都只是在while循环中转换它

你自己回答了这个。对递归问题使用递归，对本质上不起作用的事物使用循环。只是总是想：哪个感觉更自然，哪个更具可读性。

于 2009-11-25T14:34:57.083 回答