Send Beginners mailing list submissions to
[email protected]
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
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: parallel map/filter (Marcin Mrotek)
2. Re: Haskell Bin Tree Cellular Automata. (Stefan H?ck)
3. Re: Haskell Bin Tree Cellular Automata. (Kim-Ee Yeoh)
4. Re: Haskell Bin Tree Cellular Automata. (Frerich Raabe)
----------------------------------------------------------------------
Message: 1
Date: Fri, 5 Jun 2015 20:38:48 +0200
From: Marcin Mrotek <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] parallel map/filter
Message-ID:
<CAJcfPznpXR4vDaGDXrq8h2H2ytt4K7hiok=cb_s6z7_w9we...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
My first guesses would be that:
a) Your program is slowed down because lines from the file is read one line
by one, i.e. there's lazy IO at work. Have you tried your code on a list
that's loaded in the memory as a whole at once?
b) The cost of dereferencing the next link in a list overwhelms the cost of
computing one answer. Have you tried using a tree instead?
Best regards,
Marcin Mrotek
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150605/f8b218c0/attachment-0001.html>
------------------------------
Message: 2
Date: Sat, 6 Jun 2015 06:01:59 +0200
From: Stefan H?ck <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Haskell Bin Tree Cellular Automata.
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
On Thu, Jun 04, 2015 at 04:31:07PM -0700, Sourabh wrote:
> Wow, it runs in 0.44 seconds now. This is incredible! Can you explain what
> just happened here?
Here is a try at an explanation. To reduce the complexity involved with
creating automata trees, lets define a very simple function:
module Memo () where
calc :: Integer -> Integer
calc = (1+)
And now we build a list of integers in a similar fashion to your
tree-generating function:
ints :: Integer -> [Integer]
ints i = i : [calc (ints i !! (n-1)) | n <- [1..]]
Store this in a file, fire up ghci, load the file and enter
take 500 $ ints 1
You can literally watch things slowing down as new values are being
printed. As you said correctly, at every call to `ints` the
whole list is recalculated up to the value you need. Since
`ints` is called with a new parameter at every iteration, Haskell
has no way of memoizing anything.
Let's add some memoization:
ints2 :: Integer -> [Integer]
ints2 i = let is = i : [calc (is !! (n-1)) | n <- [1..]]
in is
Again, load this in ghci and run
take 500 $ ints2 1
Marvel at the difference. `is` has type [Integer] and as such is
a constant. Already calculated values of `is` will therefore be
memoized, so the whole list is only created once. Still, this is
far from ideal. Enter
ints2 1 !! 50000
and wait some more. The problem is that the algorithm still
has O(n^2) complexity, n being the length of the list you need to
create. At every iteration, `is !! (n-1)` accesses the (n-1)th
element of `is` which takes itself n-1 operations. So, to
generate a list of ten elements, the algorithm runs
is !! 1
is !! 2
.
.
.
is !! 9
to a total of 45 operations. For small list sizes, this makes hardly
a difference, but for a list size of 50'000, this means already
1'249'975'000 operations doing nothing but traversing a list.
Let's improve this further:
ints3 :: Integer -> [Integer]
ints3 i = i : ints3 (calc i)
Here we use Haskell's lazyness to great effect. This function
says: our list of ints is the initial value, prepended to the list
of ints starting at the next value.
take 500 $ ints3 1
and
ints3 1 !! 50000
are both very fast. Every item in the list is calculated exactly once
and the algorithm runs in linear time.
Now you will only run into trouble at very
large indices (above 10'000'000 on my computer). `ints3` is not
tail recursive and will produce a stack overflow for very
large lists.
When you look at the source code of `iterate`
you will see that it is just a generalized version of `ints3`
taking an additional higher order function as input.
I hope this sheds some light
Stefan
------------------------------
Message: 3
Date: Sat, 6 Jun 2015 12:18:28 +0700
From: Kim-Ee Yeoh <[email protected]>
To: [email protected], The Haskell-Beginners Mailing List -
Discussion of primarily beginner-level topics related to Haskell
<[email protected]>
Subject: Re: [Haskell-beginners] Haskell Bin Tree Cellular Automata.
Message-ID:
<capy+zdr7bftubjzjeyqudpprw4mkpq1-+qf+fd6+3_af1z_...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
On Sat, Jun 6, 2015 at 11:01 AM, Stefan H?ck <[email protected]> wrote:
> I hope this sheds some light
Marvellous! Thank you for taking the time to break it down usefully into
memoization and unnecessary list traversal.
-- Kim-Ee
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150606/3c29a8b2/attachment-0001.html>
------------------------------
Message: 4
Date: Sat, 06 Jun 2015 11:36:25 +0200
From: Frerich Raabe <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Haskell Bin Tree Cellular Automata.
Message-ID: <[email protected]>
Content-Type: text/plain; charset=UTF-8; format=flowed
On 2015-06-06 06:01, Stefan H?ck wrote:
> On Thu, Jun 04, 2015 at 04:31:07PM -0700, Sourabh wrote:
>> Wow, it runs in 0.44 seconds now. This is incredible! Can you explain what
>> just happened here?
>
> Here is a try at an explanation.
Thank you a lot for taking the time to walk through it! One thing got
me thinking though:
> And now we build a list of integers in a similar fashion to your
> tree-generating function:
>
> ints :: Integer -> [Integer]
> ints i = i : [calc (ints i !! (n-1)) | n <- [1..]]
>
> Store this in a file, fire up ghci, load the file and enter
>
> take 500 $ ints 1
[..]
> Let's add some memoization:
>
> ints2 :: Integer -> [Integer]
> ints2 i = let is = i : [calc (is !! (n-1)) | n <- [1..]]
> in is
>
> Again, load this in ghci and run
>
> take 500 $ ints2 1
>
> Marvel at the difference.
This is what's known as 'Tying the Knot' (e.g. on
https://wiki.haskell.org/Tying_the_Knot), right? I wonder - would it
be possible (and plausible) for a compiler to perform this rewriting
automatically, such that any occurrence of code like
f x = e
where 'e' involves a call to 'f x' gets replaced with
f x = let z = e in z
and all occurences of 'f x' in 'e' get replaced with 'z'?
--
Frerich Raabe - [email protected]
www.froglogic.com - Multi-Platform GUI Testing
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 84, Issue 7
****************************************
