[Haskell-cafe] Stack data structure

[Serguey Zefirov]

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>