Church numerals: Difference between revisions
→Alternate Method Using Discriminated Unions: add comments and a new side effect free version...
GordonBGood (talk | contribs) (→{{header|F#}}: add a much cleaner and faster version that doesn't use marshalling to classes...) |
GordonBGood (talk | contribs) (→Alternate Method Using Discriminated Unions: add comments and a new side effect free version...) |
||
Line 518:
===Alternate Method Using Discriminated Unions===
The above code is not only slow but ugly, and given that it breaks all static typing by using dynamic type erasing through interfaces/objects, it might be said to be fugly!
The following code uses F#'s Discriminated Unions to express the multi-ranked function Kinds that work like C# delegates; this code still uses side effects to convert the resulting Church Numerals, which is a facility that F# offers so we may as well use it since it is easily expressed:
Line 548 ⟶ 550:
applyChurch (applyChurch chb <| Church predChurch) cha
let
let rec divr n =
let loop v = Church <| fun _ -> succChurch <| divr v
Line 555 ⟶ 557:
divr <| succChurch chdvdnd
let
let churchToInt ch =
let mutable count: int = 0
let addint1 = Church <| fun v -> count <- count + 1; v
applyChurch (applyChurch ch addint1) churchZero |> ignore
count
▲let iton i = List.fold (>>) id (List.replicate i succChurch) churchZero
#nowarn "25" // eliminate incomplete pattern match warning
[<EntryPoint>]
let main _ =
let [c3; c4; c11; c12] = List.map
[ addChurch c3 c4
; multChurch c3 c4
Line 574 ⟶ 577:
; predChurch c4
; subChurch c11 c3
;
; division c12 c3
] |> List.map
0 // return an integer exit code</lang>
{{out}}
<pre>[7; 12; 64; 81; 1; 0; 2; 8; 3; 4]</pre>
The above code
===Using Pure Functional Code===
One can achieve functional purity (without side effects) within the "RankNTypes" functions defined using the recursive Discriminated Unions as per the above code by including a tag of the "arity zero" case which just wraps a value. The following code uses that to be able to convert from Church Numerals to integers without using side effects:
<lang fsharp>#nowarn "25" // eliminate incomplete pattern match warning
// types...
type Church<'a> = Church of (Church<'a> -> Church<'a>)
| ArityZero of 'a
let applyChurch (Church chf) charg =
chf charg
let composeChurch (Church chlf) (Church chrf) =
Church <| fun f -> (chlf << chrf) f
let churchZero<'a> = Church <| fun (_: Church<'a>) -> Church id
let churchOne = Church id
let succChurch (Church chf) =
Church <| fun f -> composeChurch f <| chf f
let addChurch cha chb =
Church <| fun f -> composeChurch (applyChurch cha f) (applyChurch chb f)
let multChurch cha chb =
composeChurch cha chb
let expChurch chbs chexp =
applyChurch chexp chbs
let isZeroChurch ch =
applyChurch (applyChurch ch (Church <| fun _ -> churchZero)) churchOne
let predChurch ch =
Church <| fun f -> Church <| fun x ->
let prdf = Church <| fun g -> Church <| fun h ->
applyChurch h (applyChurch g f)
applyChurch (applyChurch (applyChurch ch prdf)
(Church <| fun _ -> x)) <| Church id
let subChurch cha chb =
applyChurch (applyChurch chb <| Church predChurch) cha
let divChurch chdvdnd chdvsr =
let rec divr n =
let loop v = Church <| fun _ -> succChurch <| divr v
let tst v = applyChurch (applyChurch v <| loop v) churchZero
tst <| subChurch n chdvsr
divr <| succChurch chdvdnd
let intToChurch<'a> i =
List.fold (>>) id (List.replicate i succChurch) churchZero<'a>
let churchToInt ch =
let succInt = Church <| fun (ArityZero v) -> ArityZero <| v + 1
match applyChurch (applyChurch ch succInt) <| ArityZero 0 with
ArityZero r -> r
[<EntryPoint>]
let main _ =
let [c3; c4; c11; c12] = List.map intToChurch [3; 4; 11; 12]
[ addChurch c3 c4
; multChurch c3 c4
; expChurch c4 c3
; expChurch c3 c4
; isZeroChurch churchZero
; isZeroChurch c3
; predChurch c4
; subChurch c11 c3
; divChurch c11 c3
; divChurch c12 c3
] |> List.map churchToInt |> printfn "%A"
0 // return an integer exit code</lang>
{{out}}
<pre>[7; 12; 64; 81; 1; 0; 2; 8; 3; 4]</pre>
The above code runs at about the same speed as the Discriminated Union version with side effects.
Since F# allows non-total matching and will just generate an exception for cases not covered, the warning for non-used matches has been suppressed.
The "churchToInt" function works by applying an integer successor function which takes an "arity zero" value and returns an "arity zero" containing that value plus one, then applying an "arity zero" wrapped integer value of zero to the resulting Church value; the result of that is unwrapped to result in the desired integer returned value. The idea of using "arity zero" values as function values is borrowed from Haskell, which wraps all values as data types including integers, etc. (all other than primitive values are thus "lifted"), which allows them to be used as functions. Since Haskell has Type Classes which F# does not, this is not so obvious in Haskell code which is able to treat values such as "lifted" integers as functions automatically, and thus apply the same Type Class functions to them as to regular (also "lifted") functions. Here in the F# code, the necessary functions that would normally be part of the Functor and Applicative Type Classes as applied to Functions in Haskell are supplied here to work with the Discriminated Union wrapping of this Function idea.
=={{header|Fōrmulæ}}==
| |||