Re: When functional languages can be accepted by industry?

From: Dennis (Gang) Chen (Dennis.G.Chen@motorola.com)
Date: Tue Apr 11 2000 - 02:24:47 MET DST

  • Next message: Gerd Stolpmann: "New version of the O'Caml link database"

    Jean-Christophe Filliatre wrote:

    > > I have not found a method to implement a set with an efficient
    > > element removal operation. To my knowledge, the implementation of
    > > set based on balanced tree is efficient for union, difference etc,
    > > but does not seem to be reasonably efficient for deleting an
    > > element. Besides, the tree-based implementation of set requires that
    > > the elements have an ordered type, it is not clear to me how to
    > > extend these techniques to build a set of unordered elements, say,
    > > set of sets.
    >
    > Ocaml sets come with a comparison function, so that you can build sets
    > of sets. See http://caml.inria.fr/pub/old_caml_site/ocaml/htmlman/manual053.html.
    >
    > If you can manage with sets of integers, you could consider Patricia
    > trees instead of balanced trees, as suggested in that article
    > http://www.cs.columbia.edu/~cdo/papers.html#ml98maps
    >
    > As I already wrote, Okasaki's book is marvelous, and gives many
    > different implementations of efficient datastructures, together with
    > tools to analyze theire complexity.

    Thanks for the suggestion, it sounds to be interesting to consider the ocaml
    comparison function on sets to build sets of sets.

    For the deletion operation, I've contacted Okasaki, who has also proposed
    balanced tree and Patricia tree, as well as the above paper and the following one:
    http://www-swiss.ai.mit.edu/~adams/BB/index.html

    The deletion operation described in these papers will rebuild a tree. Therefore,
    it does not seem to be comparably efficient with those implementations in
    imperative languages.

    Best regards.

    Gang Chen



    This archive was generated by hypermail 2b29 : Tue Apr 11 2000 - 19:55:12 MET DST