Hey all, The connection between difference lists and accumulators is probably well known, but I only recently realized it myself and a quick Google search didn't find turn up any page where this was explicitly stated, so I thought this observation might be useful to some.
Every beginner Haskell student learns that this definition of "reverse" has O(n^2) complexity: reverse [] = [] reverse (x : xs) = reverse xs ++ [x] But what happens when we return a difference list instead, replacing [] with id, (++) with (.) and [x] with (x :)? reverse' [] = id reverse' (x : xs) = reverse xs . (x :) This definition of reverse' has type reverse' :: [a] -> [a] -> [a] Let's inline the second argument: reverse' [] acc = acc reverse' (x : xs) acc = reverse' xs (x : acc) And we have recovered the standard definition using an accumulator! I thought that was cute :) And may help understanding why difference lists are useful. Edsko _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
