[Haskell-cafe] Stack data structure
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
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