Correction

The astute reader will have noticed an inefficiency in the previous search function. The continuation function is doing more work than it needs to do. Below is a better version. I marked the changes with four slashes (“////”). I hope this version is bug free; the astute reader is invited to point out any bugs or remaining inefficiencies.

As always, presented “as-is” and without warranty or implied fitness; use at your own risk.

module Searcher

open System.Collections.Generic


// This is the actual tail-recursive function.
// Note: not tail-recursive unless tail-call is turned on.
let rec internal search0<'a,'b> (fGetEnum:'a->IEnumerator<'a> option)
                                (fTest:'a->bool)
                                (enum:IEnumerator<'a>)
                                (fFail:unit->'a list) 
                                //(fSucceed:'a->'a list->'a list) =
                                (fSucceed:'a list->'a list) =
  // This function is a direct tail recursion 
  // for each item in a sequence.
  match enum.MoveNext() with
  | false -> fFail()
  | _ -> 
      let current = enum.Current
      // Test for goal node.
      match fTest current with
      ////| true -> fSucceed current []
      | true -> fSucceed [current]
      | false -> 
          // Test for child enumeration.
          // (Can user short circuit here.
          match (fGetEnum current) with 
          | None -> fFail()
          | Some(newEnum) ->
              // Direct tail recursion plus
              // a continuation tail recursion.
              // (Formatted for ease of reading.)
              (search0 
                fGetEnum
                fTest
                enum 
                (fun ()->
                   search0 
                     fGetEnum
                     fTest
                     newEnum 
                     fFail 
                     // Composition of list.
                     ////(fun a0 al->(fSucceed current (a0::al))))
                     (fun a0 ->(fSucceed (current::a0))))
                 fSucceed)

// Interface funcion.             
and search<'a,'b> (fGetEnum:'a->IEnumerator<'a> option)
                  (fTest:'a->bool)
                  (a:'a) =
  // Test on the root node here makes
  // search0 more straightforward.
  match fTest a with 
  | true -> [a]
  | false ->
      // Test for child enumeration.
      // (Can user short circuit here.
      match (fGetEnum a) with 
      | None -> []
      | Some(newEnum) ->  
          //// Added match and cons.
          match (search0 
                   fGetEnum
                   fTest
                   newEnum
                   (fun ()->[]) 
                   ////(fun a0 al->a::a0::al))            
                   (fun a0->a0)) with
          | [] -> []
          | l -> a::l