[Haskell-beginners] Relationship between graphs and queues?

[Christopher Howard]

I working through the practice problems in Davie's book (by myself) and 
there is one that is not quite clear to me:

"Construct an abstract data type for a queue. Attempt to supply an 
implementation (hidden from the user of the type) which allows access to 
the head of the queue and the construction of a new queue by adding 
elements to the end of an existing one. Both these interface functions 
should operate in time independent of the length of the queue. What 
implications does the this exercise suggest for search and 'updating' 
(by copying all unchanged nodes) a general graph?"

There are two parts to the problem here: 1) defining the data type and 
the interface functions, and 2) indicating the implications for general 
graphs. On the first part I'm a little unclear because I am not sure 
what he means by "allows access to the head of the queue"; i.e., does he 
mean to just get the value in the head of the queue, or pop the value 
off the head of the queue and return the new queue? If the former, a 
solution is not hard, but if the latter, then I am not sure how to solve 
this without somehow transversing the queue, which of course is not a 
time-independent activity. (Even in the implementation for a queue in 
the Data.Graph.Inductive.Internal.Queue, eventually a "reverse" call 
must be made.)

Anyway, maybe if someone could explain the relationship between this 
problem and graphs, I'll see the bigger picture and have a clearer view 
of the problem.

-- 
frigidcode.com
theologia.indicium.us