> So it isn't a well formed sentence to say depth first
> search cannot be tail-rec, it is easy to construct a
> depth first search in any FPL that is.
>
> However, no matter what you do, you will indeed need
> memory linear in the tree depth (unless it is 1-ary tree as
> pointed out).

Yes, but tail-rec would mean the function call trace does not use
memory linear in the tree depth, which would be a positive
optimisation. BTW: the memory linear to the tree depth is used in the
list passed to search, 'visited'.

I'm just wondering if using List.exists and HOFs prevents the compiler
from generating tail-rec code (I presume that List.exists is already
tail-rec). As it wouldn't be hard to make it tail-rec I'd imagine..

Jonathan