This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

calculating a remainder of two church number on lambda calculs with ocaml
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2009-03-21 (19:06) From: Damien Guichard Subject: Re: [Caml-list] calculating a remainder of two church number on lambdacalculs with ocaml
```
Hi fellow ocaml coder,

Church numerals is a unary coding and as such is awfully inefficient.
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
```