[Haskell-cafe] Stack data structure

Ian Denhardt ian at zenhack.net
Sat Dec 8 19:46:25 UTC 2018

Quoting Serguey Zefirov (2018-12-08 09:33:35)
> The list as usually constructed (head and tail) is a stack.

This was my reaction as well; except for the over and under operations,
everything in the file would have as-good or better asymptotic
complexity as a simple list, and probably better constant factors too.
The docs for Data.Sequence even say:

> Note that sequences are typically slower than lists when using only
> operations for which they have the same big-(O) complexity: sequences
> make rather mediocre stacks!

It would also likely be more readable to use a list, in that every
Haskeller knows the list APIs, whereas Data.Sequence is less likely to
be familiar.

TBH, most cases where I would want a stack I wouldn't even bother with
the extra layer of abstraction over lists -- I'd probably use the

You mention being unsatisfied with the existing libraries -- what was
your use case?

More information about the Haskell-Cafe mailing list