subtraction of church numerals in F#

1k Views Asked by At

I am beginner in functional programming and F#. As an exercise im trying to implement church numerals.
First I coded numbers as:

let ZERO = fun p x -> x
let ONE = fun p x -> p x
let TWO = fun p x -> p(p x)
let THREE = fun p x -> p(p(p x))
let FIVE = fun p x ->p(p(p(p(p x))))
... etc

Then i wrote helper function to see if my numbers work:

let toInt p = p (fun x->x+1) 0 

for example:

toInt (THREE) |> printfn "%A" 

prints 3, as expected.
Also I implemented some arithemtic functions:

let INC = fun n f x -> f((n(f))(x)) //incrementation
let DEC = fun n f x -> n (fun g -> fun h -> h(g f))(fun y->x)(fun y-> y) //decrementation      
let ADD = fun m n -> n(INC)(m) //addition
let MUL = fun m n s z -> n(m s) z //multiplication
let POW = fun m n -> n(MUL m)ONE //exponential

All of them seem to work fine:

toInt (INC THREE) |> printfn "%A"  //prints 4
toInt (DEC THREE) |> printfn "%A" //prints 2
toInt (ADD THREE FIVE) |> printfn "%A" //prints 8
toInt (MUL THREE FIVE) |> printfn "%A"  //prints 15
toInt (POW THREE FIVE) |> printfn "%A"  //prints 243

But I am really struggling to implement subtraction:

let SUB = fun m n ->  n(DEC m)
toInt (SUB FIVE THREE) |> printfn "%A" //gives 64

Above method looks like some kind of exponential instead of subtraction.
I also tried (as wiki suggests):

let SUB = fun m n ->  n(DEC)m

but it results in type mismatch when i try to use it:

toInt (SUB FIVE THREE) |> printfn "%A"  

"Type mismatch. Expecting a
    '(((('a -> 'b) -> ('b -> 'c) -> 'c) -> ('d -> 'e) -> ('f -> 'f) -> 'g) -> 'a -> 'e -> 'g) -> (('h -> 'h) -> 'h -> 'h) -> (int -> int) -> int -> 'i'    
but given a
    '(((('a -> 'b) -> ('b -> 'c) -> 'c) -> ('d -> 'e) -> ('f -> 'f) -> 'g) -> (('a -> 'b) -> ('b -> 'c) -> 'c) -> ('d -> 'e) -> ('f -> 'f) -> 'g) -> ((('a -> 'b) -> ('b -> 'c) -> 'c) -> ('d -> 'e) -> ('f -> 'f) -> 'g) -> (('a -> 'b) -> ('b -> 'c) -> 'c) -> ('d -> 'e) -> ('f -> 'f) -> 'g'    
The types ''a' and '('a -> 'b) -> ('b -> 'c) -> 'c' cannot be unified"

I'm stuck, what am I doing wrong? And I would also appreciate any suggestions how to improve my code.

0

There are 0 best solutions below

Related Questions in F#