Dependent and independent variables in foldl and foldr

[Galaxy Being]

I have this 

myLength1 = foldl (\n _ -> n + 1) 0

and this 

myLength2 = foldr (\_ n -> n + 1) 0

I am guessing that foldl knows to assign the accumulator-seed argument to the dependent variable and the list argument's elements recursively to the independent variable; and with foldr to do the opposite. Is this a fair assumption? BTW, where can I get a look at the code for fold functions; or does the type definition answer my original question? Not really able to decipher it so well

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

LB

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

[Francesco Ariis]

Il 16 gennaio 2021 alle 16:10 Lawrence Bottorff ha scritto:

> I have this
>
> myLength1 = foldl (\n _ -> n + 1) 0
>
> and this
>
> myLength2 = foldr (\_ n -> n + 1) 0
>
> I am guessing that foldl knows to assign the accumulator-seed argument to
> the dependent variable and the list argument's elements recursively to the
> independent variable; and with foldr to do the opposite. Is this a fair
> assumption? BTW, where can I get a look at the code for fold functions; or
> does the type definition answer my original question? Not really able to
> decipher it so well
>
>  :t foldl
> foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b

foldl and foldr have slightly different signatures,

    λ> :t +d foldl
    foldl :: (b -> a -> b) -> b -> [a] -> b
    λ> :t +d foldr
    foldr :: (a -> b -> b) -> b -> [a] -> b

(Notice  `b -> a -> b`  vs.  `a -> b -> b`), hence the lambdas have a
different non-matched parameter.
Does this answer your question? —F
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

[Galaxy Being]

This is the definition of list foldr

foldr            :: (a -> b -> b) -> b -> [a] -> b
foldr _ z []     =  z
foldr f z (x:xs) =  f x (foldr f z xs)

In both foldl and foldr in the OP the n variable in lambda functions would seem to be for the accumulator, hence, I assume the n is considered the free variable? And then the wildcard in each lambda function refers to the bound variable, i.e., the list argument's elements to be folded. So I can recreate

foldr (+) 5 [1,2,3,4]

with

foldr (\x n -> x + n) 5 [1,2,3,4]

They both return 15. The first one results in

(+) 1 ((+) 2 ((+) 3 ((+) 4 5)))

but the second example I'm not sure how the (\x n -> x + n) is being applied in the form . . . f x (foldr f z xs) It obviously must be doing the same (+) 1 ((+) 2 ((+) 3 ((+) 4 5))) but how the function is being applied I don't understand.  Beta reduction doesn't get me very far

\x n -> x + n (5)([1,2,3,4])

\x 5 -> x + 5 ([1,2,3,4])

but obviously the enclosing lambda calc for foldr is doing something to create the (+) 1 ((+) 2 ((+) 3 ((+) 4 5))) form.

BTW, is the t a format in 

:type foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

something from category theory, i.e., for the list instance, t a is [a] What is the algebraic syntax where t a becomes [a] in the case of lists? It would be nice to understand some day exactly what :i Foldable is saying 

On Sat, Jan 16, 2021 at 4:36 PM Francesco Ariis <[hidden email]> wrote:

Il 16 gennaio 2021 alle 16:10 Lawrence Bottorff ha scritto:
> I have this
>
> myLength1 = foldl (\n _ -> n + 1) 0
>
> and this
>
> myLength2 = foldr (\_ n -> n + 1) 0
>
> I am guessing that foldl knows to assign the accumulator-seed argument to
> the dependent variable and the list argument's elements recursively to the
> independent variable; and with foldr to do the opposite. Is this a fair
> assumption? BTW, where can I get a look at the code for fold functions; or
> does the type definition answer my original question? Not really able to
> decipher it so well
>
>  :t foldl
> foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b

foldl and foldr have slightly different signatures,

    λ> :t +d foldl
    foldl :: (b -> a -> b) -> b -> [a] -> b
    λ> :t +d foldr
    foldr :: (a -> b -> b) -> b -> [a] -> b

(Notice  `b -> a -> b`  vs.  `a -> b -> b`), hence the lambdas have a
different non-matched parameter.
Does this answer your question? —F
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

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

[Francesco Ariis]

Il 16 gennaio 2021 alle 23:32 Lawrence Bottorff ha scritto:

> This is the definition of list foldr
>
> foldr            :: (a -> b -> b) -> b -> [a] -> b
> foldr _ z []     =  z
> foldr f z (x:xs) =  f x (foldr f z xs)
>
> In both foldl and foldr in the OP the n variable in lambda functions would
> seem to be for the accumulator, hence, I assume the n is considered the
> free variable? And then the wildcard in each lambda function refers to the
> bound variable, i.e., the list argument's elements to be folded.

The ‘_’ means «do not bind this parameter». Hence

    λ> (\x _ -> x + 1) 10 20
    11

> but the second example I'm not sure how the (\x n -> x + n) is being
> applied in the form . . . f x (foldr f z xs) It obviously must be doing the
> same (+) 1 ((+) 2 ((+) 3 ((+) 4 5))) but how the function is being applied
> I don't understand.

    foldr (+) 0 ([1,2,3])
    (+) 1 (foldr (+) 0 [2,3])
    (+) 1 ((+) 2 (foldr (+) 0 [3]))
    (+) 1 ((+) 2 ((+) 3 (foldr (+) 0 [])))
    (+) 1 ((+) 2 ((+) 3 0))
    (+) 1 ((+) 2 3)
    (+) 1 5
    6

> BTW, is the t a format in
>
> :type foldr
> foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
>
> something from category theory, i.e., for the list instance, t a is [a] What
> is the algebraic syntax where t a becomes [a] in the case of lists? It
> would be nice to understand some day exactly what :i Foldable is saying

What book are you studying on that does not talk about Typeclasses?
I feel you are making your life harder by not following a good
study program.
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners