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: GCJ 2015 - Round 1A Problem - Haircut (Doug McIlroy)
2. Re: GCJ 2015 - Round 1A Problem - Haircut (Sourabh)
3. Re: GCJ 2015 - Round 1A Problem - Haircut
(Sumit Sahrawat, Maths & Computing, IIT (BHU))
4. Re: GCJ 2015 - Round 1A Problem - Haircut (Sourabh)
5. Re: dropWhile returning last dropped element (martin)
6. Re: StateT MyState IO a vs ReaderT (IORef MyState) IO a
(Grzegorz Milka)
7. Re: StateT MyState IO a vs ReaderT (IORef MyState) IO a
(Michael Snoyman)
----------------------------------------------------------------------
Message: 1
Date: Sat, 18 Apr 2015 10:29:11 -0400
From: Doug McIlroy <[email protected]>
To: [email protected]
Cc: [email protected]
Subject: Re: [Haskell-beginners] GCJ 2015 - Round 1A Problem - Haircut
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
> Can someone tell me how I could have avoided or fixed this?
The trouble manifested as stack overflow on solving
> https://code.google.com/codejam/contest/4224486/dashboard#s=p1
For efficiency, you'll probably need more cleverness in math than
in Haskell. You can predict an approximate start time for the Nth
customer's service from the average per-customer service time M,
where 1/M = sum 1/M_k.
Starting from that estimate, one can skip over almost the entire
service simulation.
Doug McIlroy
------------------------------
Message: 2
Date: Sat, 18 Apr 2015 08:34:42 -0700
From: Sourabh <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] GCJ 2015 - Round 1A Problem - Haircut
Message-ID:
<CAK0HM3k6OR907tt7iKjOEF7_M=kvsisrhvi6lz2kvs6ojdz...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Thanks Sumit, I changed my folds to a strict foldl'. I'll check how long it
runs now.
Doug, I think you are absolutely correct. Taking the harmonic mean probably
factored into the solution, in order to make it algorithmically feasible
for the large input! Lesson learnt, next time I'll probably think harder
about the problem than the code ;)
On Sat, Apr 18, 2015 at 7:29 AM, Doug McIlroy <[email protected]> wrote:
> > Can someone tell me how I could have avoided or fixed this?
>
> The trouble manifested as stack overflow on solving
>
> > https://code.google.com/codejam/contest/4224486/dashboard#s=p1
>
> For efficiency, you'll probably need more cleverness in math than
> in Haskell. You can predict an approximate start time for the Nth
> customer's service from the average per-customer service time M,
> where 1/M = sum 1/M_k.
> Starting from that estimate, one can skip over almost the entire
> service simulation.
>
> Doug McIlroy
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150418/0c5ba600/attachment-0001.html>
------------------------------
Message: 3
Date: Sat, 18 Apr 2015 21:21:49 +0530
From: "Sumit Sahrawat, Maths & Computing, IIT (BHU)"
<[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] GCJ 2015 - Round 1A Problem - Haircut
Message-ID:
<cajbew8pbf3+1ki+nqnpqn17ryukx5avkqdnyywzwk8j_xkt...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
The link doesn't work because the hyperlink doesn't include the apostrophe
at the end.
Also, I'm sorry for having written off foldr as being worthless, I didn't
think much about it when I replied.
Foldl is the bad one here, whereas foldr and foldl' are both good and
recommended options.
Foldr can cause stack overflow as it also creates unevaluated thunks, but
then you can use foldl' to get over that.
How did it go with strict foldl?
On 18 April 2015 at 21:04, Sourabh <[email protected]> wrote:
> Thanks Sumit, I changed my folds to a strict foldl'. I'll check how long
> it runs now.
>
> Doug, I think you are absolutely correct. Taking the harmonic mean
> probably factored into the solution, in order to make it algorithmically
> feasible for the large input! Lesson learnt, next time I'll probably think
> harder about the problem than the code ;)
>
> On Sat, Apr 18, 2015 at 7:29 AM, Doug McIlroy <[email protected]>
> wrote:
>
>> > Can someone tell me how I could have avoided or fixed this?
>>
>> The trouble manifested as stack overflow on solving
>>
>> > https://code.google.com/codejam/contest/4224486/dashboard#s=p1
>>
>> For efficiency, you'll probably need more cleverness in math than
>> in Haskell. You can predict an approximate start time for the Nth
>> customer's service from the average per-customer service time M,
>> where 1/M = sum 1/M_k.
>> Starting from that estimate, one can skip over almost the entire
>> service simulation.
>>
>> Doug McIlroy
>>
>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
>
--
Regards
Sumit Sahrawat
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150418/4b39a5a9/attachment-0001.html>
------------------------------
Message: 4
Date: Sat, 18 Apr 2015 08:58:23 -0700
From: Sourabh <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] GCJ 2015 - Round 1A Problem - Haircut
Message-ID:
<CAK0HM3=guiw2__ennqpr+sfgdy0bfkxgadrlb_3qqmx5_kq...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Strict foldl' solved the stack overflow issue, thanks for catching this
Sumit. However it is still taking way too long to compute, which means this
wasn't the intended solution for the problem.
I'll need to compute the average service time w/ the harmonic mean as Doug
suggested and then massage the code some more to get exactly what is asked.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150418/acedda25/attachment-0001.html>
------------------------------
Message: 5
Date: Sat, 18 Apr 2015 19:10:35 +0200
From: martin <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] dropWhile returning last dropped
element
Message-ID: <[email protected]>
Content-Type: text/plain; charset=windows-1252
Am 04/17/2015 um 11:18 PM schrieb Michael Orlitzky:
> Why do you want to avoid recursion? You could rewrite this to use list
> indices if you really wanted to, but anything
> you come up with is going to be essentially recursive, only less safe
Thanks for the code sample and pointing out that there may not be any last
dropped element.
I was wondering if there is to achive the desired behavior by plugging
together higher-order functions. This was the
only reason why I wanted to avoid explicit recursion.
------------------------------
Message: 6
Date: Sat, 18 Apr 2015 21:10:00 +0200
From: Grzegorz Milka <[email protected]>
To: [email protected]
Subject: Re: [Haskell-beginners] StateT MyState IO a vs ReaderT (IORef
MyState) IO a
Message-ID: <[email protected]>
Content-Type: text/plain; charset=utf-8
ReaderT (IORef MyState) IO a is introducing a global mutable state into
your IO actions. This style is discouraged, because you have less
guarantees about what can happen with your state. For example IORef is
not protected from multi-threaded access. If you try to use this state
in multiple threads you may run into bugs. StateT MyState IO a doesn't
have that problem. For a typical use-case, that is an action that: reads
state, performs action, modifies state, both are similar and neither
should be significantly more comfortable. I would recommend to use
StateT version unless you find that either it does not fit your model of
computation or that it is underperforming.
As for the performance it is hard to say. StateT allows the compiler to
reason more about your code, so it might optimize better. However that's
only one factor. You would need to test it to find out which one is better.
------------------------------
Message: 7
Date: Sat, 18 Apr 2015 19:12:22 +0000
From: Michael Snoyman <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] StateT MyState IO a vs ReaderT (IORef
MyState) IO a
Message-ID:
<CAKA2JgLPR-N6bqCxsDhbWVt9CgRnhqhCifXy7=8nusuzmbm...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
I actually released a library a week or two back that uses this trick:
https://github.com/fpco/monad-unlift#reference-transformers
The main advantage in my mind is that the state survives exceptions.
On Sat, Apr 18, 2015 at 12:09 PM Konstantin Saveljev <
[email protected]> wrote:
> Hello,
>
> I'm working on a project where I use StateT MyState IO a to keep track of
> the state. MyState is deeply nested and I use lens to help me more easily
> access and modify the state.
>
> Just about yesterday I found someone mentioning about using ReaderT (IORef
> MyState) IO a instead of StateT MyState IO a because we are already in IO.
>
> Can someone explain to me what are the benefits of these different
> approaches? What about Garbage Collection in both cases (if there is any
> difference at all)? Can you use lens package to access and update the state
> which is hidden behind IORef ?
>
> Thanks,
> Konstantin Saveljev
> _______________________________________________
> 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/20150418/cfc6bf26/attachment.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 82, Issue 23
*****************************************
