Church numerals: Difference between revisions
→{{header|Haskell}}: Add more complex Church functions and comments...
GordonBGood (talk | contribs) (→All closures and a union for type-punning: Nim, simplify and improve code...) |
GordonBGood (talk | contribs) (→{{header|Haskell}}: Add more complex Church functions and comments...) |
||
Line 666:
=={{header|Haskell}}==
The following code implements the more complex Church functions using `unsafeCoerce` to avoid non-decidable infinite types:
<lang haskell>import Unsafe.Coerce ( unsafeCoerce )
type Church a = (a -> a) -> a -> a
churchZero :: Church a
churchZero = const id
churchOne :: Church a
churchOne = id
succChurch :: Church a -> Church a
succChurch = (<*>) (.) -- add one recursion, or \ ch f -> f . ch f
addChurch :: Church a -> Church a -> Church a
addChurch = (<*>). fmap (.) -- or \ ach bch f -> ach f . bch f
multChurch :: Church a -> Church a -> Church a
multChurch = (.) -- or \ ach bch -> ach . bch
expChurch basech expch = unsafeCoerce expch basech
isChurchZero :: Church a -> Church a
isChurchZero ch = unsafeCoerce ch (const churchZero) churchOne
predChurch :: Church a -> Church a
predChurch ch f x = unsafeCoerce ch (\ g h -> h (g f)) (const x) id
minusChurch :: Church a -> Church a -> Church a
minusChurch ach bch = unsafeCoerce bch predChurch ach
-- counts the times divisor can be subtracted from dividend to zero...
divChurch :: Church a -> Church a -> Church a
divChurch dvdnd dvsr =
let divr n d =
(\ v -> v (const $ succChurch $ divr v d) -- if branch
churchZero -- else branch
) (minusChurch n d)
in divr (unsafeCoerce succChurch dvdnd) $ unsafeCoerce dvsr
churchFromInt :: Int -> Church a
churchFromInt 0 = churchZero
churchFromInt n =
-- Or as a fold:
Line 686 ⟶ 716:
-- Or as an iterated application:
-- churchFromInt n = iterate
intFromChurch ::
intFromChurch
------------------------------------- TEST -------------------------------------
main :: IO ()
main = do
let [cThree, cFour, cEleven, cTwelve] = churchFromInt <$> [3, 4, 11, 12]
print $ fmap intFromChurch [ addChurch cThree cFour
, multChurch cThree cFour
, expChurch cFour cThree
, isChurchZero churchZero
, predChurch cFour
, minusChurch cEleven cThree
, divChurch cEleven cThree
, divChurch cTwelve cThree
]</lang>
{{Out}}
<pre>[7, 12, 81, 64,
Note that Haskell has directly recursive functions so the y-Combinator is not used to implement recursion in the Church division function.
This version should be suitable to translation to most statically typed languages supporting first class closure functions using casting and/or type "punning" to eliminate the infinite types problems such as is done in the second Nim contribution.
==={{header|Use of RankNTypes to Avoid Coercion}}===
The following code uses a wrapper `newtype` and the "RankNTypes" GHC Haskell extension to avoid the requirement for the unsafe coercion used above:
<lang haskell>{-# LANGUAGE RankNTypes #-}
newtype Church = Church { unChurch :: forall a. (a -> a) -> a -> a }
churchZero :: Church
churchZero = Church $ const id
succChurch :: Church -> Church
succChurch ch = Church $ (<*>) (.) $ unChurch ch -- add one recursion
addChurch :: Church -> Church -> Church
addChurch ach bch =
Church $ ((<*>) . fmap (.)) (unChurch ach) (unChurch bch)
multChurch :: Church -> Church -> Church
multChurch ach bch = Church $ unChurch ach . unChurch bch
expChurch :: Church -> Church -> Church
expChurch basech expch = Church $ unChurch expch $ unChurch basech
predChurch :: Church -> Church
predChurch ch = Church $ \ f x ->
unChurch ch (\ g h -> h (g f)) (const x) id
minusChurch :: Church -> Church -> Church
minusChurch ach bch = unChurch bch predChurch ach
isChurchZero :: Church -> Church
isChurchZero ch = unChurch ch (const churchZero) $ Church id
divChurch :: Church -> Church -> Church
divChurch dvdnd dvsr =
let divr n =
(\ v -> unChurch v
(const $ succChurch $ divr v)
churchZero
)(minusChurch n dvsr)
in divr (succChurch dvdnd)
churchFromInt :: Int -> Church
churchFromInt 0 = churchZero
churchFromInt n = succChurch $ churchFromInt (n - 1)
-- Or as a fold:
-- churchFromInt n = foldr (.) id . replicate n
-- Or as an iterated application:
-- churchFromInt n = iterate succChurch churchZero !! n
intFromChurch :: Church -> Int
intFromChurch ch = unChurch ch succ 0
------------------------------------- TEST -------------------------------------
main :: IO ()
main = do
let [cThree, cFour, cEleven, cTwelve] = churchFromInt <$> [3, 4, 11, 12]
print $ fmap intFromChurch [ addChurch cThree cFour
, multChurch cThree cFour
, expChurch cFour cThree
, expChurch cThree cFour
, isChurchZero churchZero
, predChurch cFour
, minusChurch cEleven cThree
, divChurch cEleven cThree
, divChurch cTwelve cThree
]</lang>
{{out}}
<pre>[7, 12, 81, 64, 1, 0, 3, 8, 3, 4]</pre>
Note that Haskell has directly recursive functions so the y-Combinator is not used to implement recursion in the Church division function.
=={{header|Java}}==
| |||