List Concatenation, Associativity Matters
12345678910111213141516171819202122232425262728
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)
Haskell
INFO