Split for lists

List.hs

{-# LANGUAGE RankNTypes #-}

module List where

import Data.Monoid

newtype List a = Abstr {
  apply :: forall z . (Monoid z) => (a -> z) -> z
  }

nil :: List a
nil = Abstr (\f -> mempty)

cons :: a -> List a -> List a
cons x (Abstr app) = Abstr (\f -> mappend (f x) (app f))

append :: List a -> List a -> List a
append (Abstr xs) (Abstr ys) = Abstr (\ f -> xs f <> ys f)

newtype Split a = Split { outSplit :: Maybe (a, List a) }
  deriving Show

instance Monoid (Split a) where
  mempty = Split Nothing
  mappend (Split Nothing)        (Split nns)            = Split nns
  mappend (Split mms)            (Split Nothing)        = Split mms
  mappend (Split (Just (m, ms))) (Split (Just (n, ns))) =
    Split $ Just (m, append ms (cons n ns))

split :: List a -> Split a
split xs = apply xs $ \ a -> Split $ Just (a, nil)

head :: List a -> Maybe a
head = fmap fst . outSplit . split

tail :: List a -> Maybe (List a)
tail = fmap snd . outSplit . split

instance Show a => Show (List a) where
  show xs = show $ apply xs (:[])