difference-lists.markdown

Difference Lists

Proposed BFPG lightning talk. 25 slides, 5 minutes, 12 seconds per slide. No problem!

September 2014

1

Motivation: we want to write something as clear as this, but this is O(n^2).

reverse :: [a] -> [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]

2

Get to O(n) using an accumulator, but this is less clear.

reverse :: [a] -> [a]
reverse xs = go xs []
  where
    go :: [a] -> [a] -> [a]
    go [] acc = acc
    go (x:xs) acc = go xs (x:acc)

3

Let's eliminate the accumulator parameter.

reverse :: [a] -> [a]
reverse xs = go xs []
  where
    go :: [a] -> [a] -> [a]
    go [] = \acc -> acc
    go (x:xs) = \acc -> go xs (x:acc)

4

And again.

reverse :: [a] -> [a]
reverse xs = go xs []
  where
    go :: [a] -> [a] -> [a]
    go [] = id
    go (x:xs) = go xs . (x:)

5

Now compare.

reverse :: [a] -> [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]

reverse :: [a] -> [a]
reverse xs = go xs []
  where
    go :: [a] -> [a] -> [a]
    go [] = id
    go (x:xs) = go xs . (x:)

6

Another example, also O(n^2).

Tree a = Leaf | Branch (Tree a) a (Tree a)

flatten :: Tree a -> [a]
flatten Leaf = []
flatten (Branch l x r) = flatten l ++ [x] ++ flatten r

7

Use an accumulator to get to O(n), but this is less clear.

Tree a = Leaf | Branch (Tree a) a (Tree a)

flatten :: Tree a -> [a]
flatten t = go t []
  where
    go :: Tree a -> [a] -> [a]
    go Leaf acc = acc
    go (Branch l x r) acc = go l (x : go r acc)

8

Rearrange.

Tree a = Leaf | Branch (Tree a) a (Tree a)

flatten :: Tree a -> [a]
flatten t = go t []
  where
    go :: Tree a -> [a] -> [a]
    go Leaf = id
    go (Branch l x r) = go l . (x:) . go r

9

And compare.

flatten :: Tree a -> [a]
flatten Leaf = []
flatten (Branch l x r) = flatten l ++ [x] ++ flatten r

flatten :: Tree a -> [a]
flatten t = go t []
  where
    go :: Tree a -> [a] -> [a]
    go Leaf = id
    go (Branch l x r) = go l . (x:) . go r

10

The common pattern.

type DList a = [a] -> [a]

-- empty difference list, O(1).
id :: DList a

-- difference list concatenation, amortised O(1) if used ephemerally.
(.) :: DList a -> DList a -> DList a

-- difference list to ordinary list, amortised O(1) if used ephemerally.
($[]) :: DList a -> [a]

-- singleton difference list, O(1).
(:) : a -> DList a

-- ordinary list to difference list, O(n).
(++) :: [a] -> DList a

11

Not magic.

type Queue a = DList a

put :: Queue a -> a -> Queue a
put q x = q . (x:)

-- No!
take :: Queue a -> Maybe (a, Queue a)
take q = case q [] of
  [] -> Nothing
  x:xs -> Just (x, (xs++))

12

And now for the twist.

reverse :: [a] -> [a]
reverse xs = go xs []
  where
    go :: [a] -> [a] -> [a]
    go [] = id
    go (x:xs) = go xs . (x:)

13

Abstract over the list-specific parts.

reverse :: (a -> [a] -> [a]) -> [a] -> [a] -> [a]
reverse f z xs = go xs z
  where
    go :: [a] -> [a] -> [a]
    go [] = id
    go (x:xs) = go xs . f x

14

Generalise the type. What do we get?

reverse :: (a -> b -> b) -> b -> [a] -> b
reverse f z xs = go xs z
  where
    go :: [a] -> b -> b
    go [] = id
    go (x:xs) = go xs . f x

15

A slight variation on the Prelude function.

foldl :: (a -> b -> b) -> b -> [a] -> b
foldl f z xs = go xs z
  where
    go :: [a] -> b -> b
    go [] = id
    go (x:xs) = go xs . f x

16

Just swap the function composition.

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z xs = go xs z
  where
    go :: [a] -> b -> b
    go [] = id
    go (x:xs) = f x . go xs

17

Monoids. They're everywhere.

reverse :: [a] -> [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]

reverse :: [a] -> [a]
reverse xs = go xs []
  where
    go :: [a] -> [a] -> [a]
    go [] = id
    go (x:xs) = go xs . (x:)

18

Monoids. They're everywhere.

instance Monoid [a] where
  mempty = []
  mappend = (++)

newtype Endo b = Endo { appEndo :: b -> b }

instance Monoid (Endo a) where
  mempty = Endo id
  Endo f `mappend` Endo g = Endo (f . g)

19

Rewrite inefficient reverse and flatten using Monoid and Reducer.

reverse :: [a] -> [a]
reverse [] = mempty
reverse (x:xs) = reverse xs <> unit x

flatten :: Tree a -> [a]
flatten Leaf = mempty
flatten (Branch l x r) = flatten l <> unit x <> flatten r

20

We get the efficient versions just by switching types (sans wrappers).

reverse :: [a] -> Endo [a]
reverse [] = mempty
reverse (x:xs) = reverse xs <> unit x

flatten :: Tree a -> Endo [a]
flatten Leaf = mempty
flatten (Branch l x r) = flatten l <> unit x <> flatten r

21

Let's write foldr using Monoid.

foldMap :: Monoid m => (a -> m) -> [a] -> m
foldMap f = mconcat . map f

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z xs = appEndo (foldMap (Endo . f) xs) z

22

We need the Dual of Endo to flip the function composition for foldl.

newtype Dual a = Dual { getDual :: a }

instance Monoid a => Monoid (Dual a) where
  mempty = Dual mempty
  Dual x `mappend` Dual y = Dual (y `mappend` x)

foldl :: (a -> b -> b) -> b -> [a] -> b
foldl f z xs = appEndo (getDual $ foldMap (Dual . Endo . f) xs) z

23

Tree has a foldMap, too!

foldMap :: Monoid m => (a -> m) -> Tree a -> m
foldMap f Leaf = mempty
foldMap f (Branch l x r) = foldMap f l <> f x <> foldMap f r

24

Put foldMap in a type class, get foldr and foldl for free.

class Foldable t where
  foldMap :: Monoid m => (a -> m) -> t a -> m

25

A better flatten.

flatten :: Foldable t => t a -> [a]
flatten = foldr (:) []