Type explanation of foldl?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Type explanation of foldl?

Lawrence Bottorff-2
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

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: 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: [hidden email]
Sent: 02 January 2021 17:52
To: [hidden email]
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

 


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners