Church numerals: Difference between revisions
Content added Content deleted
m (→{{header|F Sharp|F#}}: fix heading, as suggested on the Count examples/Full list/Tier 4 talk page) |
GordonBGood (talk | contribs) (→{{header|OCaml}}: add extended Church functions...) |
||
Line 1,958: | Line 1,958: | ||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
||
Original version by '''[http://rosettacode.org/wiki/User:Vanyamil User:Vanyamil]''' |
Original version by '''[http://rosettacode.org/wiki/User:Vanyamil User:Vanyamil]'''. |
||
<lang OCaml> |
|||
(* Church Numerals task for OCaml |
|||
The extended Church functions as per the "RankNTypes" Haskell version have been added... |
|||
Church Numerals are numbers represented as functions. |
|||
⚫ | |||
A numeral corresponding to a number n is a function that receives 2 arguments |
|||
⚫ | |||
- A function f |
|||
- An input x of some type |
|||
and outputs the function f applied n times to x: f(f(...(f(x)))) |
|||
*) |
*) |
||
⚫ | |||
(* Zero means apply f 0 times to x, aka return x *) |
|||
⚫ | |||
let ch_zero : church_num = { f = fun _ -> fun x -> x } |
|||
⚫ | |||
⚫ | |||
⚫ | |||
(* |
(* One simplifies to just returning the function *) |
||
let |
let ch_one : church_num = { f = fun fn -> fn } |
||
⚫ | |||
in {f} |
|||
(* The next numeral of a church numeral would apply f one more time *) |
(* The next numeral of a church numeral would apply f one more time *) |
||
let ch_succ ( |
let ch_succ (c : church_num) : church_num = { f = fun fn x -> fn (c.f fn x) } |
||
let f = fun f x -> f (n.f f x) |
|||
in {f} |
|||
(* This is just a different way to represent natural numbers - so we can still add/mul/exp them *) |
|||
(* Adding m and n is applying f m times and then also n times *) |
(* Adding m and n is applying f m times and then also n times *) |
||
let ch_add (m : church_num) (n : church_num) : church_num = |
let ch_add (m : church_num) (n : church_num) : church_num = |
||
{ f = fun fn x -> n.f fn (m.f fn x) } |
|||
in {f} |
|||
(* Multiplying is repeated addition : add n, m times *) |
(* Multiplying is repeated addition : add n, m times *) |
||
let ch_mul (m : church_num) (n : church_num) : church_num = |
let ch_mul (m : church_num) (n : church_num) : church_num = |
||
{ f = fun fn x -> m.f (n.f fn) x } |
|||
in {f} |
|||
(* Exp is repeated multiplication : multiply by base, exp times. |
(* Exp is repeated multiplication : multiply by base, exp times. |
||
However, Church numeral n is in some sense the n'th power of a function f applied to x |
However, Church numeral n is in some sense the n'th power of a function f applied to x |
||
So exp base = apply function base to the exp'th power = base^exp. |
So exp base = apply function base to the exp'th power = base^exp. |
||
⚫ | |||
Some shenanigans to typecheck though. |
|||
⚫ | |||
*) |
|||
⚫ | |||
⚫ | |||
let custom_f f x = (exp.f base.f) f x |
|||
(* extended Church functions: *) |
|||
in {f = custom_f} |
|||
(* test function for church zero *) |
|||
let ch_is_zero (c : church_num) : church_num = |
|||
{ f = fun fn x -> c.f (fun _ -> fun _ -> fun xi -> xi) (* when argument is not ch_zero *) |
|||
(fun fi -> fi) (* when argument is ch_zero *) fn x } |
|||
(* church predecessor function; reduces function calls by one unless already church zero *) |
|||
let ch_pred (c : church_num) : church_num = |
|||
{ f = fun fn x -> c.f (fun g h -> h (g fn)) (fun _ -> x) (fun xi -> xi) } |
|||
(* church subtraction function; calls predecessor function second argument times on first *) |
|||
let ch_sub (m : church_num) (n : church_num) : church_num = n.f ch_pred m |
|||
(* church division function; counts number of times divisor can be recursively |
|||
subtracted from dividend *) |
|||
let ch_div (dvdnd : church_num) (dvsr : church_num) : church_num = |
|||
let rec divr n = (fun v -> v.f (fun _ -> (ch_succ (divr v))) |
|||
ch_zero) (ch_sub n dvsr) |
|||
in divr (ch_succ dvdnd) |
|||
(* conversion functions: *) |
|||
(* Convert a number to a church_num via recursion *) |
(* Convert a number to a church_num via recursion *) |
||
Line 2,015: | Line 2,023: | ||
then acc |
then acc |
||
else helper (n-1) (ch_succ acc) |
else helper (n-1) (ch_succ acc) |
||
in |
in helper n ch_zero |
||
helper n ch_zero |
|||
(* Convert a church_num to an int is rather easy! Just +1 n times. *) |
(* Convert a church_num to an int is rather easy! Just +1 n times. *) |
||
let int_of_church (n : church_num) : int = |
let int_of_church (n : church_num) : int = n.f succ 0 |
||
n.f succ 0 |
|||
;; |
|||
(* Now the tasks at hand: *) |
(* Now the tasks at hand: *) |
||
Line 2,027: | Line 2,032: | ||
(* Derive Church numerals three and four in terms of Church zero and a Church successor function *) |
(* Derive Church numerals three and four in terms of Church zero and a Church successor function *) |
||
let ch_three = |
let ch_three = church_of_int 3 |
||
let ch_four = ch_three |> ch_succ |
let ch_four = ch_three |> ch_succ |
||
Line 2,033: | Line 2,038: | ||
let ch_7 = ch_add ch_three ch_four |
let ch_7 = ch_add ch_three ch_four |
||
let ch_12 = ch_mul ch_three ch_four |
let ch_12 = ch_mul ch_three ch_four |
||
let ch_eleven = church_of_int 11 |
|||
let ch_twelve = ch_eleven |> ch_succ |
|||
(* Similarly obtain 4^3 and 3^4 in terms of Church numerals, using a Church numeral exponentiation function *) |
(* Similarly obtain 4^3 and 3^4 in terms of Church numerals, using a Church numeral exponentiation function *) |
||
let ch_64 = ch_exp ch_four ch_three |
let ch_64 = ch_exp ch_four ch_three |
||
let ch_81 = ch_exp ch_three ch_four |
let ch_81 = ch_exp ch_three ch_four |
||
;; |
|||
(* check that ch_is_zero works *) |
|||
⚫ | |||
let ch_1 = ch_is_zero ch_zero |
|||
List.map |
|||
let ch_0 = ch_is_zero ch_three |
|||
int_of_church |
|||
⚫ | |||
(* check church predecessor, subtraction, and division, functions work *) |
|||
let ch_2 = ch_pred ch_three |
|||
let ch_8 = ch_sub ch_eleven ch_three |
|||
let ch_3 = ch_div ch_eleven ch_three |
|||
let ch_4 = ch_div ch_twelve ch_three |
|||
⚫ | |||
let result = List.map (fun c -> string_of_int(int_of_church c)) |
|||
⚫ | |||
ch_eleven; ch_twelve; ch_1; ch_0; ch_2; ch_8; ch_3; ch_4 ] |
|||
|> String.concat "; " |> Printf.sprintf "[ %s ]" |
|||
;; |
;; |
||
</lang> |
|||
print_endline result</lang> |
|||
{{out}} |
|||
<pre>[ 3; 4; 7; 12; 64; 81; 11; 12; 1; 0; 2; 8; 3; 4 ]</pre> |
|||
=={{header|Octave}}== |
=={{header|Octave}}== |