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 (.++.) :: (Show a) => List a -> List a -> List a Empty .++. r = r (h ::: t) .++. r = trace (show h) h ::: (t .++. r) x = (9 ::: 8 ::: 7 ::: Empty) :: List Int y = (6 ::: 5 ::: 4 ::: Empty) :: List Int z = (3 ::: 2 ::: 1 ::: Empty) :: List Int main = do -- time: 2 |x| + |y| print $ (x .++. y) .++. z trace (take 10 $ repeat '-') (return ()) -- time: |x| + |y| print $ x .++. (y .++. z)