CODEWITHSUNDEEP
f#
Christoph
Christoph

Reputation: 147

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

Upvotes: 3

Views: 337

Answers (2)

kvb
kvb

Reputation: 55195

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))

Upvotes: 5

desco
desco

Reputation: 16782

This is cheating, but you can use types

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))

Upvotes: 3

Related Questions