List Concatenation, Associativity Matters 

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)