> If we implement list concatenation as a fold right, `foldr (++) []`, then I think the complexity is linear in the total number of elements of the list of lists, `lol`.

I promise to get to the microbenchmarks, but I wanted to go over why this isn't always an easy solution.

It's not always easy to use `foldr (++) []`

Consider the following elementary backtrack search:


module BackTrackSearch where

import Control.Applicative (Alternative, (<|>), pure, empty)

data BTree a = Branch (BTree a) (BTree a)
| Leaf a

findInBTree :: Alternative m => (a -> Bool) -> BTree a -> m a
findInBTree p (Branch left right) = findInBTree p left
<|> findInBTree p right
findInBTree p (Leaf a) = if p a
then pure a
else empty


We can swap `Alternative` functors to get different semantics.

If I just wanted to find one leaf, I could use `findInBTree :: (a -> Bool) -> BTree a -> Maybe a`

But if I wanted *prolog* type semantics, then I can pick between `findInBTree :: (a -> Bool) -> BTree a -> [a]` and `findInBTree :: (a -> Bool) -> BTree a -> DList a` and some other suitable functors. With the former we would get the \\(\mathcal{O}(n^2)\\) searching in the worst case and the latter we would get \\(\mathcal{O}(n)\\).

I could use `foldr` too, of course, but it would require a rewrite of `findInBTree`.