8 people like it.

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:12 years ago
Author:Tomas Petricek
Tags: monad , computation builder , workflow , non-determinism