{-# LANGUAGE GADTs, RankNTypes, KindSignatures, FlexibleInstances, TypeOperators #-}
module Data.Thrist ( 
      -- * Types:
        Thrist (..)
      , Flipped (..)
      -- * Fold and map functions:
      , mapThrist 
      , foldrThrist
      , foldlThrist
      , foldr1Thrist
      , foldl1Thrist
      -- ** Monadic functions:
      , mapMThrist
      , foldMThrist
      -- * Other list-like functions:
      , appendThrist
      , nullThrist
      ) where

import Prelude hiding ((.), id)
import Control.Category
import Data.Monoid
import Control.Arrow
import Control.Monad


-- | A type-threaded list of binary polymorphic types.
data Thrist :: (* -> * -> *) -> * -> * -> * where
  Nil :: Thrist (~>) a a
  Cons :: (a ~> b) -> Thrist (~>) b c -> Thrist (~>) a c

instance Monoid (Thrist (~>) a a) where
  mempty  = Nil
  mappend = appendThrist

instance (Arrow (~>)) => Arrow (Thrist (~>)) where
  arr f     = Cons (arr f) Nil
  first Nil = Nil
  first t   = Cons ((foldrThrist (flip (.)) id t) *** id) Nil

instance Category (Thrist (~>)) where
  id    = Nil
  b . a = appendThrist a b


-- | A newtype wrapper, defined for convenience, that "swaps" the two type
-- variables of a binary type. Can be used to reverse a Thrist using 
-- `foldlThrist`. See examples.
newtype Flipped m a b = Flipped { unflip :: m b a }


-- | Equivalent to `foldr` for thrists. Takes a combining function, a value to
-- replace Nil, and a thrist, returning some new binary type.
foldrThrist :: (forall i j . (i ~> j) -> (j +> c) -> (i +> c)) 
            -> (b +> c) 
            -> Thrist (~>) a b 
            -> (a +> c)
foldrThrist _ v Nil        = v
foldrThrist f v (Cons h t) = h `f` (foldrThrist f v t)

-- | Equivalent to (++) for thrists. 
appendThrist :: Thrist (~>) a b -> Thrist (~>) b c -> Thrist (~>) a c
appendThrist = flip (foldrThrist Cons)

-- | Equivalent to `map` for thrists. Takes a function from one binary type to 
-- another and applies it to each thrist element. For example this could 
-- convert a thrist of (a,b) into a thrist of Either a b:
mapThrist :: (forall i j . (i +> j) -> (i ~> j)) 
          -> Thrist (+>) a b 
          -> Thrist (~>) a b
mapThrist f = foldrThrist (Cons . f) Nil 


-- | Equivalent to `foldl` for `Thrist`s.
foldlThrist :: (forall j k . (a +> j) -> (j ~> k) -> (a +> k)) 
            -> (a +> b) 
            -> Thrist (~>) b c 
            -> (a +> c)
foldlThrist _ v Nil        = v
foldlThrist f v (Cons h t) = foldlThrist f (v `f` h) t 



-- | Equivalent to `foldl1` for `Thrist`s.
foldl1Thrist :: (forall i j k. (i ~> j) -> (j ~> k) -> (i ~> k))
             -> Thrist (~>) a b
             -> (a ~> b)
foldl1Thrist f (Cons a th) = foldlThrist f a th
foldl1Thrist _ Nil         = error "empty thrist"

    

-- | Equivalent to `foldr1` for `Thrist`s.
foldr1Thrist :: (forall i j k. (i ~> j) -> (j ~> k) -> (i ~> k))
             -> Thrist (~>) a b
             -> (a ~> b)
foldr1Thrist _ (Cons b Nil) = b
foldr1Thrist f (Cons a th)  = f a $ foldr1Thrist f th
foldr1Thrist _ Nil          = error "empty thrist"



-- | Equivalent to `mapM` on `Thrist`s. 
mapMThrist :: Monad m => 
             (forall i j . (i +> j) -> m (i ~> j)) 
           -> Thrist (+>) a b 
           -> m (Thrist (~>) a b)
mapMThrist _ Nil        = return Nil
mapMThrist f (Cons h t) = liftM2 Cons (f h) (mapMThrist f t)


-- | Equivalent to `foldM` on `Thrist`s.
foldMThrist :: Monad m => 
               (forall j k . (a +> j) -> (j ~> k) -> m (a +> k)) 
            -> (a +> b) 
            -> Thrist (~>) b c 
            -> m (a +> c)
foldMThrist _ a Nil        = return a
foldMThrist f a (Cons h t) = f a h >>= \fah -> foldMThrist f fah t



-- | Returns `True` when the Thrist is `Nil`.
nullThrist :: Thrist (~>) a b -> Bool
nullThrist Nil = True
nullThrist _   = False

-- | Returns the length of the Thrist.
lengthThrist :: Thrist (~>) a b -> Int
lengthThrist Nil = 0
lengthThrist (Cons _ rest) = 1 + lengthThrist rest