Church numerals: Difference between revisions
→{{header|Elm}}: add Extended Church Numeral functions and comments...
GordonBGood (talk | contribs) (→Alternate Method Using Discriminated Unions: add comments and a new side effect free version...) |
GordonBGood (talk | contribs) (→{{header|Elm}}: add Extended Church Numeral functions and comments...) |
||
Line 426:
{{out}}
<pre>[7,12,81,64]</pre>
===Extended Church Numeral Functions===
{{trans|F#}}
<lang elm>module Main exposing (main)
import Html exposing (text)
-- the Church wrapper and functions...
type Church a = Church (Church a -> Church a)
| ArityZero a -- treat a value as a function
applyChurch : Church a -> Church a -> Church a
applyChurch ch charg = case ch of Church chf -> chf charg
ArityZero _ -> charg -- never happens!
composeChurch : Church a -> Church a -> Church a
composeChurch chl chr =
case chl of Church chlf ->
case chr of Church chrf -> Church <| \ f -> (chlf << chrf) f
otherwise -> chr -- never happens!
otherwise -> chr -- never happens!
-- the Church Numeral functions...
churchZero : Church a
churchZero = Church <| always <| Church identity
churchOne : Church a
churchOne = Church identity
succChurch : Church a -> Church a
succChurch ch = Church <| \ f -> composeChurch f <| applyChurch ch f
addChurch : Church a -> Church a -> Church a
addChurch cha chb =
Church <| \ f -> composeChurch (applyChurch cha f) (applyChurch chb f)
multChurch : Church a -> Church a -> Church a
multChurch cha chb = composeChurch cha chb
expChurch : Church a -> Church a -> Church a
expChurch chbs chexp = applyChurch chexp chbs
isZeroChurch : Church a -> Church a
isZeroChurch ch =
applyChurch (applyChurch ch (Church <| \ _ -> churchZero)) churchOne
predChurch : Church a -> Church a
predChurch ch =
Church <| \ f -> Church <| \ x ->
let prdf = Church <| \ g -> Church <| \ h ->
applyChurch h (applyChurch g f)
in applyChurch (applyChurch (applyChurch ch prdf)
(Church <| \ _ -> x)) <| Church identity
subChurch : Church a -> Church a -> Church a
subChurch cha chb = applyChurch (applyChurch chb <| Church predChurch) cha
divChurch : Church a -> Church a -> Church a
divChurch chdvdnd chdvsr =
let divr n =
let loop v = Church <| \ _ -> succChurch <| divr v
tst v = applyChurch (applyChurch v <| loop v) churchZero
in tst <| subChurch n chdvsr
in divr <| succChurch chdvdnd
-- conversion functions...
intToChurch : Int -> Church a
intToChurch i = List.foldl (\ _ ch -> succChurch ch) churchZero (List.range 1 i)
churchToInt : Church Int -> Int
churchToInt ch =
let succInt = Church <| \ ach -> case ach of ArityZero v -> ArityZero (v + 1)
otherwise -> ach -- never happens!
in case applyChurch (applyChurch ch succInt) <| ArityZero 0 of
ArityZero r -> r
otherwise -> -1 -- never happens!
--------------------------------------TEST--------------------------------------
main : Html.Html Never
main =
let chThree = intToChurch 3
chFour = succChurch chThree
chEleven = intToChurch 11
chTwelve = succChurch chEleven
in [ addChurch chThree chFour
, multChurch chThree chFour
, expChurch chFour chThree
, expChurch chThree chFour
, isZeroChurch churchZero
, isZeroChurch chThree
, predChurch chFour
, subChurch chEleven chThree
, divChurch chEleven chThree
, divChurch chTwelve chThree
] |> List.map (String.fromInt << churchToInt)
|> String.join ", " |> text</lang>
{{out}}
<pre>7, 12, 64, 81, 1, 0, 3, 8, 3, 4</pre>
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# and Elm do 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/custom type wrapping of this Function idea.
=={{header|Erlang}}==
| |||