GHC 8.4 DeriveFoldable will derive the definition of `null` rather than falling back on the default. This can produce dramatic performance improvements. I would like to do the same for `length`, but unfortunately, there's a problem. ### Why I want to derive length Consider the declaration data Foo a = Foo (Map "String" a) (Set a) A hand-written definition of `length` would look like this: length (Foo m set) = length m + length set This would produce an O(1) implementation of length, since Map and Set are annotated with their lengths. But the default implementation of length (which is what you get when you use `deriving Foldable`) would instead produce length foo = foldl' (\acc _ -> acc + 1) 0 foo which is O(n). Gross. ### What's the problem? There's no problem deriving length for Foo. The trouble comes when trying to derive length for a recursive type. data List a = Nil | Cons a (List a) The most obvious implementation to derive would be length Nil = 0 length (Cons _ xs) = 1 + length xs but this is not tail recursive! That's absolutely no good. What we *want* here is length = lengthPlus 0 lengthPlus acc Nil = acc lengthPlus !acc (Cons _ xs) = lengthPlus (acc + 1) xs We actually could arrange for that in this case, since we see that a `List` contains itself recursively. But what about *mutual* recursion? data List2 a = Nil | Cons a (List2' a) newtype List2' a = List2' (List2 a) Now the deriving mechanism can't see the recursion, and everything is horrible. ### The simplest solution It seems likely that the simplest solution would be what nobody really wants: add yet another method to Foldable: lengthPlus :: Int -> f a -> Int lengthPlus n xs = n + length xs We could derive efficient implementations of `lengthPlus` without any particular difficulty. ### Alternatives? I haven't thought of any plausible alternatives yet. Maybe someone else will. David