[Haskell-beginners] Type explanation of foldl?

[David James]

Hello – in

myFoldl :: (t -> a -> t) -> t -> [a] -> t

the t and the a are type variables. There are no “classes” at all. Since you didn’t name the type variables, Haskell has provided default names for you “at random”, and it’s in some ways a little unfortunate that it’s named one of them t.

You could (probably should) provide your own declaration, e.g. renaming t to b:

myFoldl :: (b -> a -> b) -> b -> [a] -> b

This represents exactly the same thing, and says that myFoldl will work for any two types a and b. It takes three params:
                (b -> a -> b)         A function of values of type b and type a
that returns a value of type b.                                    (The accumulation function)
                b                             A value of type b                                                              (The initial accumulated value)
                [a]                          A list of values of type a                                                 (This list to accumulate over)
and returns
                b                             A value of type b                                                              (The final accumulated value)

The prelude function:

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

is then almost identical. This time, though, instead of being restricted to a list of values (of type a) to fold over, it can fold over any type of foldable collection of values (of type a). t represents the type of the foldable collection, and Foldable t => is a constraint that says the function will only work for a type t that is an instance of the class Foldable.

[BTW: does a type declaration like this one reflect in any way the recursion going on? I didn’t really understand the question, but you can often deduce what a function does, and how it might be implemented, from its type signature.]

I don’t know how you’re going about learning Haskell, but following a tutorial (such as http://learnyouahaskell.com/) might be helpful, and I think explains all of the above step by step.

Regards, David.

From: Lawrence Bottorff<mailto:borgauf at gmail.com>
Sent: 02 January 2021 17:52
To: The Haskell-Beginners Mailing List - Discussion of primarily beginner-level topics related to Haskell<mailto:beginners at haskell.org>
Subject: [Haskell-beginners] Type explanation of foldl?

I've got this

myFoldl f init [] = init
myFoldl f init (x:xs) = myFoldl f newInit xs
  where newInit = f init x

which when evaluated gives this for its type

> :t myFoldl
myFoldl :: (t -> a -> t) -> t -> [a] -> t

. . . not totally sure what that all means, e.g., how the t as a generic class is behaving is very mysterious. Obviously, the final result is of type t . . . and that must relate to the incoming argument init, correct? (BTW, does a type declaration like this one reflect in any way the recursion going on?)  But then with Prelude foldl I'm really clueless

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

I'm guessing the t is again a generic type of the Foldable class, but then. . .  Can someone walk me through this?

LB

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20210103/278cd30a/attachment.html>