{-# OPTIONS_GHC -XRankNTypes #-}

module Main 
where

--- http://stackoverflow.com/questions/13346200/type-safe-difference-lists



newtype F a = F { runF :: forall r. r -> (a -> r -> r) -> r }

empty = F (\r g->r)
singleton x = F (\r g-> g x r)

{-
*Main> runF empty [1] (:)
[1]

*Main> runF (singleton 2) [1] (:)
[2,1]

*Main> runF (singleton 4) [3,2,1] (:)
[4,3,2,1]

*Main> runF (singleton 2) [1] (\a r->[a])
[2]

*Main> runF (singleton 4) [3,2,1] (\a r->a:reverse r)
[4,1,2,3]

-}

x4 = runF (singleton 4) [3,2,1] (\a r->a:reverse r)


fromList []     = empty         -- fromList [x] = singleton x

fromList (x:xs) = F (\r g-> g x $ runF (fromList xs) r g)


{-
*Main> runF (fromList [1..4]) [] (:)
[1,2,3,4]

*Main> runF (fromList [1..4]) [] (\a r->[a])
[1]

*Main> runF (fromList [1..4]) [] (\a r->a:reverse r)
[1,3,4,2]

*Main> runF (fromList [1..4]) [] (\a r->a:reverse r++r)
[1,4,4,3,3,4,4,2,2,4,4,3,3,4,4]

*Main> runF (append (fromList [1,2]) (fromList [3,4]))[] (\a r->a:reverse r++r)
[1,4,4,3,3,4,4,2,2,4,4,3,3,4,4]
                                 -- same result as above... OK we can argue that
                                 -- appending worked right, it's the reporting that
                                 -- is screwing things up here
-}


append a b = F (\r g-> runF a (runF b r g) g)     

toList a = runF a [] (:)


{-
*Main> toList (append (fromList [1..4]) (fromList [11..15]))
[1,2,3,4,11,12,13,14,15]



BUT!! IF we define    -- and the point it, WE *CAN* --
                      --   the proper chaining is NOT enforced by the type 
                      --   the `g` functions are "too loose"


> append a b = F (\r g-> runF b (runF a r g) g)       --- NB!! switched a/b <--> b/a


THEN


*Main> runF (append (fromList [1,2]) (fromList [3,4]))[] (\a r->a:reverse r++r)
[3,2,2,1,1,2,2,4,4,2,2,1,1,2,2]
                                 -- DIFFERENT RESULT!!! OK, we could argue that
                                 -- this "swapped" append is wrong for this kind of
                                 -- "reporting function" ut the point is, the type
                                 -- allowed us to do this... so this means it's "too big", right?


*Main> toList (append (fromList [1..4]) (fromList [11..15]))
[11,12,13,14,15,1,2,3,4]
-}