Send Beginners mailing list submissions to
beginners@haskell.org
To subscribe or unsubscribe via the World Wide Web, visit
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
beginners-requ...@haskell.org
You can reach the person managing the list at
beginners-ow...@haskell.org
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: Dependent and independent variables in foldl and foldr
(Lawrence Bottorff)
2. Re: Dependent and independent variables in foldl and foldr
(Francesco Ariis)
----------------------------------------------------------------------
Message: 1
Date: Sat, 16 Jan 2021 23:32:33 -0600
From: Lawrence Bottorff <borg...@gmail.com>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <beginners@haskell.org>
Subject: Re: [Haskell-beginners] Dependent and independent variables
in foldl and foldr
Message-ID:
<CAFAhFSWPmaRKWShUE_5Higgpv=kd6GxaW=D+3cV+PGL7=g7...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
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 <fa...@ariis.it> 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
> Beginners@haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20210116/36953770/attachment-0001.html>
------------------------------
Message: 2
Date: Sun, 17 Jan 2021 06:55:20 +0100
From: Francesco Ariis <fa...@ariis.it>
To: beginners@haskell.org
Subject: Re: [Haskell-beginners] Dependent and independent variables
in foldl and foldr
Message-ID: <20210117055520.GA27441@extensa>
Content-Type: text/plain; charset=utf-8
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.
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 150, Issue 8
*****************************************
