Send Beginners mailing list submissions to
beginners@haskell.org
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
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. Queues in Haskell (rohan sumant)
2. Re: Queues in Haskell (Rahul Muttineni)
3. Re: Queues in Haskell (rohan sumant)
----------------------------------------------------------------------
Message: 1
Date: Wed, 6 Apr 2016 11:03:20 +0530
From: rohan sumant <r.s.sum...@gmail.com>
To: beginners@haskell.org
Subject: [Haskell-beginners] Queues in Haskell
Message-ID:
<CAEHN=yYQR__6=sjkv29zbi6nvsztuemjxzrfx0tcxf23e11...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Hello,
According to http://rafal.io/posts/haskell-queues.html (++) cant be
used to implement queues in Haskell. The reason being that a push operation
takes linear time which is indeed very valid given that (++) operates in
linear time. However, since Haskell is lazy shouldn't (++) be implemented
only when the need occurs? In head ([1..] ++ [10])
I sincerely doubt the the [10] is concatenated before evaluating the head
of the list.
Please note that this question is focused upon the internals of Haskell. I
am aware that there are other approaches to implementing queues in Haskell.
Rohan Sumant
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20160406/83db5c81/attachment-0001.html>
------------------------------
Message: 2
Date: Wed, 6 Apr 2016 11:26:45 +0530
From: Rahul Muttineni <rahulm...@gmail.com>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <beginners@haskell.org>
Subject: Re: [Haskell-beginners] Queues in Haskell
Message-ID:
<canij+etrobh9b9sq4c57bm0oqgztb7xbwna12_dwj+tm22u...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Hi Rohan,
The definition of Prelude.head is
head :: [a] -> a
head (x:_) = x
head [] = undefined -- not exactly true but the details are irrelevant here
This is the same as
head :: [a] -> a
head xs = case xs of
(x : xs) -> x
[] -> undefined
(Remeber that a list type can be thought of as data [a] = x : xs | [],
hence (:) and [] are both data constructors.)
A case expression forces the evaluation of the scrutinee (xs in this case)
and since xs = ([1..] ++ [10]), the expression is forced to evaluate to
Weak Head Normal Form, which means it evaluates until it hits a data
constructor or function. So this requires us to lookup the definition of
(++) as well.
(++) [] ys = ys
(++) (x:xs) ys = x : xs ++ ys
This is the same as
(++) xs ys = case xs of
[] -> ys
x:xs -> x : (xs ++ ys)
Hence, evaluting ([1..] ++ [10]) will give 1 : ([2..] + [10]) which is in
WHNF, hence head ([1..] ++ [10]) = 1.
So yes, you are correct, adding the (++) won't add the list until the
evaluation "gets there", it will be stored as a thunk (suspended state). I
suppose you can effectively consider that as "adding in constant time". But
do note that it will consume quite a bit of memory over time to store the
appends and the singleton lists.
Yes, list concatenation is O(n), but pushing to the end of the queue is not
due to nature of laziness. This is precisely why it's hard to do running
time analysis in the context of laziness.
But due note that in your particular example, appending to [1..] is futile
since it's an infinite list, so that 10 will never actually get "seen" no
matter how far you go in the list.
Hope that helps!
Rahul Muttineni
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20160406/06ea99e7/attachment-0001.html>
------------------------------
Message: 3
Date: Wed, 6 Apr 2016 11:49:39 +0530
From: rohan sumant <r.s.sum...@gmail.com>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <beginners@haskell.org>
Subject: Re: [Haskell-beginners] Queues in Haskell
Message-ID:
<CAEHN=ybN=hUDmL2ppY+CZW5TotiNe4LoXbTnUuBv=fqb57r...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Thank you Rahul. This is very helpful.
Rohan Sumant
On Wed, Apr 6, 2016 at 11:26 AM, Rahul Muttineni <rahulm...@gmail.com>
wrote:
> Hi Rohan,
>
> The definition of Prelude.head is
>
> head :: [a] -> a
> head (x:_) = x
> head [] = undefined -- not exactly true but the details are irrelevant here
>
> This is the same as
>
> head :: [a] -> a
> head xs = case xs of
> (x : xs) -> x
> [] -> undefined
>
> (Remeber that a list type can be thought of as data [a] = x : xs | [],
> hence (:) and [] are both data constructors.)
>
> A case expression forces the evaluation of the scrutinee (xs in this case)
> and since xs = ([1..] ++ [10]), the expression is forced to evaluate to
> Weak Head Normal Form, which means it evaluates until it hits a data
> constructor or function. So this requires us to lookup the definition of
> (++) as well.
>
> (++) [] ys = ys
> (++) (x:xs) ys = x : xs ++ ys
>
> This is the same as
>
> (++) xs ys = case xs of
> [] -> ys
> x:xs -> x : (xs ++ ys)
>
> Hence, evaluting ([1..] ++ [10]) will give 1 : ([2..] + [10]) which is in
> WHNF, hence head ([1..] ++ [10]) = 1.
>
> So yes, you are correct, adding the (++) won't add the list until the
> evaluation "gets there", it will be stored as a thunk (suspended state). I
> suppose you can effectively consider that as "adding in constant time". But
> do note that it will consume quite a bit of memory over time to store the
> appends and the singleton lists.
>
> Yes, list concatenation is O(n), but pushing to the end of the queue is
> not due to nature of laziness. This is precisely why it's hard to do
> running time analysis in the context of laziness.
>
> But due note that in your particular example, appending to [1..] is futile
> since it's an infinite list, so that 10 will never actually get "seen" no
> matter how far you go in the list.
>
> Hope that helps!
> Rahul Muttineni
>
> _______________________________________________
> Beginners mailing list
> Beginners@haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20160406/454aba74/attachment-0001.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 94, Issue 3
****************************************
