Improved Continutation Search

This one returns a list in the right order, and the example shows how to detect circularities. It's a little tricky; the tail recursion involves both a direct tail recursion and a continuation that results in a tail call. I had to run tests to convince myself it really wasn't eating up the stack, lol.

Next up: adding this to the semantic network code.

As always, presented without warranty or implied fitness. That and there may still be a bug or two or a simpler way of doing this.

The functions:

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) =
  // 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 []
      | 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))))
                 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) ->
          (search0 
            fGetEnum
            fTest
            newEnum
            (fun ()->[]) 
            (fun a0 al->a::a0::al))

Test:

open System.Collections.Generic


// A simple tree node based on a HashSet.
[<System.Diagnostics.DebuggerDisplayAttribute("{S}")>]
type Node (s:string) =
  
  let h = new HashSet<Node>()
  
  member this.Add n =
    h.Add(n) |> ignore
    this // Convenient chaining of adds.
  
  member this.H = h
  member this.S = s 


// This "safe" search uses a hash table 
// to detect circularity and returns 
// a None for the enumerator option.
let searchSafe =

  // Hash of visited nodes.
  let tested = new HashSet<Node>()
  
  // Returns child node enumerator iff
  // node has not already been considered.
  // Also marks unvisited nodes as visited.
  let fEnum (n:Node) =
    match tested.Add(n) with
    | false -> None
    | true -> Some(n.H.GetEnumerator():>IEnumerator<Node>)
  
  // Return a function.
  // (F# behavior means tested Hash will be cached.)
  (fun n s ->
    tested.Clear()  
    Searcher.search 
      fEnum
      (fun (n:Node)->n.S=s)
      n)


// Test it. 
// (Formatted for blog width.)

let n11 = (Node "n11").Add(Node "n110").Add(Node "n111")
let n10 = (Node "n10").Add(Node "n100").Add(Node "n101")
let n01 = (Node "n01").Add(Node "n010").Add(Node "n011")
let n00 = (Node "n00").Add(Node "n000").Add(Node "n001")
let n1  = (Node "n1").Add(n10).Add(n11)
let n0  = (Node "n0").Add(n00).Add(n01)
let n   = (Node "n").Add(n0).Add(n1) 


let l     = searchSafe n "n"
let l011  = searchSafe n "n011"
let l01x  = searchSafe n "n01x"

printfn "Your breakpoint here!"