[Haskell-beginners] Queues in Haskell

[Rahul Muttineni]

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.html>