Version française
Home     About     Download     Resources     Contact us    
Browse thread
[Caml-list] HOFs, recursion, and being tail-rec...
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Jonathan Roewen <jonathan.roewen@g...>
Subject: [Caml-list] HOFs, recursion, and being tail-rec...
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 =
    let rec search visited position =
      if position = goal then true
      else List.exists (search (position::visited)) (positions
position edges (position::visited))
    in search [] start;;

Jonathan