F#尾递归函数示例
我是F#的新手,并且正在阅读关于尾递归函数的内容,并希望有人能够给我两个不同的函数foo实现 - 一个是尾递归函数,另一个不是我能更好地理解这个原理。
从一个简单的任务开始,比如将项目从'a'映射到列表中。 我们想写一个有签名的函数
val map: ('a -> 'b) -> 'a list -> 'b list
哪里
map (fun x -> x * 2) [1;2;3;4;5] == [2;4;6;8;10]
从非尾递归版本开始:
let rec map f = function
| [] -> []
| x::xs -> f x::map f xs
这不是尾递归,因为函数在递归调用后仍然有工作要做。 ::
是List.Cons(fx, map f xs)
语法糖List.Cons(fx, map f xs)
。
如果我将最后一行重新写为| x::xs -> let temp = map f xs; fx::temp
该函数的非递归性质可能会更加明显 | x::xs -> let temp = map f xs; fx::temp
| x::xs -> let temp = map f xs; fx::temp
- 显然是在递归调用之后做的工作。
使用累加器变量使其尾递归:
let map f l =
let rec loop acc = function
| [] -> List.rev acc
| x::xs -> loop (f x::acc) xs
loop [] l
这是我们在变量acc
建立一个新列表。 由于列表反向构建,我们需要在将输出列表返回给用户之前将其反转。
如果你有一点思维扭曲,你可以使用延续传递来更简洁地编写代码:
let map f l =
let rec loop cont = function
| [] -> cont []
| x::xs -> loop ( fun acc -> cont (f x::acc) ) xs
loop id l
由于调用loop
和cont
是最后一个没有额外工作的函数,所以它们是尾递归的。
这是有效的,因为continuation cont
是由一个新的continuation捕获的,而这个continuation又被另一个捕获,产生了一种如下的树状数据结构:
(fun acc -> (f 1)::acc)
((fun acc -> (f 2)::acc)
((fun acc -> (f 3)::acc)
((fun acc -> (f 4)::acc)
((fun acc -> (f 5)::acc)
(id [])))))
它按顺序构建一个列表,而不需要您将其撤消。
对于它的价值,开始以非尾递归方式编写函数,它们更易于阅读和使用。
如果你有一个大的列表需要通过,使用累加器变量。
如果您无法以方便的方式找到使用蓄能器的方法,并且您没有任何其他选项可供您使用,请使用继续。 我个人认为,重要的是使用难以阅读的延续。
试图比其他例子更简短的解释:
let rec foo n =
match n with
| 0 -> 0
| _ -> 2 + foo (n-1)
let rec bar acc n =
match n with
| 0 -> acc
| _ -> bar (acc+2) (n-1)
foo不是尾递归,因为foo必须递归地调用foo来评估“2 + foo(n-1)”并返回它。
bar是尾递归的,因为bar不必使用递归调用的返回值来返回一个值。 它可以让递归调用的bar立即返回它的值(不需要通过调用堆栈返回)。 编译器通过将递归重写为循环来看到这个和'欺骗'。
将bar中的最后一行更改为“| _ - > 2+(bar(acc + 2)(n-1))”将会破坏尾端递归。
下面是一个更明显的例子,将它与您通常为阶乘做比较。
let factorial n =
let rec fact n acc =
match n with
| 0 -> acc
| _ -> fact (n-1) (acc*n)
fact n 1
这个有点复杂,但是你的想法是你有一个累加器来保持运行计数,而不是修改返回值。
另外,这种包装方式通常是一个好主意,这样你的调用者就不必担心为累加器播种了(注意事实上这个函数是局部的)
链接地址: http://www.djcxy.com/p/2279.html