Skip to content
Create a gist now

Instantly share code, notes, and snippets.

{-# 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'
@ChristopherKing42

What is the computational complexity of zipWith?

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.