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

_______________________________________________

Libraries mailing list

[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries