F#中的定点组合器

Question

这不起作用:

let rec fix f = f (fix f)

解决方案是添加一个额外的参数:

let rec fix f x = f (fix f) x

有没有办法做到这一点使用lazy和Lazy.force呢？

Answer 1

你的原件fix需要'a -> 'a:

> let rec fix f = f (fix f);;

val fix : ('a -> 'a) -> 'a

如果你需要一个,Lazy<'a> -> 'a那么你可以写这个:

> let rec fix f = lazy f (fix f);;

val fix : (Lazy<'a> -> 'a) -> Lazy<'a>

f如果它不需要它,则允许不评估其参数,因此递归可以在运行时终止.

如果您希望结果为类型,'a则只需强制执行最终结果:

> let rec fix' f = lazy f (fix' f);;

val fix' : (Lazy<'a> -> 'a) -> Lazy<'a>

> let fix f = (fix' f).Value;;

val fix : (Lazy<'a> -> 'a) -> 'a

例如,这里是阶乘函数:

> fix (fun f n -> if n > 1 then n * f.Value (n-1) else 1) 4;;
val it : int = 24