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

[Jacques Garrigue <garrigue@math.nagoya-u.ac.jp>]

From: Jonathan Roewen <jonathan.roewen@gmail.com>
> 
> 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).

By definition a depth-first-search cannot be tail-recursive: you need
a stack to implement the backtracking.
There is a degenerate case where all nodes are non-branching
(i.e. there is only one path), which in theory could be made
tail-recursive. But it would not be the case with your code, as
List.exists has no special case for the last element of the list (not
that it would make a lot of sense in general.)

> 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;;