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. Usage of $ (Shishir Srivastava)
2. Re: Usage of $ (Mike Meyer)
3. Re: Haskell Bin Tree Cellular Automata (Sourabh)
4. Dynamic programming (memoization) w/ string keys. (Sourabh)
5. Re: Dynamic programming (memoization) w/ string keys.
(Stefan H?ck)
----------------------------------------------------------------------
Message: 1
Date: Sun, 7 Jun 2015 21:09:06 +0100
From: Shishir Srivastava <[email protected]>
To: beginners <[email protected]>
Subject: [Haskell-beginners] Usage of $
Message-ID:
<CALe5RTsj24OGyxwDAsQqBzRu4vmrXPmgFzFw4-Gpk-u0rMGK=g...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Hi,
Can someone please highlight how '$' is making the difference in the
execution of this function. With $ in place the function runs fine but
without $ for large input values the function overflows the stack.
--------
s mp 1 = 4
s mp n = ((s mp $ n-1)^2-2) `mod` mp
--------
I cannot understand the difference between
(s mp $ n-1) and (s mp n-1)
Thanks,
Shishir Srivastava
+44 (0) 750 127 5019
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150607/c349afe7/attachment-0001.html>
------------------------------
Message: 2
Date: Sun, 7 Jun 2015 15:21:26 -0500
From: Mike Meyer <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Usage of $
Message-ID:
<CAD=7U2BqOBd_mWg=yrwpswlluiicnvzbsmhjfhuodpgdibd...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
s mp $ n - 1 parses as s mp (n - 1)
s mp n - 1 parses as (s mp n) - 1
On Sun, Jun 7, 2015 at 3:09 PM, Shishir Srivastava <
[email protected]> wrote:
> Hi,
>
> Can someone please highlight how '$' is making the difference in the
> execution of this function. With $ in place the function runs fine but
> without $ for large input values the function overflows the stack.
>
> --------
> s mp 1 = 4
> s mp n = ((s mp $ n-1)^2-2) `mod` mp
> --------
>
> I cannot understand the difference between
> (s mp $ n-1) and (s mp n-1)
>
> Thanks,
> Shishir Srivastava
> +44 (0) 750 127 5019
>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150607/06128d27/attachment-0001.html>
------------------------------
Message: 3
Date: Sun, 7 Jun 2015 14:56:34 -0700
From: Sourabh <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] Haskell Bin Tree Cellular Automata
Message-ID:
<CAK0HM3=kzqrasxy4+ef7xj7kqg9bcgd6nxv3nm+4ecv-fdv...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Thanks for the wonderful post earlier on memoization Stefan.
I'm still trying to wrap my head around all the details. For example I'm
trying to figure out why (in the second version) the constant "is" scoped
within the function isn't garbage collected in between different calls to
the function. It seems like there is a lot going on behind the scenes, and
even though things look "semantically correct" to a beginner, they aren't
so straightforward. :) I think I will re-read your post a couple more time,
and hopefully get some more insight.
BTW, Sorry I didn't notice your update earlier. For some reason, I only get
certain emails from this list, and others disappear down a black hole. I
just happened to browse the archives and noticed this response.
Is there a web interface or such to browse and/or respond to threads? I
just usually mail "[email protected]" which is a painful way to do
this... (unless I'm doing it wrong).
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150607/26e05323/attachment-0001.html>
------------------------------
Message: 4
Date: Sun, 7 Jun 2015 15:15:16 -0700
From: Sourabh <[email protected]>
To: [email protected]
Subject: [Haskell-beginners] Dynamic programming (memoization) w/
string keys.
Message-ID:
<CAK0HM3kb0U=4OU6W3LnV8beasgs3mWX0QK--dvv=6pc5ye6...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Hello again! I'm hoping to get some more insight into another memoization
issue I'm facing.
This time, I was solving the following problem, which seems like a dynamic
programming problem.
https://www.hackerrank.com/challenges/game-of-kyles
I coded up a straightforward recurrence equation (without any memoization):
https://github.com/cbrghostrider/Hacking/blob/master/HackerRank/FunctionalProgramming/AdHoc/gameOfKyles_functionallyCorrect.hs
The function playGameOfKyles shows the recurrence. (playGameOfKyles ::
String -> Bool)
I tried to perform top-down dynamic programming, by caching the results in
a Data.Map, in between calls to the function. This is because the input is
a string.
Here is the new version:
https://github.com/cbrghostrider/Hacking/blob/master/HackerRank/FunctionalProgramming/AdHoc/gameOfKyles_mapMemoized.hs
Basically I am passing a map around, and returning one as well. (
playGameOfKyles :: CacheMap -> String -> (Bool, CacheMap))
The naive version (without memoization) is extremely slow of course, and
probably won't finish running until the sun cools down (so far, even one
test case of a string with length 74 hasn't finished running after many
minutes).
The memoized version is... improving something... and for example the
entire test case 2, which contains 100 test cases of size 50 to 100 each,
runs in about 8 minutes.
Is there something I can improve with the memoization, to make it faster?
Use something other than Data.Map? Or could the bottleneck be someplace
else in the algorithm? I know those are kinda broad questions, but I've run
out of ideas...
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150607/eb94ddd6/attachment-0001.html>
------------------------------
Message: 5
Date: Mon, 8 Jun 2015 05:45:47 +0200
From: Stefan H?ck <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] Dynamic programming (memoization) w/
string keys.
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
Do you have a dynamic programming solution which runs reasonably fast
in another language? Because this game of kyles looks like an example
from combinatoric game theory to me and as such it might be much more
efficient to solve it using nim-sums (if possible; I haven't given this
too much thought).
Also note that, since your strings only consist of X and I, you could
also use Integers and bit-operations instead of lists in your
algorithms. You'd still need a Map for memoization, but other operations
might be much faster.
Cheers
Stefan
On Sun, Jun 07, 2015 at 03:15:16PM -0700, Sourabh wrote:
> Hello again! I'm hoping to get some more insight into another memoization
> issue I'm facing.
>
> This time, I was solving the following problem, which seems like a dynamic
> programming problem.
> https://www.hackerrank.com/challenges/game-of-kyles
>
> I coded up a straightforward recurrence equation (without any memoization):
> https://github.com/cbrghostrider/Hacking/blob/master/HackerRank/FunctionalProgramming/AdHoc/gameOfKyles_functionallyCorrect.hs
>
>
> The function playGameOfKyles shows the recurrence. (playGameOfKyles ::
> String -> Bool)
>
> I tried to perform top-down dynamic programming, by caching the results in
> a Data.Map, in between calls to the function. This is because the input is
> a string.
>
> Here is the new version:
> https://github.com/cbrghostrider/Hacking/blob/master/HackerRank/FunctionalProgramming/AdHoc/gameOfKyles_mapMemoized.hs
>
> Basically I am passing a map around, and returning one as well. (
> playGameOfKyles :: CacheMap -> String -> (Bool, CacheMap))
>
> The naive version (without memoization) is extremely slow of course, and
> probably won't finish running until the sun cools down (so far, even one
> test case of a string with length 74 hasn't finished running after many
> minutes).
>
> The memoized version is... improving something... and for example the
> entire test case 2, which contains 100 test cases of size 50 to 100 each,
> runs in about 8 minutes.
>
> Is there something I can improve with the memoization, to make it faster?
> Use something other than Data.Map? Or could the bottleneck be someplace
> else in the algorithm? I know those are kinda broad questions, but I've run
> out of ideas...
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 84, Issue 10
*****************************************
