{-# LANGUAGE TypeOperators, MultiParamTypeClasses, FlexibleInstances, ViewPatterns, FunctionalDependencies #-}

import Prelude hiding (map)
import qualified Data.Sequence as Seq
import Data.Sequence(Seq)

data a :< as = a :< as | NoViewL
data a :> as = as :> a | NoViewR

data End = End | NoEnd


class ViewL a as | as -> a where 
    viewL :: as -> a :< as

class (ViewL a as) => EndR a as | as -> a where
    endR :: as -> End

instance ViewL a [a] where
    viewL (x:xs) = x :< xs
    viewL _ = NoViewL

instance EndR a [a] where
    endR [] = End
    endR _ = NoEnd

instance ViewL a (Seq a) where
    viewL (Seq.viewl -> x Seq.:< xs) = x :< xs
    viewL _ = NoViewL

instance EndR a (Seq a) where
    endR (Seq.viewl -> Seq.EmptyL) = End
    endR _ = NoEnd

class Nil as where
    nil :: as

class Cons a as | as -> a where
    (<:) :: a -> as -> as

instance Cons a [a] where
    x <: xs = x:xs

instance Nil [a] where
    nil = []

instance Cons a (Seq a) where
    x <: xs = x Seq.<| xs

instance Nil (Seq a) where
    nil = Seq.empty

map :: (ViewL a as, EndR a as, Cons b bs, Nil bs) => (a -> b) -> as -> bs
map _ (endR -> End) = nil
map f (viewL -> x :< xs) = f x <: map f xs

map' :: (ViewL a as, Cons b bs) => (a -> b) -> as -> bs
map' f (viewL -> x :< xs) = f x <: map' f xs

convert :: (ViewL a as, EndR a as, Cons a bs, Nil bs) => as -> bs
convert = map id

convert' :: (ViewL a as, Cons a bs) => as -> bs
convert' = map' id

toList :: (ViewL a as, EndR a as) => as -> [a]
toList = convert

toList' :: (ViewL a as) => as -> [a]
toList' = convert'

fromList :: (Cons a as, Nil as) => [a] -> as
fromList = convert

fromList' :: (Cons a as) => [a] -> as
fromList' = convert'