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: Learning about channels (Benjamin Edwards)
2. Re: Learning about channels (Daniel Fischer)
3. Re: Removing the biggest element from a list - maybe slow?
(Markus L?ll)
----------------------------------------------------------------------
Message: 1
Date: Tue, 25 May 2010 11:35:38 +0100
From: Benjamin Edwards <edwards.b...@googlemail.com>
Subject: Re: [Haskell-beginners] Learning about channels
To: beginners@haskell.org
Message-ID:
<aanlktik9h9cuvsbnnppahj74_6anbblcfqsm2njgm...@mail.gmail.com>
Content-Type: text/plain; charset="iso-8859-1"
Having read
this<http://haskell.org/ghc/docs/6.12.1/html/libraries/base-4.2.0.0/Control-Concurrent.html>page
a bit more I think I understand why the prgram was blocking, but if I
compile with -threaded surely the readChan function shouldn't prevent the
producer from producing?
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20100525/686ca391/attachment-0001.html
------------------------------
Message: 2
Date: Tue, 25 May 2010 13:31:51 +0200
From: Daniel Fischer <daniel.is.fisc...@web.de>
Subject: Re: [Haskell-beginners] Learning about channels
To: beginners@haskell.org
Message-ID: <201005251331.51498.daniel.is.fisc...@web.de>
Content-Type: text/plain; charset="utf-8"
On Tuesday 25 May 2010 12:35:38, Benjamin Edwards wrote:
> Having read
> this<http://haskell.org/ghc/docs/6.12.1/html/libraries/base-4.2.0.0/Cont
>rol-Concurrent.html>page a bit more I think I understand why the prgram
> was blocking, but if I compile with -threaded surely the readChan
> function shouldn't prevent the producer from producing?
I'm afraid that is not so, "The downside of having lightweight threads is
that only one can run at a time" and I compiled the original with -threaded
and got:
$ ./chanTest +RTS -N2
chanTest: thread blocked indefinitely in an MVar operation
------------------------------
Message: 3
Date: Tue, 25 May 2010 18:30:25 +0300
From: Markus L?ll <markus.l...@gmail.com>
Subject: Re: [Haskell-beginners] Removing the biggest element from a
list - maybe slow?
To: beginners@haskell.org
Message-ID:
<aanlktikoxgn1i0mhq2dh3ek-n54apw7gruygn7vco...@mail.gmail.com>
Content-Type: text/plain; charset=ISO-8859-1
Here is an ugly one:
remLargest2 [] = []
remLargest2 (li:st) = if something_bigger_in_tail then (li:result) else result
where ismax [] previous = ([], False)
ismax (current:rest) previous =
case (current_is_bigger_than_previous,
but_something_even_bigger_in_tail) of
(True, True) -> (current:newRest, True)
(False, True) -> (current:newRest, True)
(False, False) -> (current:newRest, False)
(True, False) -> ( newRest, True) -- current
is the biggest, lets leave it out
where f = ismax rest
current_is_bigger_than_previous = current > previous
(newRest, but_something_even_bigger_in_tail) =
if current_is_bigger_than_previous then f current
else f previous
(result, something_bigger_in_tail) = ismax st li
Besides the long names, could this be done somehow shorter?
The idea of it is to carry the maximum in 'previous' and compare it
with every element when recursing the list. When recursion reaches the
end, it starts to return, and on every step it tells the previous step
if there was something bigger down it's road of recursion or not. This
way every step knows if to drop its 'current' element -- this drop
happens only once.
So the steps it takes are defenitely 2n, because it rolls out, and
then has to return all the way -- even to get the first element
(because for it theres the question: "drop it or not?").
The order-not-retaining functions thus far are faster, taking only n steps.
The performance of Daniels remLargest depends on the order of elements
in the list: best case is if the list is grows like (=<), so there's
no use of an accumulator and concatenation: worst case is when the
list is composed of strictly descending lists -- then the time it
takes is 3n (n for traversing the list, n for reversing all sublists
and n for concatenating).
Cool problem ;-)
And we should do tests!
------------------------------
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 23, Issue 39
*****************************************
