Church numerals: Difference between revisions
→{{header|F#}}: Add a more complete set of Church functions with comments...
GordonBGood (talk | contribs) (→{{header|C sharp}}: Added extended Church functions and comments...) |
GordonBGood (talk | contribs) (→{{header|F#}}: Add a more complete set of Church functions with comments...) |
||
Line 459:
=={{header|F#}}==
<lang fsharp>type INumeral =▼
abstract Apply : ('a -> 'a) -> 'a -> 'a▼
The following code uses what is seemingly the only work around to implement Haskell's "RankNTypes" in F# by using an abstract Interface type to represent it and create and instantiate a new type for every invocation of the wrapped function as required to implement this more complete set of Church functions, especially subtraction and division:
let zero = {new INumeral with override __.Apply _ x = x}▼
{{trans|C sharp}}
let successor (n: INumeral) = {new INumeral with override __.Apply f x = f (n.Apply f x)}▼
let addition (m: INumeral) (n: INumeral) = {new INumeral with override __.Apply f x = m.Apply f (n.Apply f x)}▼
let multiplication (m: INumeral) (n: INumeral) = {new INumeral with override __.Apply f x = m.Apply (n.Apply f) x}▼
let exponential (m: INumeral) (n: INumeral) = {new INumeral with override __.Apply f x = n.Apply m.Apply f x}▼
let
let iton i = List.fold (>>) id (List.replicate i successor) zero▼
let succChurch (n: IChurch) =
▲
let addChurch (m: IChurch) (n: IChurch) =
▲
let multChurch (m: IChurch) (n: IChurch) =
▲
let expChurch (m: IChurch) (n: IChurch) =
▲
let iszeroChurch (n: IChurch) =
{ new IChurch with
override __.Apply f = n.Apply (fun _ -> zeroChurch.Apply) oneChurch.Apply f }
let predChurch (n: IChurch) =
{ new IChurch with
override __.Apply f = fun x -> n.Apply (fun g h -> h (g f))
(fun _ -> x) id }
let subChurch (m: IChurch) (n: IChurch) =
{ new IChurch with override __.Apply f = (n.Apply predChurch m).Apply f }
let divChurch (dvdnd: IChurch) (dvsr: IChurch) =
let rec divr (n: IChurch) (d: IChurch) =
{ new IChurch with
override __.Apply f =
((fun (v: IChurch) -> // test v for Church zeroChurch...
v.Apply (fun _ -> (succChurch (divr v d)).Apply) // if not zeroChurch
zeroChurch.Apply)(subChurch n d)) f }
divr (succChurch dvdnd) dvsr
let chtoi (ch: IChurch) = ch.Apply ((+) 1) 0
#nowarn "25" // skip incomplete pattern warning
[<EntryPoint>]
let main _ =
let [c3; c4; c11; c12] = List.map itoch [3; 4; 11; 12]
[ addChurch c3 c4
; multChurch c3 c4
; expChurch c4 c3
; expChurch c3 c4
; iszeroChurch zeroChurch
; iszeroChurch oneChurch
; predChurch c3
; subChurch c11 c3
; divChurch c11 c3
; divChurch c12 c3
] |> List.map chtoi |> printfn "%A"
0 // return an integer exit code</lang>
{{out}}
<pre>[7; 12; 64; 81; 1; 0; 2; 8; 3; 4]</pre>
Using the Abstract Interface work around is extremely slow, especially for the recursive Church division function which requires many type creations and instantiations such that the execution time for even these small numbers can take many seconds.
=={{header|Fōrmulæ}}==
| |||