On Jan 17, 5:48 am, "Mark H." <mark.hoem...@gmail.com
> On Jan 16, 8:51 am, Rich Hickey <richhic...@gmail.com
> > On Jan 15, 10:44 pm, Jonathan T <jonnyt...@gmail.com
> > > Instead of destructuring-bind, what about pattern matching? I'm going
> > > to end up implementing this myself eventually anyway. It would be
> > > nice if there was a standard way of doing it in Clojure.
> > If you are talking about the aspect of pattern matching that acts as a
> > conditional based upon structure, I'm not a big fan.
> You may want to check out "Purely Functional Data Structures" -- see
> -- and look at the neat stuff people have done with these ideas in CL.
> There's a red-black tree example which is particularly elegant. (Any
> kind of dynamic tree rebalancing involves pattern matching on
> structure, for example, regardless of whether you have a syntax to
> support pattern matching or not.)
I've read Okasaki. You might want to check out PersistentTreeMap.java,
in the Clojure source, as it is an implementation of Okasaki's
persistent red-black tree in Java, and is what you get back from
sorted-map. Also PersistentQueue.java (not yet exposed) is based on
Okasaki's batched queues, but not amortized, as I have persistent
vectors and a constant time way to turn them into sequences.
I won't argue for the verbosity of Java vs. SML or Haskell, and I
readily acknowledge the beauty of the original formulation (although
the remove code, not in the book, isn't pretty in any language). But
it was an interesting exercise to move code from a pattern-matching
language to a non-pattern-matching language. This was my experience:
I started with pretty much a transliteration of the original,
replacing datatype tags with enums and matches with conditionals. The
result was none too fast. Also, I wanted to optimize the memory use,
as I knew many nodes would be non-branching leaves, and often maps
would be used as sets, i.e. without values. (Also, at that time I
didn't have persistent hash maps, and thought the rb tree would have
to serve all the purposes for which hash maps now serve). One could
imagine extending the Tree ADT (of the SML version) from E|T to E|T|
Leaf|EmptyT|EmptyLeaf or some such, but, without polymorphism, the
effect on the pattern matching is a multiplicative growth of
So, given I was in Rome (Java), I decided to do the idiomatic thing,
and pursued a hybrid strategy, maximizing the use of polymorphism,
(which I know is optimized in Java), and minimizing the use of
conditionals. (The remove code is still pretty much conditionals, as
the logic is too impenetrable to safely recast :)
The result is the hierarchy of Nodes, implementing the memory usage
strategy, and, for add/lookup at least, mostly polymorphic method
dispatch. The result is more efficient and _much_ faster. The logic is
distributed - each node type takes care of itself to some degree. It
was, IMO, easier to add the with/without value/branches variations
this way to maintain a conditional approach, with or without patterns.
The result might seem a bit verbose, but comparing it to the Okasaki
book example is not apples-to-apples. You would have to have an SML/
Haskell version that:
Was a map, not just a set.
Had the remove code.
Had optional values, and used no storage for no value.
Didn't store branches for leaves.
Allowed the option of comparing elements _or_ supplying a comparator.
I'm sure all of this is elegantly possible, but it won't be the pretty
little thing in the book anymore.
Here are some of my takeaways:
- Adding types can have a multiplicative, rather than an additive,
effect on pattern matches.
- Without a pattern-match optimizer, naive mechanical translation of
patterns to if-else constructs can produce slow code.
The latter is particularly important. I'm sure SML/Haskell/Erlang
optimize pattern matching, and while it may be easy to mimic the
superficial behavior with a macro, the optimizers are likely non-
> > the conditional part, and I would make any destructuring-bind for
> > Clojure work with all of the data structures, not just lists, i.e.
> > vectors and maps and metadata.
> METABANG-BIND is a good example of such a package in CL. I
> imagine it could be adapted without too much trouble.
Given that Clojure has vector and map literals, I would hope to use
them to match their counterparts, so it will differ in at least that