Send Beginners mailing list submissions to
[email protected]
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
[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. foldM efficiency (Matthew Moppett)
2. Re: Help with improving a program (Marcelo Lacerda)
3. Simple Continuation question (martin)
----------------------------------------------------------------------
Message: 1
Date: Fri, 11 Jul 2014 19:05:18 +0700
From: Matthew Moppett <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: [Haskell-beginners] foldM efficiency
Message-ID:
<CAMLEjZAn3nVEnig7VvhSzURVJNhhbLS6Br_3Z8qNhbZB1S=5...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
I recently wrote the following code to solve a Project Euler problem:
coin :: Int -> Int -> [Int]
coin coinvalue stash = [stash, stash + coinvalue .. 200]
main = print . length . foldl (>>=) [0] $ map coin [200, 100, 50, 20, 10, 5, 2]
The program (correctly) works out how many ways there are to make up ?2
from ?2, ?1, 50p, 20p, 10p, 5p, and 1p coins. Looking at the code, I
realised that (foldl (>>=) [0] . map) does a very similar job to foldM from
Control.Monad. So I tried rewriting the code as
follows:
import Control.Monad
coin :: Int -> Int -> [Int]
coin stash coinvalue = [stash, stash + coinvalue .. 200]
main = print . length $ foldM coin 0 [200, 100, 50, 20, 10, 5, 2]
This works, but it's about four times slower: it takes about 0.065 seconds
on my computer, while the first version takes about 0.017 seconds. To put
it another way, if I define foldM as follows:
foldM :: Monad m => (a -> b -> m a) -> a -> [b] -> m a
foldM f x = foldl (>>=) (return x) . map (flip f)
... and use that definition instead of the standard Control.Monad version,
the code runs about four times faster. Here's the Control.Monad version
(copied from Hackage):
foldM :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m a
foldM _ a [] = return a
foldM f a (x:xs) = f a x >>= \fax -> foldM f fax xs
Why is my version so much faster here? And under what circumstances (if
any) could I expect the Control.Monad foldM to give better performance than
my version?
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140711/a964bb8c/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: FoldM.hs
Type: text/x-haskell
Size: 241 bytes
Desc: not available
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140711/a964bb8c/attachment-0003.hs>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: problem31a.hs
Type: text/x-haskell
Size: 169 bytes
Desc: not available
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140711/a964bb8c/attachment-0004.hs>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: problem31b.hs
Type: text/x-haskell
Size: 175 bytes
Desc: not available
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140711/a964bb8c/attachment-0005.hs>
------------------------------
Message: 2
Date: Fri, 11 Jul 2014 21:13:27 -0300
From: Marcelo Lacerda <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] Help with improving a program
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
Thanks for all the replies, I really liked Florian's answer, even
though, if I were to adopt that style, I think the haskell gods would
shunne me for using mixing too much pure and impure code.
On 07/10/2014 10:24 AM, Florian Gillard wrote:
> I don't know if this is any good but here is my attempt to solve this.
>
> I used comprehensions.
>
> It seems to be working fine with the test files :)
>
>
>
> On Thu, Jul 10, 2014 at 11:35 AM, Frerich Raabe <[email protected]> wrote:
>
>> On 2014-07-10 11:24, Francesco Ariis wrote:
>>
>>> On Wed, Jul 09, 2014 at 11:02:14PM -0300, Marcelo Lacerda wrote:
>>>
>>>> Hi I'm just starting with haskell and want some help with it.
>>>>
>>>> I tried to solve the Store Credit[1] problem from google code jam just
>>>> to practice, the result was a slow code[2] that I find hard to read.
>>>>
>>>> Can you guys give me some directions on how to improve it?
>>>>
>>>> [1] - https://code.google.com/codejam/contest/351101/dashboard#s=p0
>>>> [2] - http://pastebin.com/jNGxGP5H
>>>>
>>>>
>>> Don't know about efficiency, but I never liked (!!). Maybe computing all
>>> pairs+positions in advance using |zip| would be a little better?
>>>
>>
>> Yeah, that's what I went for as well. I'm attaching my solution for
>> comparison to this mail.
>>
>>
>> --
>> Frerich Raabe - [email protected]
>> www.froglogic.com - Multi-Platform GUI Testing
>>
>> _______________________________________________
>> Beginners mailing list
>> [email protected]
>> http://www.haskell.org/mailman/listinfo/beginners
>>
>>
>
>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
------------------------------
Message: 3
Date: Sat, 12 Jul 2014 12:24:58 +0200
From: martin <[email protected]>
To: [email protected]
Subject: [Haskell-beginners] Simple Continuation question
Message-ID: <[email protected]>
Content-Type: text/plain; charset=ISO-8859-15
Hello all,
I just started trying to understand Continuations, but my very first exercise
already left me mystified.
import Control.Monad.Cont
resultIs :: Int -> Cont String String
resultIs i = ContT $ f
where
f :: (String -> a) -> a
f k = k ("result=" ++ show i)
If resultIs returns a Cont String String, then f should be
(String->String)->String, but that doesn't compile. Why is
that so?
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 73, Issue 8
****************************************
