Document early termination of `all` and friends.

[milesfrain]

Do all, any, and, or terminate early (short-circuit) when encountering the first overpowering value (e.g. all can return false as soon it sees the first false).
If so, should we add a note to the docs?
If not, should we also add a note, explain why, and then point to other options to achieve this behavior?

[JordanMartinez]

I believe Harry and I had a conversation about this once. I'll write what I remember from that conversation.

They do not short-circuit. If you look at the Haskell definition for Foldable, you will see that the elem function is included in the definition of Foldable whereas PureScript's elem is a derived function. So, why is PureScript different?

Haskell supports "default implementations" of type class members. Looking at the Haskell source code, we can see per the "MINIMAL" pragma that a data type only needs to implement either foldMap or foldr to have an instance for Foldable. All other functions defined in that class can be derived using one of those two functions. However, such defaults may not be as performant (i.e. short-circuit). Fortunately, these defaults can be overridden. So, if elem should short-circuit on a data type like List, someone writing an instance for List could stop the recursion as soon as the first element is found.

PureScript does not support default implementations. The closest thing we have are functions like foldrDefault that can be used within the definition of a type class member. Note: these need to be "eta-expanded" (i.e. include the arguments on the left hand side) to prevent a stack overflow issue.:

data List a = Cons a (List a) | Nil

instance foldableList :: Foldable List where
  foldMap aToMonoid list = -- normal definition
  foldr acc init list = foldrDefault (flip acc) init list

If PureScript did support default implementations, we could include things like all, any, or, etc. for free (as we already do via derived functions), but also get short-circuiting versions for types that can support that.

[hdgarrood]

Yep 👍 There’s another factor in this, which is that it’s difficult to short circuit here because our versions of any, all, and, and or use a HeytingAlgebra constraint rather than a concrete Boolean type, which means that we can’t know whether we’ve seen a true or a false in order to short circuit unless we add an Eq constraint so that we can check for equality with either tt or ff (the generalised versions of true and false).