weighted-search-0.1.0.1: A weighted nondeterministic search monad

Description

This is a nondeterminism monad which allows you to give computations weights, such that the lowest-weight computations will be returned first. This allows you to search infinite spaces productively, by guarding recursive calls with weights. Example:

``` import qualified Control.Monad.WeightedSearch as W
import Control.Applicative

-- All naturals, weighted by the size of the number
naturals :: W.T Integer Integer
naturals = go 0
where
go n = pure n <|> W.weight 1 (go \$! n+1)

-- All finite lists, weighted by the length of the list
finiteLists :: W.T Integer a -> W.T Integer a
finiteLists = pure [] <|> W.weight 1 ((:) <\$> w <*> finiteLists w)

-- A list of all finite lists of naturals
finiteListsOfNaturals = W.toList (finiteLists naturals)
-- [ [], [0], [0,0], [1], [0,0,0], [0,1], [1,0], [2], [0,0,0,0], [0,0,1], ... ]
```

Weights must be strictly positive for this to be well-defined.

Synopsis

# Documentation

data T w a Source

Weighted nondeterminstic computations over the weight `w`.

Instances

 Weight w => Monad (T w) Functor (T w) Weight w => MonadPlus (T w) Weight w => Applicative (T w) Foldable (T w) Traversable (T w) Weight w => Alternative (T w)

class Ord w => Weight w whereSource

The class of positive weights. We need to know how to subtract. Weights must be strictly positive.

Methods

difference :: w -> w -> wSource

Instances

 Weight Double Weight Float Weight Int Weight Integer Integral a => Weight (Ratio a)

weight :: w -> T w a -> T w aSource

Take a positive weight and weight a computation with it.

toList :: Foldable t => t a -> [a]

List of elements of a structure.