Send Beginners mailing list submissions to
beginners@haskell.org
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/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: folds -- help! (Peter Verswyvelen)
2. Re: folds -- help! (Adrian Neumann)
3. Integer factorization (Sergey V. Mikhanov)
4. Re: folds -- help! (7stud)
----------------------------------------------------------------------
Message: 1
Date: Mon, 9 Mar 2009 18:24:14 +0100
From: Peter Verswyvelen <bugf...@gmail.com>
Subject: Re: [Haskell-beginners] folds -- help!
To: 7stud <bbxx789_0...@yahoo.com>
Cc: beginners@haskell.org
Message-ID:
<a88790d10903091024g624c382akabfdd55e49622...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
Maybe it helps to visualize it like this. Instead of computing the sum by
using a fold with (+), we just construct data:
data Expr = N Int
| Expr :+: Expr
deriving Show
ns :: [Expr]
ns = map N [1..3]
lf :: Expr
lf = foldl1 (:+:) ns
rf :: Expr
rf = foldr1 (:+:) ns
For simplicity Iused foldl1 and foldr1, which only work on non-empty lists.
(regarding the weird :+: well in Haskell, you can use operators for data
constructors when they start with a colon)
Run this with GHCi, and evaluate lf and rf. You should get
*Main> lf
(N 1 :+: N 2) :+: N 3
*Main> rf
N 1 :+: (N 2 :+: N 3)
So really, foldl "folds on the left", because the parentheses are on the
left side. Similarly for foldr.
Does this help?
On Mon, Mar 9, 2009 at 5:46 PM, 7stud <bbxx789_0...@yahoo.com> wrote:
> This is an example that shows how foldl and foldr work (from RWH p.93-94):
>
> foldl (+) 0 (1:2:3:[])
> == foldl (+) (0 + 1) (2:3:[])
> == foldl (+) ((0 + 1) + 2) (3:[])
> == foldl (+) (((0 + 1) + 2) + 3) []
> == (((0 + 1) + 2) + 3)
>
>
> foldr (+) 0 (1:2:3:[])
> == 1 + foldr (+) 0 (2:3:[])
> == 1 + (2 + foldr (+) 0 (3:[])
> == 1 + (2 + (3 + foldr (+) 0 []))
> == 1 + (2 + (3 + 0))
>
> The book says on p.94:
>
> -----
> The difference between foldl and foldr should be clear from looking at
> where
> the parentheses and the empty list elements show up. With foldl, the empty
> list element is on the left, and all the parentheses group to the left.
> With foldr, the zero value is on the right, and the parentheses group to
> the
> right.
> ----
>
> Huh? With foldl, the only empty list element I see is on the right.
>
> Initially, it looked to me ike they did the same thing, and that the only
> difference was the way they called step. I think "step" is a horrible,
> non-descriptive name, so I'm going to use "accFunc" instead:
>
> foldl calls: accFunc acc x
>
> foldr calls: accFunc x acc
>
> So it looks like you can define a function using either one and get the
> same result. Here is a test:
>
> --I am going to use odd for pfunc and [1, 2, 3] for xs:
>
> myFilter1 pfunc xs = foldl accFunc [] xs
> where accFunc acc x
> | pfunc x = acc ++ [x]
> | otherwise = acc
>
> myFilter2 pfunc xs = foldr accFunc [] xs
> where accFunc x acc
> | pfunc x = acc ++ [x]
> | otherwise = acc
>
>
> *Main> myFilter1 odd [1, 2, 3]
> [1,3]
> *Main> myFilter2 odd [1, 2, 3]
> [3,1]
>
> Hmmm. So there is a difference. foldr appears to grab elements from
> the end of the list. Therefore, to get the same result from the function
> that uses foldr, I did this:
>
>
> myFilter3 pfunc xs = foldr accFunc [] xs
> where accFunc x acc
> | pfunc x = x : acc
> | otherwise = acc
>
>
> *Main> myFilter3 odd [1, 2, 3]
> [1,3]
>
> But then RWH explains that you would never use foldl in practice because it
> thunks the result, which for large lists can overwhelm the maximum memory
> alloted for a thunk. But it appears to me the same thunk problem would
> occur with foldr. So why is foldr used in practice but not foldl?
>
>
>
>
>
> _______________________________________________
> Beginners mailing list
> Beginners@haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20090309/add4f687/attachment-0001.htm
------------------------------
Message: 2
Date: Mon, 9 Mar 2009 18:24:07 +0100
From: Adrian Neumann <aneum...@inf.fu-berlin.de>
Subject: Re: [Haskell-beginners] folds -- help!
To: beginners@haskell.org
Message-ID: <a334284e-950b-43ee-bd26-081c2bbc5...@inf.fu-berlin.de>
Content-Type: text/plain; charset="us-ascii"
Am 09.03.2009 um 17:46 schrieb 7stud:
> This is an example that shows how foldl and foldr work (from RWH p.
> 93-94):
>
> foldl (+) 0 (1:2:3:[])
> == foldl (+) (0 + 1) (2:3:[])
> == foldl (+) ((0 + 1) + 2) (3:[])
> == foldl (+) (((0 + 1) + 2) + 3) []
> == (((0 + 1) + 2) + 3)
>
>
> foldr (+) 0 (1:2:3:[])
> == 1 + foldr (+) 0 (2:3:[])
> == 1 + (2 + foldr (+) 0 (3:[])
> == 1 + (2 + (3 + foldr (+) 0 []))
> == 1 + (2 + (3 + 0))
>
> The book says on p.94:
>
> -----
> The difference between foldl and foldr should be clear from looking
> at where
> the parentheses and the empty list elements show up. With foldl,
> the empty
> list element is on the left, and all the parentheses group to the
> left.
> With foldr, the zero value is on the right, and the parentheses
> group to the
> right.
> ----
>
> Huh? With foldl, the only empty list element I see is on the right.
Have a look at foldl.com and foldr.com. With "empty list element"
they mean the 0.
> But then RWH explains that you would never use foldl in practice
> because it
> thunks the result, which for large lists can overwhelm the maximum
> memory
> alloted for a thunk. But it appears to me the same thunk problem
> would
> occur with foldr. So why is foldr used in practice but not foldl?
The problem is that foldr can lazyly produce a result. Try foldr (:)
[] [1..]. It works. Now try foldl (flip (:)) [] [1..]. It breaks.
However foldl is tail recursive, so the compiler can optimize the
recursion away. In some cases that is beneficial. Notice that there
is no difference between
foldr g a
foldl f a
(for appropriate g and f) if g and f are strict in both arguments.
Have a look at the "Foldl as foldr" wikipage. Also have a look at
this paper
> http://www.cs.nott.ac.uk/~gmh/fold.pdf
Regards,
Adrian
-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 194 bytes
Desc: Signierter Teil der Nachricht
Url :
http://www.haskell.org/pipermail/beginners/attachments/20090309/a5bb8304/PGP-0001.bin
------------------------------
Message: 3
Date: Tue, 10 Mar 2009 02:21:35 +0100
From: "Sergey V. Mikhanov" <ser...@mikhanov.com>
Subject: [Haskell-beginners] Integer factorization
To: beginners <beginners@haskell.org>
Message-ID:
<b38b3dd10903091821v1608ab1dta105465cea57d...@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
Hello,
I am solving a problem of finding the largest prime factor of
600851475143 (Project Euler is great for learning new language!), and
came with the following solution (it uses the most ineffective
approach to finding prime numbers, however is able to factor the above
number in fraction of second):
factors :: Integer -> [Integer]
factors n = doFactors n (eratosthenesFilter [1..n])
doFactors n primes
| null newPrimes = []
| otherwise =
let topPrime = head newPrimes in
if topPrime == n
then [topPrime]
else topPrime : (doFactors (n `quot` topPrime) primes)
where
newPrimes = snd $ break (\x -> (n `rem` x) == 0) primes
eratosthenesFilter :: [Integer] -> [Integer]
eratosthenesFilter [] = []
eratosthenesFilter (num : nums)
| num == 1 = eratosthenesFilter nums
| otherwise = num : (eratosthenesFilter $ doFilter num nums)
where
doFilter num nums = filter (\x -> x > num && (x `rem` num) /= 0) nums
What would you do different (including stylistic changes)? What are
the general comments about efficiency (not of the algorithm, but of
the implementation: for example, is it fine to use break at every
invocation of doFactors?) and elegance of the solution?
Thanks and regards,
Sergey
------------------------------
Message: 4
Date: Tue, 10 Mar 2009 07:59:03 +0000 (UTC)
From: 7stud <bbxx789_0...@yahoo.com>
Subject: [Haskell-beginners] Re: folds -- help!
To: beginners@haskell.org
Message-ID: <loom.20090310t003343-...@post.gmane.org>
Content-Type: text/plain; charset=utf-8
Daniel Fischer <daniel.is.fischer <at> web.de> writes:
>
> Am Montag, 9. März 2009 17:46 schrieb 7stud:
> > This is an example that shows how foldl and foldr work (from RWH p.93-94):
> >
> > foldl (+) 0 (1:2:3:[])
> > == foldl (+) (0 + 1) (2:3:[])
> > == foldl (+) ((0 + 1) + 2) (3:[])
> > == foldl (+) (((0 + 1) + 2) + 3) []
> > == (((0 + 1) + 2) + 3)
> >
> >
> > foldr (+) 0 (1:2:3:[])
> > == 1 + foldr (+) 0 (2:3:[])
> > == 1 + (2 + foldr (+) 0 (3:[])
> > == 1 + (2 + (3 + foldr (+) 0 []))
> > == 1 + (2 + (3 + 0))
> >
> > The book says on p.94:
> >
> > -----
> > The difference between foldl and foldr should be clear from looking at
> > where the parentheses and the empty list elements show up. With foldl, the
> > empty list element is on the left, and all the parentheses group to the
> > left. With foldr, the zero value is on the right, and the parentheses group
> > to the right.
> > ----
> >
> > Huh? With foldl, the only empty list element I see is on the right.
>
> What they meant was "the value that is the result in case the fold is applied
> to an empty list", in this case the 0, in the definition
>
So that's an error right? Or is that correct haskell terminology?
The book also says on p. 95:
-------------
Like foldl, foldr takes a function and a base case(what to do when the input
list is empty) as arguments.
-------------
That also does not seem correct. For example:
foldrSum xs = foldr accFunc 0 xs
where accFunc x acc = acc + x
*Main> foldrSum [1, 2, 3]
6
In that example, the first two arguments to foldr are the function accFunc
and 0. It does not seem accurate to say that "0 is what to do when the
input list is empty". What foldr does when the input list is empty
is return the value of the acc parameter variable:
foldr _ acc [] = acc
In my example, the value of the acc parameter is 6 "when the input list is
empty"--not the value 0, which is the argument to foldr.
> fold(l/r) f z xs = ...
>
> the 'z'.
>
> >
> > Initially, it looked to me ike they did the same thing, and that the only
> > difference was the way they called step. I think "step" is a horrible,
> > non-descriptive name, so I'm going to use "accFunc" instead:
> >
> > foldl calls: accFunc acc x
> >
> > foldr calls: accFunc x acc
> >
> > So it looks like you can define a function using either one and get the
> > same result.
>
> Note that in general the list elements and acc have different types, so only
> one of
> accFun acc x
> and
> accFun x acc
> typechecks.
>
I don't know how that comment is relevant. In my examples, acc and x have
different types:
*Main> :type []
[] :: [a]
*Main> :type 1
1 :: (Num t) => t
And both examples work fine.
> If the types are the same, in general accFun x acc /= accFun acc x,
>
Is that correct? Can you give some examples? Here is what I tried:
1)
accFunc1 acc x = x + acc
accFunc2 x acc = x + acc
*Main> let x = 1
*Main> let acc = 3
*Main> accFunc1 acc x
4
*Main> accFunc1 x acc
4
2)
accFunc3 acc x = x ++ acc
accFunc4 x acc = x ++ acc
*Main> let x = [1]
*Main> let acc = [2, 3]
*Main> accFunc3 acc x
[1,2,3]
*Main> accFunc4 x acc
[1,2,3]
> so foldr and foldl give different results, too.
>
I think the results produced by my example functions myFilter1 and myFilter2
demonstrate that, but the differing results are because of the way foldr and
foldl are defined.
> > Here is a test:
> >
> > --I am going to use odd for pfunc and [1, 2, 3] for xs:
> >
> > myFilter1 pfunc xs = foldl accFunc [] xs
> > where accFunc acc x
> >
> > | pfunc x = acc ++ [x]
> > | otherwise = acc
> >
> > myFilter2 pfunc xs = foldr accFunc [] xs
> > where accFunc x acc
> >
> > | pfunc x = acc ++ [x]
> > | otherwise = acc
> >
> > *Main> myFilter1 odd [1, 2, 3]
> > [1,3]
> > *Main> myFilter2 odd [1, 2, 3]
> > [3,1]
> >
> > Hmmm. So there is a difference. foldr appears to grab elements from
> > the end of the list. Therefore, to get the same result from the function
> > that uses foldr, I did this:
> >
> >
> > myFilter3 pfunc xs = foldr accFunc [] xs
> > where accFunc x acc
> >
> > | pfunc x = x : acc
> > | otherwise = acc
> >
> > *Main> myFilter3 odd [1, 2, 3]
> > [1,3]
> >
> > But then RWH explains that you would never use foldl in practice because it
> > thunks the result, which for large lists can overwhelm the maximum memory
> > alloted for a thunk. But it appears to me the same thunk problem would
> > occur with foldr. So why is foldr used in practice but not foldl?
> >
>
> Since with foldr, the parentheses are grouped to the right:
>
> if f can start delivering the result without looking at its second argument,
> you can start consuming the result before the fold has traversed the whole
> list.
>
Ok, that isn't clearly illustrated by the example in the book:
> > foldl (+) 0 (1:2:3:[])
> > == foldl (+) (0 + 1) (2:3:[])
> > == foldl (+) ((0 + 1) + 2) (3:[])
> > == foldl (+) (((0 + 1) + 2) + 3) []
> > == (((0 + 1) + 2) + 3)
> >
> >
> > foldr (+) 0 (1:2:3:[])
> > == 1 + foldr (+) 0 (2:3:[])
> > == 1 + (2 + foldr (+) 0 (3:[])
> > == 1 + (2 + (3 + foldr (+) 0 []))
> > == 1 + (2 + (3 + 0))
> >
In that example, it doesn't look like anything in foldr can be evaluated
until the whole fold has been completed.
> Common examples are things like
>
> concat = foldr (++) [],
> so
> concat [l1,l2,l3,l4,l5] = l1 ++ (foldr (++) [] [l2,l3,l4,l5])
> and the start (l1) can be used before further reducing the fold,
>
So does haskell store a thunk for everything to the right of l1?
You said that when using foldr you can start "consuming" the beginning of the
result before the whole result is reduced. I don't quite get that.
> and = foldr (&&) True
>
> [to evaluate the expression] and [True,False,..........]
> [haskell] needs only inspect the list until it encounters the first False
>(if any), otherwise it must of course traverse the whole list
>
> or = foldr (||) False
>
> foldr is useful if the combination function is lazy in its second argument.
>
Ok.
> foldl on the other hand can't deliver anything before the whole list is
> consumed. So since foldl builds thunks (except in some easy cases where the
> optimiser sees it should be strict), which would have to be evaluated at the
> end when they've become rather large, foldl isn't as useful and one uses the
> strict left fold, foldl'.
>
Thanks.
------------------------------
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 9, Issue 10
****************************************
