F# Create Factorial function without recursion, library functions or loops

In this video about functional programming at 35:14 Jim Weirich writes a function to compute factorial without using recursion, library functions or loops: see image of Ruby code here

The code in Ruby

fx = ->(improver) {
  improver.(improver)
}.(
   ->(improver) {
     ->(n) { n.zero ? 1 : n * improver.(improver).(n-1) }
   }
   )

I'm trying to express this approach F#

let fx =
    (fun improver -> improver(improver))(
    fun improver ->
             fun n ->
             if n = 0 then 1
             else n * improver(improver(n - 1)))

I'm currently stuck at

Type mismatch. Expecting a 'a but given a 'a -> 'b
The resulting type would be infinite when unifying ''a' and ''a -> 'b'

I can't seem find the right type annotation or other way of expressing the function

Edit:

*without the rec keyword


Languages with ML-style type inference won't be able to infer a type for the term fun improver -> improver improver ; they start by assuming the type 'a -> 'b for a lambda-definition (for some undetermined types 'a and 'b ), so as the argument improver has type 'a , but then it's applied to itself to give the result (of type 'b ), so improver must simultaneously have type 'a -> 'b . But in the F# type system there's no way to unify these types (and in the simply-typed lambda calculus there's no way to give this term a type at all). My answer to the question that you linked to in your comment covers some workarounds. @desco has given one of those already. Another is:

let fx = (fun (improver:obj->_) -> improver improver)
         (fun improver n -> 
              if n = 0 then 1 
              else n * (improver :?> _) improver (n-1))

这是作弊,但你可以使用类型

type Self<'T> = delegate of Self<'T> -> 'T
let fx1 = (fun (x: Self<_>) -> x.Invoke(x))(Self(fun x -> fun n -> if n = 0 then 1 else x.Invoke(x)(n - 1) * n))

type Rec<'T> = Rec of (Rec<'T> -> 'T)
let fx2 = (fun (Rec(f ) as r) -> f r)(Rec(fun ((Rec f) as r) -> fun n -> if n = 0 then 1 else f(r)(n - 1) * n))
链接地址: http://www.djcxy.com/p/80550.html

上一篇: F#vs OCaml:堆栈溢出

下一篇: F#创建没有递归,库函数或循环的因子函数