clarification

[Paul Rubin]

aleax at mac.com (Alex Martelli) writes:
> > turn indicates that both implementations actually work about same and
> > your "O(n squared)" argument is irrelevant.
> 
> It's indeed irrelevant when the behavior _isn't_ quadratic (as in the
> case of intersections) -- but unfortunately it _is_ needlessly quadratic
> in most interesting cases involving containers (catenation of sequences,
> union of sets, merging of dictionaries, merging of priority-queues,
> ...), because in those cases the intermediate temporary values tend to
> grow, as I tried to explain in more detail above.

Mostly directed to samwyse: Alex is correct here and I'd add that
Python and its libraries are written for an imperative, mutating
approach though there are some situations in which you can write in
functional style without a big efficiency hit.  In particular, the
quadratic behavior Alex points out is because of Python's hash-based
implementation of sets, so you can't make a new set that adds or
removes one element from the old set, without copying all the elements
around.

A more purist functional approach would probably implement sets with
some other data structure such as AVL trees, so you can make a new one
that adds or deletes some node in O(log n) time (it would share almost
all of its structure with the old one).  So instead of O(n) for the
hash-based mutating implementation or O(n**2) for the hash/copying
based functional implementation, you get O(n log n) for the functional
tree implementation.  Haskell's Data.Map module does something like
this.  There's a book "Purely Functional Data Structures" by Chris
Okasaki that shows how to implement dicts, priority queues, and
fancier objects in functional style based on similar principles.

If you want to try out functional programming in a lightweight
language (much easier to grok than Haskell) you might look at Hedgehog Lisp:

   http://hedgehog.oliotalo.fi/

It includes a functional dictionary implementation based on AVL trees
but with a Python dictionary-like API.