3 ms·
Never thought lazyness could transform an o(1) operation into an o(n) as a side effect. I thought memory management was hard to reason about in pure functional
by bsaul 11y ago
Never thought lazyness could transform an o(1) operation into an o(n) as a side effect.
I thought memory management was hard to reason about in pure functional languages, but i never thought it could affect algorithmic complexity this badly.
- oilywater 11y agohttp://accidentallyquadratic.tumblr.com/ http://accidentallyquadratic.tumblr.com/ Great blog with examples where something linear turns quadratic! :D Most of the examples show that being this high at the abstraction level disallows you to properly evaluate the complexity of the code you are writing. Something that might look simple and linear can in fact have a quadratic behavior.
- jkarni 11y agoIf you're talking about the discussion of head and snoc at the beginning of the article, laziness just moved the costs around - head becomes O(n) (from O(1)), but snoc becomes O(1) (from O(n)), because you only pay for the snoc costs when inspecting the queue with 'head'.
- jeremyjh 11y agoIt can be stunning the first few times you see this sort of thing, but Haskell run time performance is not that hard to reason about it - is simply different from strict languages. As an experienced Haskeller I could see their point at the definition of the data structure and operations. In fact there is an entire data structure library built around this idea of O(1) snoc/appends, the dlist: https://hackage.haskell.org/package/dlist-0.7.1.2 https://hackage.haskell.org/package/dlist-0.7.1.2