Non-deterministic computation builder

Computation builder for writing non-deterministic computations.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36:

/// Represents a non-deterministic computation that
/// returns some calculated value of 'T
type Nondet<'T> = ND of seq<'T>

/// Simple computation builder for non-deterministic
/// computations. You can use 'require' to specify
/// assertions and 'choose' to generate possibilities.
type NondetBuilder() =
  member x.Bind(ND v, f) = ND (Seq.collect (fun v -> let (ND s) = f v in s) v)
  member x.Return(v) = ND (seq { yield v })

/// Computation builder for non-deterministic computations
let nondet = NondetBuilder()

/// Specifies an assertion on non-deterministic computation
/// (the computation will only succeed if 'b' is true)
let require b = 
  ND (if not b then Seq.empty else seq { yield () })

/// Returns a nondeterministic computation that may 
/// return any of the specified values
let choose opts = ND opts

/// Find some solution of the non-deterministic computation
/// (may run for really long time or fail!)
let solve (ND c) = Seq.head c

// Sample non-deterministic computation. Find 'a' and 'b'
// from 1 to 50 such that 'a * b = 91'
nondet {
  let! a = choose [ 1 .. 50 ]
  let! b = choose [ 1 .. 50 ]
  let c = a * b
  do! require (c = 91) 
  return (a, b) }
|> solve

union case Nondet.ND: seq<'T> -> Nondet<'T>

Multiple items
val seq : sequence:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Core.Operators.seq

--------------------
type seq<'T> = System.Collections.Generic.IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>

Multiple items
type NondetBuilder =
  new : unit -> NondetBuilder
  member Bind : Nondet<'b> * f:('b -> Nondet<'c>) -> Nondet<'c>
  member Return : v:'a -> Nondet<'a>

Full name: Script.NondetBuilder

Simple computation builder for non-deterministic
computations. You can use 'require' to specify
assertions and 'choose' to generate possibilities.

--------------------
new : unit -> NondetBuilder

val x : NondetBuilder

member NondetBuilder.Bind : Nondet<'b> * f:('b -> Nondet<'c>) -> Nondet<'c>

Full name: Script.NondetBuilder.Bind

val v : seq<'b>

val f : ('b -> Nondet<'c>)

module Seq

from Microsoft.FSharp.Collections

val collect : mapping:('T -> #seq<'U>) -> source:seq<'T> -> seq<'U>

Full name: Microsoft.FSharp.Collections.Seq.collect

val v : 'b

val s : seq<'c>

member NondetBuilder.Return : v:'a -> Nondet<'a>

Full name: Script.NondetBuilder.Return

val v : 'a

val nondet : NondetBuilder

Full name: Script.nondet

Computation builder for non-deterministic computations

val require : b:bool -> Nondet<unit>

Full name: Script.require

Specifies an assertion on non-deterministic computation
(the computation will only succeed if 'b' is true)

val b : bool

val not : value:bool -> bool

Full name: Microsoft.FSharp.Core.Operators.not

val empty<'T> : seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.empty

val choose : opts:seq<'a> -> Nondet<'a>

Full name: Script.choose

Returns a nondeterministic computation that may
return any of the specified values

val opts : seq<'a>

val solve : Nondet<'a> -> 'a

Full name: Script.solve

Find some solution of the non-deterministic computation
(may run for really long time or fail!)

val c : seq<'a>

val head : source:seq<'T> -> 'T

Full name: Microsoft.FSharp.Collections.Seq.head

val a : int

val b : int

val c : int

Raw view Test code New version

More information

Link:	http://fssnip.net/98
Posted:	13 years ago
Author:	Tomas Petricek
Tags:	monad , computation builder , workflow , non-determinism