Hi fellow ocaml coder,
Church numerals is a unary coding and as such is awfully inefficient.
Multiplication typically uses repeated addition.
Division/remainder also typically uses repeated substraction.
Because of the crappy unary coding there is little you can do to improve on
that.
My advice is you could gain much better efficiency via a binary coding.
Here is how you can do the easy part :
type nat =
| Null (* 0 *)
| Unit (* 1 *)
| Zero of nat (* 0... *)
| One of nat (* 1... *)
let rec even = function
| Null -> true
| Unit -> false
| Zero n | One n -> even n
let rec double = function
| Null -> Zero Null
| Unit -> One Null
| Zero n -> Zero (double n)
| One n -> One (double n)
let succ n =
let rec loop = function
| Null -> Unit,false
| Unit -> Null,true
| Zero n -> let m,c = loop n in (if c then One m else Zero m),false
| One n -> let m,c = loop n in (if c then Zero m else One m),c
in
let m,c = loop n in if c then One m else m
let mult a b =
let rec loop = function
| Null -> Null,double b
| Unit -> b,double b
| Zero n -> let d,c = loop n in d,double c
| One n -> let d,c = loop n in add d c,double c
in let n,_ = loop a in n
That is dirty untested code yet i hope you get the idea.
Addition/substraction and division will be somewhat trickier however.
- damien
Damien Guichard
2009-03-21
En réponse au message
de : Su Zhang
du : 2009-03-21 18:36:11
À : caml-list@yquem.inria.fr
CC :
Sujet : [Caml-list] calculating a remainder of two church number on
lambdacalculs with ocaml
Hi OCaml hackers,
I have a question about how can I write a function which can get the remainder
of two church numberials in lambda calculus. I know this is a ocaml maillist,
but this lambda calculus should use ocaml engine, so is there anybody know how
can I write this function?
Thanks!
--
Su Zhang
PHD Student
Computer Information and Science
Kansas State University
_______________________________________________
Caml-list mailing list. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
Archives: http://caml.inria.fr
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs
