Church numerals: Difference between revisions

Content added Content deleted
(→‎All closures and a union for type-punning: Nim, simplify and improve code...)
(→‎{{header|Haskell}}: Add more complex Church functions and comments...)
Line 666: Line 666:


=={{header|Haskell}}==
=={{header|Haskell}}==
<lang haskell>--------------------- CHURCH NUMERALS --------------------


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
churchZero = const id


churchOne :: Church a
churchSucc = (<*>) (.)
churchOne = id


succChurch :: Church a -> Church a
churchAdd = (<*>) . fmap (.)
succChurch = (<*>) (.) -- add one recursion, or \ ch f -> f . ch f


addChurch :: Church a -> Church a -> Church a
churchMult = (.)
addChurch = (<*>). fmap (.) -- or \ ach bch f -> ach f . bch f


multChurch :: Church a -> Church a -> Church a
churchExp = flip id
multChurch = (.) -- or \ ach bch -> ach . bch


churchFromInt :: Int -> ((a -> a) -> a -> a)
expChurch :: Church a -> Church a -> Church a
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 0 = churchZero
churchFromInt n = churchSucc $ churchFromInt (n - 1)
churchFromInt n = succChurch $ churchFromInt (n - 1)


-- Or as a fold:
-- Or as a fold:
Line 686: Line 716:


-- Or as an iterated application:
-- Or as an iterated application:
-- churchFromInt n = iterate churchSucc churchZero !! n
-- churchFromInt n = iterate succChurch churchZero !! n


intFromChurch :: ((Int -> Int) -> Int -> Int) -> Int
intFromChurch :: Church Int -> Int
intFromChurch cn = cn succ 0
intFromChurch ch = ch succ 0


------------------------------------- TEST -------------------------------------

--------------------------- TEST -------------------------
main :: IO ()
main :: IO ()
main = do
main = do
let [cThree, cFour] = churchFromInt <$> [3, 4]
let [cThree, cFour, cEleven, cTwelve] = churchFromInt <$> [3, 4, 11, 12]
print $ fmap intFromChurch [ addChurch cThree cFour
print $
, multChurch cThree cFour
fmap
, expChurch cFour cThree
intFromChurch
[ churchAdd cThree cFour,
, expChurch cThree cFour
, isChurchZero churchZero
churchMult cThree cFour,
, predChurch cFour
churchExp cFour cThree,
, minusChurch cEleven cThree
churchExp cThree cFour
, divChurch cEleven cThree
]</lang>
, divChurch cTwelve cThree
]</lang>
{{Out}}
{{Out}}
<pre>[7,12,64,81]</pre>
<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.

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}}==
=={{header|Java}}==
Retrieved from "https://rosettacode.org/wiki/Church_numerals"