[Haskell-beginners] Queues in Haskell

[rohan sumant]

Thank you Rahul. This is very helpful.




Rohan Sumant


On Wed, Apr 6, 2016 at 11:26 AM, Rahul Muttineni <rahulmutt at 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 at 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.html>