Control.Monad.WeightedSearch

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.

Documentation

data T w a

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 where

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

Methods

difference :: w -> w -> w

Instances

Weight Double

Weight Float

Weight Int

Weight Integer

Integral a => Weight (Ratio a)

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

Take a positive weight and weight a computation with it.

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

List of elements of a structure.