weighted-search- A weighted nondeterministic search monad

Safe HaskellSafe-Inferred



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
     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.



data T w a Source

Weighted nondeterminstic computations over the weight w.


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.


difference :: w -> w -> wSource

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.