From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <jonathan.roewen@gmail.com>
X-Original-To: caml-list@yquem.inria.fr
Delivered-To: caml-list@yquem.inria.fr
Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78])
	by yquem.inria.fr (Postfix) with ESMTP id 87BB0BB81
	for <caml-list@yquem.inria.fr>; Sun, 12 Feb 2006 23:08:17 +0100 (CET)
Received: from wproxy.gmail.com (wproxy.gmail.com [64.233.184.205])
	by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id k1CM8GEE026980
	for <caml-list@yquem.inria.fr>; Sun, 12 Feb 2006 23:08:17 +0100
Received: by wproxy.gmail.com with SMTP id i31so740775wra
        for <caml-list@yquem.inria.fr>; Sun, 12 Feb 2006 14:08:16 -0800 (PST)
DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws;
        s=beta; d=gmail.com;
        h=received:message-id:date:from:to:subject:mime-version:content-type:content-transfer-encoding:content-disposition;
        b=kK+MFFJ3DwqQN67W64EVG4XB9E46HUqy9b0pfNF25YWQPCzlEOSGj8+CTXl25H8TE/4j8+vOAhJpzmWxunmg5/8hC4x9ZLuUyF6R4by00QKR/PnSD/TMlhbmCTGW+/LjsDvAeYNa5rgdh7geaasxRKJJjJmtYyqwaQyrcSJVaY8=
Received: by 10.64.153.16 with SMTP id a16mr688139qbe;
        Sun, 12 Feb 2006 14:08:16 -0800 (PST)
Received: by 10.65.35.3 with HTTP; Sun, 12 Feb 2006 14:08:16 -0800 (PST)
Message-ID: <ad8cfe7e0602121408q15124406ta0e3a42a69c0abcc@mail.gmail.com>
Date: Mon, 13 Feb 2006 11:08:16 +1300
From: Jonathan Roewen <jonathan.roewen@gmail.com>
To: OCaml <caml-list@yquem.inria.fr>
Subject: [Caml-list] HOFs, recursion, and being tail-rec...
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline
X-Miltered: at nez-perce with ID 43EFB1D0.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)!
X-Spam: no; 0.00; caml-list:01 hofs:01 recursion:01 ocaml:01 optimise:01 val:01 omitting:01 nodes:01 val:01 dfs:01 bool:01 dfs:01 rec:01 edges:01 edges:01 
X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr
X-Spam-Level: 
X-Spam-Status: No, score=0.0 required=5.0 tests=RCVD_BY_IP autolearn=disabled 
	version=3.0.3

Hi,

I have a simple implementation of depth-first-search, and was
wondering if my approach would qualify as tail-rec (whether from the
code it is/isn't, and whether ocaml can optimise it so it is).

val positions : 'a -> ('a * 'a) list -> 'a list -> 'a list
(* I think that's right type: returns positions we can traverse to,
omitting nodes we've previously visited *)

(* val dfs: 'a -> 'a -> ('a * 'a) list -> bool *)
let dfs start goal edges =3D
    let rec search visited position =3D
      if position =3D goal then true
      else List.exists (search (position::visited)) (positions
position edges (position::visited))
    in search [] start;;

Jonathan