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.6 required=5.0 tests=NO_REAL_NAME autolearn=disabled version=3.1.3 Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by yquem.inria.fr (Postfix) with ESMTP id 9070EBBAF for ; Mon, 10 Aug 2009 02:45:24 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: ArsBAC4Kf0rUGyoFkWdsb2JhbACaSwEBAQEJCwoHEwOxI4QYBYIn X-IronPort-AV: E=Sophos;i="4.43,350,1246831200"; d="scan'208";a="44504891" Received: from smtp5-g21.free.fr ([212.27.42.5]) by mail4-smtp-sop.national.inria.fr with ESMTP; 10 Aug 2009 02:45:23 +0200 Received: from smtp5-g21.free.fr (localhost [127.0.0.1]) by smtp5-g21.free.fr (Postfix) with ESMTP id E9024D480AF for ; Mon, 10 Aug 2009 02:45:18 +0200 (CEST) Received: from apc.happyleptic.org (happyleptic.org [82.67.194.89]) by smtp5-g21.free.fr (Postfix) with ESMTP id D4B9AD4804E for ; Mon, 10 Aug 2009 02:45:15 +0200 (CEST) Received: from yeeloong (unknown [82.229.213.209]) by apc.happyleptic.org (Postfix) with ESMTP id 84FE23355D for ; Sun, 9 Aug 2009 20:32:47 +0200 (CEST) Received: from rixed by yeeloong with local (Exim 4.69) (envelope-from ) id 1MaDCI-0005LO-7B for caml-list@yquem.inria.fr; Sun, 09 Aug 2009 20:32:46 +0200 Date: Sun, 9 Aug 2009 20:32:46 +0200 From: rixed@happyleptic.org To: caml-list@yquem.inria.fr Subject: Re: [Caml-list] ocamlgraph predecessors Message-ID: <20090809183246.GB25629@happyleptic.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.5.18 (2008-05-17) X-Spam: no; 0.00; node:01 functionnal:01 doubly:01 caml-list:01 arbitrary:02 purely:02 data:02 implemented:02 languages:03 overhead:04 overhead:04 problem:05 scan:06 linux:07 linked:07 > What you're asking is similar to the problem of finding the predecessor > of an arbitrary node in a singly-linked-list. You have no option but to > scan the whole list to find its predecessor. If you had a > doubly-linked-list, predecessor lookups would work easily, but that's a > different data structure, with much more overhead. Much more overhead, really ? So this is for performance reasons that all functionnal languages promote singly-linked lists, while for instance in Linux every list is implemented with a doubly linked list for purely ideological reasons ? :-)