[Caml-list] HOFs, recursion, and being tail-rec...

[Jonathan Roewen <jonathan.roewen@gmail.com>]

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