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
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
Thank you Rahul. This is very helpful.
Rohan Sumant
On Wed, Apr 6, 2016 at 11:26 AM, 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
_______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
participants (2)
-
Rahul Muttineni -
rohan sumant