Difference List

import Prelude hiding (abs)
import Debug.Trace (trace)

data List a  = Empty | a ::: List a
infixr 5 :::

instance (Show a) => Show (List a) where
  show Empty = "Empty"
  show (h ::: t) = show h ++ " ::: " ++ show t


(.++.) :: List a -> List a -> List a
Empty .++. r  = r
(h ::: t) .++. r = trace (show ".++.") h ::: (t .++. r)

x = (9 ::: 8 ::: 7 ::: Empty) :: List Int
y = (6 ::: 5 ::: 4 ::: Empty) :: List Int
z = (3 ::: 2 ::: 1 ::: Empty) :: List Int

type DiffList a = List a -> List a

abs :: DiffList a -> List a
abs df = df Empty

rep :: List a -> DiffList a
rep = (.++.)

(^++^) :: DiffList a -> DiffList a -> DiffList a
(^++^) = (.)


main = do

  -- time: |x| + |y|
  print $ abs $ (rep x ^++^ rep y) ^++^ rep z

  trace (replicate 10 '-') (return ())

  -- time: |x| + |y|
  print $ abs $ rep x ^++^ (rep y ^++^ rep z)