Thursday, March 25, 2010

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)
(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.)
(fun ()->
// Composition of list.
(fun a0 al->(fSucceed current (a0::al))))

// Interface funcion.
and search<'a,'b> (fGetEnum:'a->IEnumerator<'a> option)
(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) ->
(fun ()->[])
(fun a0 al->a::a0::al))

open System.Collections.Generic

// A simple tree node based on a HashSet.
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 ->
(fun (n:Node)->n.S=s)

// 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!"

No comments: