Jim Apple wrote:

Why isn't the type of group :: Eq a => [a] -> [(a,[a])]

You mean that the actual type Eq a => [a] -> [[a]] does not give the information that each element of the result is non-empty. Perhaps this word "non-empty" could be inserted in the specification:

The group function takes a list and returns a list of *non-empty* lists such that the concatenation of the result is equal to the argument. [...]

best regards, J.W.

On 2008-08-26, Jim Apple wrote:

Why isn't the type of group

Eq a => [a] -> [(a,[a])]

That matches more exactly what group does, and it's easy to see that functions like

nubOrd = map fst . group . sort

are clearly safe, whereas

map head . group . sort

is not.

I think the big thing is that while this is safer type, it's also much harder to use. Knowing I have a non-empty list is certainly useful information that can be reasoned about at the type level, but if I can't pass them easily to normal list functions, it's much less useful. Perhaps judicious use of typeclasses would make this easier, but I don't think those were in the original either. In any case the design space for a standard prelude that had the normal list type and a non-empty list type united in a sequence class is rather large, particularly if it's an open class that new sequence-like data types are expected to be an instance of. -- Aaron Denney -><-