Not necessarily a permutation; e.g.

    f :: [a] -> [a]
    f [] = []
    f (x:xs) = x: x: f xs

Yeah, Hickey was just wrong about this. For me, watching his talks goes like this:

Hickey: I value X, Y, Z

Me: Yeah man!

Hickey: We get great consequences A, B, C

Me: Ah yeah, I love programming like that. That's why I love Haskell!

Hickey: That's why Haskell is bad.

Me: err, what!?

> It tells you that the function must calculate a subset of a permutation of the input list

As tromp pointed out, "permutation" is technically incorrect. You mean something like "a list formed only from elements of the elements of the input list, and the particular arrangement is independent of the values of the input list"!

Not sure why you were downvoted though.

Rich’s point is the type signature actually tells you little about what the function does. You need the name, docs, tribal knowledge, your own understanding of the math… etc. to actually understand what it does. Type signature alone is a very incomplete understanding. But come on, do you think I learned how to write Haskell and don’t understand what a type signature’s value is? Give me a little credit.

Here is Rich’s work on the subject: https://youtu.be/YR5WdGrpoug?si=7C8EjQ7TVo2Ua8w7

I’m biased, but I think he’s got a point.