Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

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: 2006-02-13 (02:47)
From: Jonathan Roewen <jonathan.roewen@g...>
Subject: Re: [Caml-list] HOFs, recursion, and being tail-rec...
> 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..