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. Using a monadic operation in a list comprehension.
(Derek McLoughlin)
2. what space leak could happen here? (Dimitri DeFigueiredo)
3. Re: Using a monadic operation in a list comprehension.
(Kim-Ee Yeoh)
4. Re: what space leak could happen here? (Chadda? Fouch?)
5. Re: what space leak could happen here? (Dimitri DeFigueiredo)
6. Re: Using a monadic operation in a list comprehension.
(Derek McLoughlin)
7. Re: what space leak could happen here? (Phil Xiaojun Hu)
----------------------------------------------------------------------
Message: 1
Date: Sun, 21 Sep 2014 15:02:55 +0100
From: Derek McLoughlin <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: [Haskell-beginners] Using a monadic operation in a list
comprehension.
Message-ID:
<CAAw9fmkLRmuiDRKpTd8ng2u=cxczduadrcvm90ras2jzet-...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
Hi,
I'm trying to get Graham Hutton's "Programming with Effects" article
(http://www.cs.nott.ac.uk/~gmh/monads) working with Data.Tree instead
of the Tree he provides.
My code is here:
https://gist.github.com/derekmcloughlin/95ab690e0c07c5a7221e
The compiler is complaining about the use of
lab <- mlabel c
in the list comprehension:
Couldn't match expected type ?[Tree (a, Int)]?
with actual type ?ST (Tree (a, Int))?
This makes sense, but is there any way to execute the monad operation
"mlabel" within the list comprehension? I've tried the
MonadComprehensions extension but still get an error.
Derek.
------------------------------
Message: 2
Date: Sun, 21 Sep 2014 11:05:43 -0600
From: Dimitri DeFigueiredo <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: [Haskell-beginners] what space leak could happen here?
Message-ID: <[email protected]>
Content-Type: text/plain; charset="windows-1252"; Format="flowed"
Hi All,
I was looking at the definition of intersperse on
http://hackage.haskell.org/package/base-4.7.0.1/docs/src/Data-List.html#intersperse
And found this
-- | The 'intersperse' function takes an element and a list and
-- \`intersperses\' that element between the elements of the list.
-- For example,
--
-- > intersperse ',' "abcde" == "a,b,c,d,e"
intersperse :: a -> [a] -> [a]
intersperse _ [] = []
intersperse sep (x:xs) = x : prependToAll sep xs
-- Not exported:
-- We want to make every element in the 'intersperse'd list available
-- as soon as possible to avoid space leaks. Experiments suggested that
-- a separate top-level helper is more efficient than a local worker.
prependToAll :: a -> [a] -> [a]
prependToAll _ [] = []
prependToAll sep (x:xs) = sep : x : prependToAll sep xs
I don't understand why we need to "make every element in the
'intersperse'd list available as soon as possible to avoid space leaks."
Could somebody shed some light on what could cause a space leak here? In
particular, would this simpler version cause problems?
intersperse :: a -> [a] -> [a]
intersperse _ [] = []
intersperse _ [x] = [x]
intersperse a (x: xs@(y:ys)) = x : a : intersperse a xs
Thanks,
Dimitri
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140921/2f4d7959/attachment-0001.html>
------------------------------
Message: 3
Date: Mon, 22 Sep 2014 01:38:36 +0700
From: Kim-Ee Yeoh <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Using a monadic operation in a list
comprehension.
Message-ID:
<CAPY+ZdRiYOkBtKfZ5E0g6Sr=iskps5rw10xj-si2bzw+fkv...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
On Sun, Sep 21, 2014 at 9:02 PM, Derek McLoughlin <
[email protected]> wrote:
> I'm trying to get Graham Hutton's "Programming with Effects" article
> (http://www.cs.nott.ac.uk/~gmh/monads) working with Data.Tree instead
> of the Tree he provides.
>
Hi Derek,
This is a lovely problem that's inspired a bunch of interesting papers
recently.
Here's a stab at the compilation error you're facing:
http://www.atamo.com/blog/how-to-solve-a-tricky-monad-problem-1/
Enjoy :)
-- Kim-Ee
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140922/5b88c000/attachment-0001.html>
------------------------------
Message: 4
Date: Sun, 21 Sep 2014 21:20:04 +0200
From: Chadda? Fouch? <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] what space leak could happen here?
Message-ID:
<CANfjZRZ-=iFhvEE79ah+HjmxNZO9NB53o=ezggz3io61ubp...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
On Sun, Sep 21, 2014 at 7:05 PM, Dimitri DeFigueiredo <
[email protected]> wrote:
> I don't understand why we need to "make every element in the
> 'intersperse'd list available as soon as possible to avoid space leaks."
> Could somebody shed some light on what could cause a space leak here? In
> particular, would this simpler version cause problems?
>
This is delicate but basically your version needs to force the second
element of the list (to check if it's []) before it produce the first
element of the result while the base version doesn't, check with "take 1 .
intersperse ',' $ 'a' : undefined".
The leak can occur when you only need the first element of the result to
start producing but the second one is expensive to produce and store, the
base version avoid the problem by being maximally lazy.
--
Jeda?
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140921/9a2117a2/attachment-0001.html>
------------------------------
Message: 5
Date: Sun, 21 Sep 2014 14:12:04 -0600
From: Dimitri DeFigueiredo <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] what space leak could happen here?
Message-ID: <[email protected]>
Content-Type: text/plain; charset="windows-1252"; Format="flowed"
Thanks!
I don't quite understand the last sentence, though. So, it is a leak
just because it needs to evaluate an element that may not be required? I
thought a space leak implied we would be changing the "Big O" asymptotic
order of space usage. How would the extra evaluation would change that?
Thanks again,
Dimitri
On 21/09/14 13:20, Chadda? Fouch? wrote:
> On Sun, Sep 21, 2014 at 7:05 PM, Dimitri DeFigueiredo
> <[email protected] <mailto:[email protected]>> wrote:
>
> I don't understand why we need to "make every element in the
> 'intersperse'd list available as soon as possible to avoid space
> leaks." Could somebody shed some light on what could cause a space
> leak here? In particular, would this simpler version cause problems?
>
>
> This is delicate but basically your version needs to force the second
> element of the list (to check if it's []) before it produce the first
> element of the result while the base version doesn't, check with "take
> 1 . intersperse ',' $ 'a' : undefined".
>
> The leak can occur when you only need the first element of the result
> to start producing but the second one is expensive to produce and
> store, the base version avoid the problem by being maximally lazy.
> --
> Jeda?
>
>
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140921/5e52412e/attachment-0001.html>
------------------------------
Message: 6
Date: Sun, 21 Sep 2014 21:55:50 +0100
From: Derek McLoughlin <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Using a monadic operation in a list
comprehension.
Message-ID:
<CAAw9fmkeJHo_pMvMjLpEhN0vY1kaEZ6M_qsL0mS=xwnyx+v...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
Thanks very much for your clear explanation! Worked perfectly. You're
right about the ST - I got very confused at the start with
Control.Monad.ST. I'll be removing Graham's ST in favour of the
'normal' State monad.
On 21 September 2014 19:38, Kim-Ee Yeoh <[email protected]> wrote:
>
> On Sun, Sep 21, 2014 at 9:02 PM, Derek McLoughlin
> <[email protected]> wrote:
>>
>> I'm trying to get Graham Hutton's "Programming with Effects" article
>> (http://www.cs.nott.ac.uk/~gmh/monads) working with Data.Tree instead
>> of the Tree he provides.
>
>
> Hi Derek,
>
> This is a lovely problem that's inspired a bunch of interesting papers
> recently.
>
> Here's a stab at the compilation error you're facing:
>
> http://www.atamo.com/blog/how-to-solve-a-tricky-monad-problem-1/
>
> Enjoy :)
>
> -- Kim-Ee
>
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://www.haskell.org/mailman/listinfo/beginners
>
------------------------------
Message: 7
Date: Mon, 22 Sep 2014 12:10:45 +0800
From: Phil Xiaojun Hu <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] what space leak could happen here?
Message-ID: <[email protected]>
Content-Type: text/plain; charset="us-ascii"
On Sun, Sep 21, 2014 at 02:12:04PM -0600, Dimitri DeFigueiredo wrote:
> Thanks!
>
> I don't quite understand the last sentence, though. So, it is a leak just
> because it needs to evaluate an element that may not be required? I thought
> a space leak implied we would be changing the "Big O" asymptotic order of
> space usage. How would the extra evaluation would change that?
Think of a network socket as the source of your list, and the first
character is all you need. If you need to evaluate the second character
to get the first, you could be stuck on the network socket for some
time waiting for the second one to come.
And I think the reason it would break some "Big O"s is that most
complexity analysis in Haskell are amortized bounds and it uses the fact
that Haskell is lazy and won't evaluate something until we actually need
it.
--
Phil Xiaojun Hu
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 819 bytes
Desc: not available
URL:
<http://www.haskell.org/pipermail/beginners/attachments/20140922/00bc6e38/attachment.sig>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 75, Issue 17
*****************************************
