{-# Language RankNTypes, FlexibleInstances, MultiParamTypeClasses #-}
module Church where

import Data.Functor.Identity

import Traversable -- for fusion rules
import Unfoldable_r
import Unfoldable
import Empty
import FIFO_r
import FIFO
import State

----
-- Church0 for Stream

data Church0 a = Church0 {runChurch0 :: forall b. (((a,b) -> b) -> b)}

instance Set0_r Identity Church0 where
 set0_r (Identity x,(Church0 xs)) = Church0 (\set0' -> set0' (x,(xs set0')))

instance Set0 Church0

instance Unfoldable0_r Identity Church0 where
 unfoldr0_r = unfoldr0_rDefault

instance Unfoldable0 Church0 where
 unfoldr0 = unfoldr0Default

build0 :: Set0 f => Church0 a -> f a
{-# INLINE [1] build0 #-}
build0 (Church0 f) = f set0

{-# RULES
"foldr0'/build0"    forall k (g::forall b. ((a,b) -> b) -> b) .
                    foldr0' k (build0 (Church0 g)) = g (uncurry k)
#-}

loop0 :: Set0 f => s -> State0 s a -> f a
loop0 s = build0 . unfoldr0 s


----
-- Church1 for Linear

data Church1 a = Church1 {runChurch1 :: forall b. (((a,Maybe b) -> b) -> b)}

instance Set0_r Identity Church1 where
 set0_r = set0_rDefault

-- instance Set0 Church1

instance Unfoldable0_r Identity Church1 where

instance Unfoldable0 Church1

instance Set1_r Identity Church1 where
 set1_r (Identity x,Nothing) = Church1 (\f -> f (x,Nothing))
 set1_r (Identity x,Just (Church1 xs)) = Church1 (\set1' -> set1' (x,Just (xs set1')))

instance Set1 Church1

instance Unfoldable1_r Identity Church1 where
 unfoldr1_r = unfoldr1_rDefault

instance Unfoldable1 Church1 where
 unfoldr1 = unfoldr1Default

build1 :: Set1 f => Church1 a -> f a
{-# INLINE [1] build1 #-}
build1 (Church1 f) = f set1

{-# RULES
"foldr1'/build1"    forall k (g::forall b. ((a,Maybe b) -> b) -> b) .
                    foldr1' k (build1 (Church1 g)) = g (uncurry k)
#-}

loop1 :: Set1 f => s -> State1 s a -> f a
loop1 s = build1 . unfoldr1 s

----
-- Church for Stack

data Church a = Church {runChurch :: forall b. ((Maybe (a,b) -> b) -> b)}

instance Set0_r Identity Church where
 set0_r = set0_rDefault

instance Set0 Church

instance Set1_r Identity Church where
 set1_r = set1_rDefault

instance Set1 Church

instance Empty Church where
 empty = emptyDefault
 isEmpty = error "isEmpty Church"

instance Set_r Identity Church where
 set_r Nothing = Church (\f -> f Nothing)
 set_r (Just (Identity x,(Church xs))) = Church (\set' -> set' (Just (x,(xs set'))))

instance Set Church

instance Unfoldable0_r Identity Church

instance Unfoldable0 Church

instance Unfoldable1_r Identity Church

instance Unfoldable1 Church

instance Unfoldable_r Identity Church where
 unfoldr_r = unfoldr_rDefault

instance Unfoldable Church where
 unfoldr = unfoldrDefault

build :: Set f => Church a -> f a
{-# INLINE [1] build #-}
build (Church f) = f set

{-# RULES
"foldr'/build"    forall b k (g::forall b. (Maybe (a,b) -> b) -> b) .
                  foldr' k b (build (Church g)) = g ((\f b' -> maybe b' (uncurry f)) k b)
#-}


loop :: Set f => s -> State s a -> f a
loop s = build . unfoldr s