Safe Haskell | Safe-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 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

Weighted nondeterminstic computations over the weight `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