Wednesday, March 24, 2010

Search Using Continuations

Here's my first pass at a search using continuations. This is my first non-trivial implementation of continuations! It may not be the simplest way to do this, and it still returns a list in the opposite order from that which I want, but it's a start. I even made it generic. (Note: this version is only for acyclic graphs; this will be fixed in the next version.)

As always, presented without warranty or implied fitness. That and there may still be a bug or two.

p.s. The name "SeqTryPick" is an anachronism from experiments involving Seq; it will be changed in the next version.
open System
open System.Collections.Generic


[<System.Diagnostics.DebuggerDisplayAttribute("{S}")>]
type Bob (s:string) =

let h = new HashSet<Bob>()

member this.Add b =
h.Add(b) |> ignore
this

member this.H = h
member this.S = s


let rec internal SeqTryPick0<'a,'b> (fe:'a->IEnumerator<'a>)
(ft:'a->bool)
(e:IEnumerator<'a>)
(ff:unit->'a list)
(fs:'a list->'a list) =
match e.MoveNext() with
| false -> ff()
| _ ->
let c = e.Current
match ft c with
| true -> c::fs([])
| false ->
(SeqTryPick0
fe
ft
e
(fun ()->
SeqTryPick0
fe
ft
(fe c)
ff
(fun s->c::fs(s)))
fs)

and SeqTryPick<'a,'b> (fe:'a->IEnumerator<'a>)
(ft:'a->bool)
(a:'a) =
match ft a with
| true -> [a]
| false ->
SeqTryPick0
fe
ft
(fe a)
(fun ()->[])
(fun a0->a::a0)

let b =
(Bob "b").Add(
(Bob "b0").Add(
(Bob "b00").Add((Bob "b000")).Add((Bob "b001"))).Add(
(Bob "b01").Add((Bob "b010")).Add((Bob "b011")))).Add(
(Bob "b1").Add(
(Bob "b10").Add((Bob "b100")).Add((Bob "b101").Add((Bob "b1010")).Add((Bob "b1011")))).Add(
(Bob "b11").Add((Bob "b110")).Add((Bob "b111"))))

let x =
SeqTryPick
(fun (b:Bob)->(b.H.GetEnumerator():>IEnumerator<Bob>))
(fun (b:Bob)->b.S="b1011")
b

Console.ReadLine() |> ignore

No comments: