> 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.