I'm not sure I understand the type definition of the foldl function in haskell

Question

When I ask about the foldl type, what I see is this:

*Main> :t foldl
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b

In this case, what is t a?

I guess it means that the function is using a Foldable parametrized with a but I'm not even really sure about the syntax. For instance, why can't I substitute t a with Foldable a?

And, bonus question, if I had to define foldl myself, I would start with the base case

foldl f b [] = []

But if the base case takes a list, than it would not make much sense to accept a Foldable. What is the "empty Foldable" that I could use as the base case?

Answer 1

foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b

In this case, what is t a?

I guess it means that the function is using a Foldable parametrized with a [...]

That's exactly right. Note, however, that it is "a Foldable parameterized with a", and not "Foldable parametrized with a". As hegel5000's answer explains, when you write Foldable t to the left of =>, you are saying something about the type (constructor) t. Replacing t a with Foldable a would be a little like putting an adjective where a noun should be.

Moving on to your bonus question: foldl happens to be a method of the Foldable class. That means you are able to, when writing an instance of Foldable for a type, to supply an appropriate definition of foldl in which you can make use of the specific features of the type (e.g. that [] is a constructor of lists -- see also Daniel Wagner's answer).

If foldl weren't a method of Foldable, though, the only things you would be able to use to deal with the t a argument when implementing it would be the (other) methods of Foldable (foldr, foldMap, etc.), as you don't know anything else about t other than the fact that it has a Foldable instance. (Perhaps surprisingly, it is possible to implement foldl in such a way. Such an implementation is provided as a default for the foldl method in the Foldable class, so that you don't have to implement it yourself when writing an instance if you don't consider it necessary.)

Answer 2

I like the other answers, which discuss briefly the distinction between types and classes and so answer the first half of the question in that way. To keep this answer complete, I'll reiterate this very briefly; but see the other answers for longer explanations, since I want to spend the bulk of my time on the second half of the question.

So: Foldable is a typeclass (a collection of types). The t in the type of foldl rangers over types, not collections of types, and this explains why it can't be replaced by Foldable.

But I think this is also a very interesting question that the other answers didn't address:

If I had to define foldl myself, I would start with the base case

foldl f b [] = []

But if the base case takes a list, than it would not make much sense to accept a Foldable.

If you were to define foldl yourself, you would be creating an instance of Foldable for a specific type. Because in the instance you know which specific type is involved, you can write base cases for that type and need not know about any other instances of Foldable. In the Foldable instance for lists:

instance Foldable [] where
    foldl f b [] = b

...is perfectly well-typed, because we know t ~ []. On the other hand, in the instance for another type, we would of course have to use a different base case. For example:

import qualified Data.Set as S
instance Foldable S.Set where
    foldl f b s | S.null s = b

Again, this is okay inside the instance block because then we have t ~ S.Set. We can (and generally have to) write things that only work on S.Sets and would not work well with other Foldable instances.

Answer 3

Foldable is something called a "typeclass". Saying Foldable t => declares that t must implement the requirements of Foldable. However, t remains t, and doesn't get collapsed into a reference to a Foldable interface like it might in Java. That's why you can't just have Foldable a.

Definitely check out https://hackage.haskell.org/package/base-4.10.1.0/docs/Data-Foldable.html for an explanation of the requirements of Foldable and what methods that gets you.

Anyways, if you want to use one of Foldable's methods, then either use a known Foldable type like Set:

import qualified Data.Set as S
import Data.Foldable

sumSet :: (Num n) => S.Set n -> n
sumSet ns = foldl' (\ n acc -> n + acc ) 0 ns --make this pointfree if you want

Or you can take a type parameter and constrain it to be foldable:

sumFld :: (Num n, Foldable f) => f n -> n --different signature
sumFld ns = foldl' (\ n acc -> n + acc ) 0 ns --same implementation!

The following prints 6, twice:

main :: IO ()
main = print (sumSet $ S.fromList [1, 2, 3]) >> print (sumFld $ S.fromList [1, 2, 3])

Answer 4

In the context (Foldable t) => ... the t is the foldable type. An example of this could be the list type [].

Some more concrete types for foldl would be

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl :: (b -> a -> b) -> b -> Tree a -> b

Foldable t => ... can be read as t is required to be a Foldable. It is not the type constructor Foldable applied to the type t! Therefore Foldable t is not even a type and you can't ever use it on the right hand side of a =>.