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,0,0], [0,1], [1,0], , [0,0,0,0], [0,0,1], ... ]
Weights must be strictly positive for this to be well-defined.
Weighted nondeterminstic computations over the weight
The class of positive weights. We need to know how to subtract. Weights must be strictly positive.