[Haskell-cafe] Stack data structure

Serguey Zefirov sergueyz at gmail.com
Sat Dec 8 21:23:14 UTC 2018

I once improved Seq-based code by changing them to lists. The improvement
was about 10x in both memory and speed and all can be attributed to just
constant factors.

When I saw the same error again above I can't help myself.

сб, 8 дек. 2018 г. в 22:48, Ian Denhardt <ian at zenhack.net>:

> 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
> directly.
> You mention being unsatisfied with the existing libraries -- what was
> your use case?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20181209/b3a1fb3b/attachment.html>

More information about the Haskell-Cafe mailing list