Difference List
1234567891011121314151617181920212223242526272829303132333435363738394041
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)
Haskell
INFO