-- | Church-encoded lists. Used in Twee.CP to make sure that fusion happens.
{-# LANGUAGE Rank2Types, BangPatterns #-}
module Data.ChurchList where

import Prelude(Functor(..), Applicative(..), Monad(..), Bool(..), Maybe(..), (.), ($), id)
import qualified Prelude
import GHC.Magic(oneShot)
import GHC.Exts(build)
import Control.Monad(MonadPlus(..), liftM2)
import Control.Applicative(Alternative(..))

newtype ChurchList a =
  ChurchList (forall b. (a -> b -> b) -> b -> b)

{-# INLINE foldr #-}
foldr :: (a -> b -> b) -> b -> ChurchList a -> b
foldr :: forall a b. (a -> b -> b) -> b -> ChurchList a -> b
foldr a -> b -> b
op b
e (ChurchList forall b. (a -> b -> b) -> b -> b
f) = forall a. a -> a
eta (forall b. (a -> b -> b) -> b -> b
f a -> b -> b
op (forall a. a -> a
eta b
e))
  -- Using eta here seems to help with eta-expanding foldl'

{-# INLINE[0] eta #-}
eta :: a -> a
eta :: forall a. a -> a
eta a
x = a
x
{-# RULES "eta" forall f. eta f = \x -> f x #-}

{-# INLINE nil #-}
nil :: ChurchList a
nil :: forall a. ChurchList a
nil = forall a. (forall b. (a -> b -> b) -> b -> b) -> ChurchList a
ChurchList (\a -> b -> b
_ b
n -> b
n)

{-# INLINE unit #-}
unit :: a -> ChurchList a
unit :: forall a. a -> ChurchList a
unit a
x = forall a. (forall b. (a -> b -> b) -> b -> b) -> ChurchList a
ChurchList (\a -> b -> b
c b
n -> a -> b -> b
c a
x b
n)

{-# INLINE cons #-}
cons :: a -> ChurchList a -> ChurchList a
cons :: forall a. a -> ChurchList a -> ChurchList a
cons a
x ChurchList a
xs = forall a. (forall b. (a -> b -> b) -> b -> b) -> ChurchList a
ChurchList (\a -> b -> b
c b
n -> a -> b -> b
c a
x (forall a b. (a -> b -> b) -> b -> ChurchList a -> b
foldr a -> b -> b
c b
n ChurchList a
xs))

{-# INLINE append #-}
append :: ChurchList a -> ChurchList a -> ChurchList a
append :: forall a. ChurchList a -> ChurchList a -> ChurchList a
append ChurchList a
xs ChurchList a
ys = forall a. (forall b. (a -> b -> b) -> b -> b) -> ChurchList a
ChurchList (\a -> b -> b
c b
n -> forall a b. (a -> b -> b) -> b -> ChurchList a -> b
foldr a -> b -> b
c (forall a b. (a -> b -> b) -> b -> ChurchList a -> b
foldr a -> b -> b
c b
n ChurchList a
ys) ChurchList a
xs)

{-# INLINE join #-}
join :: ChurchList (ChurchList a) -> ChurchList a
join :: forall a. ChurchList (ChurchList a) -> ChurchList a
join ChurchList (ChurchList a)
xss = forall a. (forall b. (a -> b -> b) -> b -> b) -> ChurchList a
ChurchList (\a -> b -> b
c b
n -> forall a b. (a -> b -> b) -> b -> ChurchList a -> b
foldr (\ChurchList a
xs b
ys -> forall a b. (a -> b -> b) -> b -> ChurchList a -> b
foldr a -> b -> b
c b
ys ChurchList a
xs) b
n ChurchList (ChurchList a)
xss)

instance Functor ChurchList where
  {-# INLINE fmap #-}
  fmap :: forall a b. (a -> b) -> ChurchList a -> ChurchList b
fmap a -> b
f ChurchList a
xs = forall a. (forall b. (a -> b -> b) -> b -> b) -> ChurchList a
ChurchList (\b -> b -> b
c b
n -> forall a b. (a -> b -> b) -> b -> ChurchList a -> b
foldr (b -> b -> b
c forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> b
f) b
n ChurchList a
xs)

instance Applicative ChurchList where
  {-# INLINE pure #-}
  pure :: forall a. a -> ChurchList a
pure = forall a. a -> ChurchList a
unit
  {-# INLINE (<*>) #-}
  <*> :: forall a b. ChurchList (a -> b) -> ChurchList a -> ChurchList b
(<*>) = forall (m :: * -> *) a1 a2 r.
Monad m =>
(a1 -> a2 -> r) -> m a1 -> m a2 -> m r
liftM2 forall a b. (a -> b) -> a -> b
($)

instance Monad ChurchList where
  {-# INLINE (>>=) #-}
  ChurchList a
xs >>= :: forall a b. ChurchList a -> (a -> ChurchList b) -> ChurchList b
>>= a -> ChurchList b
f = forall a. ChurchList (ChurchList a) -> ChurchList a
join (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> ChurchList b
f ChurchList a
xs)

instance Alternative ChurchList where
  {-# INLINE empty #-}
  empty :: forall a. ChurchList a
empty = forall a. ChurchList a
nil
  {-# INLINE (<|>) #-}
  <|> :: forall a. ChurchList a -> ChurchList a -> ChurchList a
(<|>) = forall a. ChurchList a -> ChurchList a -> ChurchList a
append

instance MonadPlus ChurchList where
  {-# INLINE mzero #-}
  mzero :: forall a. ChurchList a
mzero = forall (f :: * -> *) a. Alternative f => f a
empty
  {-# INLINE mplus #-}
  mplus :: forall a. ChurchList a -> ChurchList a -> ChurchList a
mplus = forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
(<|>)

{-# INLINE fromList #-}
fromList :: [a] -> ChurchList a
fromList :: forall a. [a] -> ChurchList a
fromList [a]
xs = forall a. (forall b. (a -> b -> b) -> b -> b) -> ChurchList a
ChurchList (\a -> b -> b
c b
n -> forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
Prelude.foldr a -> b -> b
c b
n [a]
xs)

{-# INLINE toList #-}
toList :: ChurchList a -> [a]
toList :: forall a. ChurchList a -> [a]
toList (ChurchList forall b. (a -> b -> b) -> b -> b
f) = forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
build forall b. (a -> b -> b) -> b -> b
f

{-# INLINE foldl' #-}
foldl' :: (b -> a -> b) -> b -> ChurchList a -> b
foldl' :: forall b a. (b -> a -> b) -> b -> ChurchList a -> b
foldl' b -> a -> b
op b
e ChurchList a
xs =
  forall a b. (a -> b -> b) -> b -> ChurchList a -> b
foldr (\a
x b -> b
f -> oneShot :: forall a b. (a -> b) -> a -> b
oneShot (\ (!b
acc) -> b -> b
f (b -> a -> b
op b
acc a
x))) forall a. a -> a
id ChurchList a
xs b
e

{-# INLINE filter #-}
filter :: (a -> Bool) -> ChurchList a -> ChurchList a
filter :: forall a. (a -> Bool) -> ChurchList a -> ChurchList a
filter a -> Bool
p ChurchList a
xs =
  forall a. (forall b. (a -> b -> b) -> b -> b) -> ChurchList a
ChurchList forall a b. (a -> b) -> a -> b
$ \a -> b -> b
c b
n ->
    let            
      {-# INLINE op #-}
      op :: a -> b -> b
op a
x b
xs = if a -> Bool
p a
x then a -> b -> b
c a
x b
xs else b
xs
    in
      forall a b. (a -> b -> b) -> b -> ChurchList a -> b
foldr a -> b -> b
op b
n ChurchList a
xs

{-# INLINE fromMaybe #-}
fromMaybe :: Maybe a -> ChurchList a
fromMaybe :: forall a. Maybe a -> ChurchList a
fromMaybe Maybe a
Nothing = forall a. ChurchList a
nil
fromMaybe (Just a
x) = forall a. a -> ChurchList a
unit a
x

{-# INLINE null #-}
null :: ChurchList a -> Bool
null :: forall a. ChurchList a -> Bool
null = forall a b. (a -> b -> b) -> b -> ChurchList a -> b
foldr (\a
_ Bool
_ -> Bool
False) Bool
True