Skip to content

@rampion /ChurchList.hs
Created

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
{-# LANGUAGE RankNTypes #-}
module ChurchList where
import Data.Monoid
import Prelude hiding (zipWith)
-- church encoding for pairs
newtype ChurchPair a b = CP { runCP :: forall c. (a -> b -> c) -> c }
comma :: a -> b -> ChurchPair a b
comma a b = CP $ \c -> c a b
toPair :: ChurchPair a b -> (a,b)
toPair (CP cuncurry) = cuncurry (,)
fromPair :: (a,b) -> ChurchPair a b
fromPair = uncurry comma
instance Functor (ChurchPair a) where
fmap f (CP cuncurry) = CP $ \c -> cuncurry $ \a -> c a . f
instance Monoid a => Monad (ChurchPair a) where
return = comma mempty
(CP cuncurry) >>= f = CP $ \c -> cuncurry $ \a b -> f b `runCP` (c . mappend a)
-- church encoding for maybe
newtype ChurchMaybe a = CM { runCM :: forall b. b -> (a -> b) -> b }
nothing :: ChurchMaybe a
nothing = CM $ \n j -> n
just :: a -> ChurchMaybe a
just a = CM $ \n j -> j a
toMaybe :: ChurchMaybe a -> Maybe a
toMaybe (CM cmaybe) = cmaybe Nothing Just
fromMaybe :: Maybe a -> ChurchMaybe a
fromMaybe = maybe nothing just
instance Functor ChurchMaybe where
fmap f (CM cmaybe) = CM $ \n j -> cmaybe n (j.f)
instance Monad ChurchMaybe where
return = just
(CM cmaybe) >>= f = CM $ \n j -> cmaybe n $ \a -> runCM (f a) n j
-- church encoding for list
newtype ChurchList a = CL { runCL :: forall b. (a -> b -> b) -> b -> b }
nil :: ChurchList a
nil = CL $ \c n -> n
cons :: a -> ChurchList a -> ChurchList a
cons a (CL cfoldr) = CL $ \c n -> c a $ cfoldr c n
toList :: ChurchList a -> [a]
toList (CL cfoldr) = cfoldr (:) []
fromList :: [a] -> ChurchList a
fromList = foldr cons nil
instance Functor ChurchList where
fmap f (CL cfoldr) = CL $ \c n -> cfoldr (c.f) n
instance Monad ChurchList where
return a = cons a nil
(CL cfoldr) >>= f = CL $ \c n -> cfoldr (\a b -> runCL (f a) c b) n
uncons :: ChurchList a -> ChurchMaybe (ChurchPair a (ChurchList a))
uncons (CL cfoldr) = cfoldr (\a (CM cmaybe) -> just . comma a . cmaybe nil $ \(CP cuncurry) -> cuncurry cons) nothing
zipWith :: (a -> b -> c) -> ChurchList a -> ChurchList b -> ChurchList c
zipWith f as bs = runCM (uncons as) nil . flip runCP $ \a as' ->
runCM (uncons bs) nil . flip runCP $ \b bs' ->
f a b `cons` zipWith f as' bs'
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.