From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=AWL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by yquem.inria.fr (Postfix) with ESMTP id 261E9BBC1 for ; Sat, 26 Apr 2008 03:26:40 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AmQBAMIhEkjUnw6EfGdsb2JhbACCMY8qAQELBQIECRGaEA X-IronPort-AV: E=Sophos;i="4.25,709,1199660400"; d="scan'208";a="11468649" Received: from pih-relay05.plus.net ([212.159.14.132]) by mail1-smtp-roc.national.inria.fr with ESMTP; 26 Apr 2008 03:26:39 +0200 Received: from [80.229.56.224] (helo=beast.local) by pih-relay05.plus.net with esmtp (Exim) id 1JpZBW-0007PP-TJ for caml-list@yquem.inria.fr; Sat, 26 Apr 2008 02:26:39 +0100 From: Jon Harrop Organization: Flying Frog Consultancy Ltd. To: caml-list@yquem.inria.fr Subject: Tries are to sequences as ? is to trees Date: Sat, 26 Apr 2008 02:20:04 +0100 User-Agent: KMail/1.9.9 MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200804260220.04921.jon@ffconsultancy.com> X-Plusnet-Relay: 5d3a8a2ca43adeae9374a36a190e2f1c X-Spam: no; 0.00; hash:01 trie:98 frog:98 purely:02 data:02 tree:02 functional:02 seems:03 let:03 expressions:04 expressions:04 fold:06 sequences:07 sequences:07 tries:07 So tries let us associate sequences with values. What data structure lets us associate trees with values? I ask because I am interested in replacing hash consing of expressions with a purely functional equivalent so I need a way to map expressions onto expressions. The only idea I've come up with so far is to fold over the tree to make a sequence and use that as the key into a trie but it seems a bit naff... -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/products/?e