monus-weighted-search-0.2.0.0: Efficient search weighted by an ordered monoid with monus.
Copyright(c) Donnacha Oisín Kidney 2021
Maintainermail@doisinkidney.com
Stabilityexperimental
Portabilitynon-portable
Safe HaskellNone
LanguageHaskell2010

Control.Monad.Heap

Description

The Heap monad: a monad for efficient weighted search.

This module provides an implementation of the Heap monad transformer as described in:

  • Donnacha Oisín Kidney and Nicolas Wu. 2021. Algebras for weighted search. Proc. ACM Program. Lang. 5, ICFP, Article 72 (August 2021), 30 pages. DOI:https://doi.org/10.1145/3473577

This monad transformer can be used to implement search algorithms like Dijkstra's algorithm (see MonusWeightedSearch.Examples.Dijkstra), or the Viterbi algorithm (MonusWeightedSearch.Examples.Viterbi), or probabilistic parsing (MonusWeightedSearch.Examples.Parsing).

The type supports nondeterminism (using the Alternative and MonadPlus interfaces), where each branch in a computation can be weighted by some Monus. A Monus is an ordered Monoid with some pseudo-subtraction operator, see the Data.Monus module for more details.

Synopsis

Heap Type

newtype HeapT w m a Source #

The HeapT monad transformer: a monad for weighted search.

This monad supports nondeterminism through the Alternative and MonadPlus classes, but different branches in the computation may be weighted by the w parameter. A computation can be given a specific weight using the MonadWriter interface:

  tell 4 >> xs

This weights the computation xs with 4.

Depending on the Monus used, the order of the search can be specified. For instance, using the Monus in Data.Monus.Dist, we have the following:

>>> search (fromList [('a',5), ('b', 3), ('c',6)])
[('b',3),('a',5),('c',6)]
>>> search (fromList [('b',3), ('a',5), ('c',6)])
[('b',3),('a',5),('c',6)]

Constructors

HeapT 

Fields

Instances

Instances details
(Monad m, Monoid w) => MonadWriter w (HeapT w m) Source # 
Instance details

Defined in Control.Monad.Heap

Methods

writer :: (a, w) -> HeapT w m a #

tell :: w -> HeapT w m () #

listen :: HeapT w m a -> HeapT w m (a, w) #

pass :: HeapT w m (a, w -> w) -> HeapT w m a #

MonadState s m => MonadState s (HeapT w m) Source # 
Instance details

Defined in Control.Monad.Heap

Methods

get :: HeapT w m s #

put :: s -> HeapT w m () #

state :: (s -> (a, s)) -> HeapT w m a #

MonadReader r m => MonadReader r (HeapT w m) Source # 
Instance details

Defined in Control.Monad.Heap

Methods

ask :: HeapT w m r #

local :: (r -> r) -> HeapT w m a -> HeapT w m a #

reader :: (r -> a) -> HeapT w m a #

MonadError e m => MonadError e (HeapT w m) Source # 
Instance details

Defined in Control.Monad.Heap

Methods

throwError :: e -> HeapT w m a #

catchError :: HeapT w m a -> (e -> HeapT w m a) -> HeapT w m a #

MonadTrans (HeapT w) Source # 
Instance details

Defined in Control.Monad.Heap

Methods

lift :: Monad m => m a -> HeapT w m a #

Monad m => MonadFree ((,) w) (HeapT w m) Source # 
Instance details

Defined in Control.Monad.Heap

Methods

wrap :: (w, HeapT w m a) -> HeapT w m a #

Monad m => Monad (HeapT w m) Source # 
Instance details

Defined in Control.Monad.Heap

Methods

(>>=) :: HeapT w m a -> (a -> HeapT w m b) -> HeapT w m b #

(>>) :: HeapT w m a -> HeapT w m b -> HeapT w m b #

return :: a -> HeapT w m a #

Functor m => Functor (HeapT w m) Source # 
Instance details

Defined in Control.Monad.Heap

Methods

fmap :: (a -> b) -> HeapT w m a -> HeapT w m b #

(<$) :: a -> HeapT w m b -> HeapT w m a #

Monad m => Applicative (HeapT w m) Source # 
Instance details

Defined in Control.Monad.Heap

Methods

pure :: a -> HeapT w m a #

(<*>) :: HeapT w m (a -> b) -> HeapT w m a -> HeapT w m b #

liftA2 :: (a -> b -> c) -> HeapT w m a -> HeapT w m b -> HeapT w m c #

(*>) :: HeapT w m a -> HeapT w m b -> HeapT w m b #

(<*) :: HeapT w m a -> HeapT w m b -> HeapT w m a #

Foldable m => Foldable (HeapT w m) Source # 
Instance details

Defined in Control.Monad.Heap

Methods

fold :: Monoid m0 => HeapT w m m0 -> m0 #

foldMap :: Monoid m0 => (a -> m0) -> HeapT w m a -> m0 #

foldMap' :: Monoid m0 => (a -> m0) -> HeapT w m a -> m0 #

foldr :: (a -> b -> b) -> b -> HeapT w m a -> b #

foldr' :: (a -> b -> b) -> b -> HeapT w m a -> b #

foldl :: (b -> a -> b) -> b -> HeapT w m a -> b #

foldl' :: (b -> a -> b) -> b -> HeapT w m a -> b #

foldr1 :: (a -> a -> a) -> HeapT w m a -> a #

foldl1 :: (a -> a -> a) -> HeapT w m a -> a #

toList :: HeapT w m a -> [a] #

null :: HeapT w m a -> Bool #

length :: HeapT w m a -> Int #

elem :: Eq a => a -> HeapT w m a -> Bool #

maximum :: Ord a => HeapT w m a -> a #

minimum :: Ord a => HeapT w m a -> a #

sum :: Num a => HeapT w m a -> a #

product :: Num a => HeapT w m a -> a #

Traversable m => Traversable (HeapT w m) Source # 
Instance details

Defined in Control.Monad.Heap

Methods

traverse :: Applicative f => (a -> f b) -> HeapT w m a -> f (HeapT w m b) #

sequenceA :: Applicative f => HeapT w m (f a) -> f (HeapT w m a) #

mapM :: Monad m0 => (a -> m0 b) -> HeapT w m a -> m0 (HeapT w m b) #

sequence :: Monad m0 => HeapT w m (m0 a) -> m0 (HeapT w m a) #

(Arbitrary1 m, Arbitrary w) => Arbitrary1 (HeapT w m) Source # 
Instance details

Defined in Control.Monad.Heap

Methods

liftArbitrary :: Gen a -> Gen (HeapT w m a) #

liftShrink :: (a -> [a]) -> HeapT w m a -> [HeapT w m a] #

Monad m => Alternative (HeapT w m) Source # 
Instance details

Defined in Control.Monad.Heap

Methods

empty :: HeapT w m a #

(<|>) :: HeapT w m a -> HeapT w m a -> HeapT w m a #

some :: HeapT w m a -> HeapT w m [a] #

many :: HeapT w m a -> HeapT w m [a] #

Monad m => MonadPlus (HeapT w m) Source # 
Instance details

Defined in Control.Monad.Heap

Methods

mzero :: HeapT w m a #

mplus :: HeapT w m a -> HeapT w m a -> HeapT w m a #

MonadCont m => MonadCont (HeapT w m) Source # 
Instance details

Defined in Control.Monad.Heap

Methods

callCC :: ((a -> HeapT w m b) -> HeapT w m a) -> HeapT w m a #

(Monoid w, m ~ Identity) => IsList (HeapT w m a) Source # 
Instance details

Defined in Control.Monad.Heap

Associated Types

type Item (HeapT w m a) #

Methods

fromList :: [Item (HeapT w m a)] -> HeapT w m a #

fromListN :: Int -> [Item (HeapT w m a)] -> HeapT w m a #

toList :: HeapT w m a -> [Item (HeapT w m a)] #

(forall x. Eq x => Eq (m x), Eq a, Eq w) => Eq (HeapT w m a) Source # 
Instance details

Defined in Control.Monad.Heap

Methods

(==) :: HeapT w m a -> HeapT w m a -> Bool #

(/=) :: HeapT w m a -> HeapT w m a -> Bool #

(forall x. Data x => Data (m x), Typeable m, Data a, Data w) => Data (HeapT w m a) Source # 
Instance details

Defined in Control.Monad.Heap

Methods

gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> HeapT w m a -> c (HeapT w m a) #

gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (HeapT w m a) #

toConstr :: HeapT w m a -> Constr #

dataTypeOf :: HeapT w m a -> DataType #

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (HeapT w m a)) #

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (HeapT w m a)) #

gmapT :: (forall b. Data b => b -> b) -> HeapT w m a -> HeapT w m a #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> HeapT w m a -> r #

gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> HeapT w m a -> r #

gmapQ :: (forall d. Data d => d -> u) -> HeapT w m a -> [u] #

gmapQi :: Int -> (forall d. Data d => d -> u) -> HeapT w m a -> u #

gmapM :: Monad m0 => (forall d. Data d => d -> m0 d) -> HeapT w m a -> m0 (HeapT w m a) #

gmapMp :: MonadPlus m0 => (forall d. Data d => d -> m0 d) -> HeapT w m a -> m0 (HeapT w m a) #

gmapMo :: MonadPlus m0 => (forall d. Data d => d -> m0 d) -> HeapT w m a -> m0 (HeapT w m a) #

(Ord w, Ord a, forall x. Ord x => Ord (m x), Eq (HeapT w m a), Eq (ListT m (Node w a (HeapT w m a)))) => Ord (HeapT w m a) Source # 
Instance details

Defined in Control.Monad.Heap

Methods

compare :: HeapT w m a -> HeapT w m a -> Ordering #

(<) :: HeapT w m a -> HeapT w m a -> Bool #

(<=) :: HeapT w m a -> HeapT w m a -> Bool #

(>) :: HeapT w m a -> HeapT w m a -> Bool #

(>=) :: HeapT w m a -> HeapT w m a -> Bool #

max :: HeapT w m a -> HeapT w m a -> HeapT w m a #

min :: HeapT w m a -> HeapT w m a -> HeapT w m a #

(forall x. Read x => Read (m x), Read w, Read a) => Read (HeapT w m a) Source # 
Instance details

Defined in Control.Monad.Heap

Methods

readsPrec :: Int -> ReadS (HeapT w m a) #

readList :: ReadS [HeapT w m a] #

readPrec :: ReadPrec (HeapT w m a) #

readListPrec :: ReadPrec [HeapT w m a] #

(forall x. Show x => Show (m x), Show a, Show w) => Show (HeapT w m a) Source # 
Instance details

Defined in Control.Monad.Heap

Methods

showsPrec :: Int -> HeapT w m a -> ShowS #

show :: HeapT w m a -> String #

showList :: [HeapT w m a] -> ShowS #

Generic (HeapT w m a) Source # 
Instance details

Defined in Control.Monad.Heap

Associated Types

type Rep (HeapT w m a) :: Type -> Type #

Methods

from :: HeapT w m a -> Rep (HeapT w m a) x #

to :: Rep (HeapT w m a) x -> HeapT w m a #

Monad m => Semigroup (HeapT w m a) Source # 
Instance details

Defined in Control.Monad.Heap

Methods

(<>) :: HeapT w m a -> HeapT w m a -> HeapT w m a #

sconcat :: NonEmpty (HeapT w m a) -> HeapT w m a #

stimes :: Integral b => b -> HeapT w m a -> HeapT w m a #

Monad m => Monoid (HeapT w m a) Source # 
Instance details

Defined in Control.Monad.Heap

Methods

mempty :: HeapT w m a #

mappend :: HeapT w m a -> HeapT w m a -> HeapT w m a #

mconcat :: [HeapT w m a] -> HeapT w m a #

(Arbitrary1 m, Arbitrary w, Arbitrary a) => Arbitrary (HeapT w m a) Source # 
Instance details

Defined in Control.Monad.Heap

Methods

arbitrary :: Gen (HeapT w m a) #

shrink :: HeapT w m a -> [HeapT w m a] #

(forall x. NFData x => NFData (m x), NFData w, NFData a) => NFData (HeapT w m a) Source # 
Instance details

Defined in Control.Monad.Heap

Methods

rnf :: HeapT w m a -> () #

type Rep (HeapT w m a) Source # 
Instance details

Defined in Control.Monad.Heap

type Rep (HeapT w m a) = D1 ('MetaData "HeapT" "Control.Monad.Heap" "monus-weighted-search-0.2.0.0-inplace" 'True) (C1 ('MetaCons "HeapT" 'PrefixI 'True) (S1 ('MetaSel ('Just "runHeapT") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (ListT m (Node w a (HeapT w m a))))))
type Item (HeapT w m a) Source # 
Instance details

Defined in Control.Monad.Heap

type Item (HeapT w m a) = (a, w)

data Node w a b Source #

A Heap is a list of Nodes of Heaps.

Constructors

Leaf a 
!w :< b infixr 5 

Instances

Instances details
Bitraversable (Node w) Source # 
Instance details

Defined in Control.Monad.Heap

Methods

bitraverse :: Applicative f => (a -> f c) -> (b -> f d) -> Node w a b -> f (Node w c d) #

Bifoldable (Node w) Source # 
Instance details

Defined in Control.Monad.Heap

Methods

bifold :: Monoid m => Node w m m -> m #

bifoldMap :: Monoid m => (a -> m) -> (b -> m) -> Node w a b -> m #

bifoldr :: (a -> c -> c) -> (b -> c -> c) -> c -> Node w a b -> c #

bifoldl :: (c -> a -> c) -> (c -> b -> c) -> c -> Node w a b -> c #

Bifunctor (Node w) Source # 
Instance details

Defined in Control.Monad.Heap

Methods

bimap :: (a -> b) -> (c -> d) -> Node w a c -> Node w b d #

first :: (a -> b) -> Node w a c -> Node w b c #

second :: (b -> c) -> Node w a b -> Node w a c #

Generic1 (Node w a :: Type -> Type) Source # 
Instance details

Defined in Control.Monad.Heap

Associated Types

type Rep1 (Node w a) :: k -> Type #

Methods

from1 :: forall (a0 :: k). Node w a a0 -> Rep1 (Node w a) a0 #

to1 :: forall (a0 :: k). Rep1 (Node w a) a0 -> Node w a a0 #

Functor (Node w a) Source # 
Instance details

Defined in Control.Monad.Heap

Methods

fmap :: (a0 -> b) -> Node w a a0 -> Node w a b #

(<$) :: a0 -> Node w a b -> Node w a a0 #

Foldable (Node w a) Source # 
Instance details

Defined in Control.Monad.Heap

Methods

fold :: Monoid m => Node w a m -> m #

foldMap :: Monoid m => (a0 -> m) -> Node w a a0 -> m #

foldMap' :: Monoid m => (a0 -> m) -> Node w a a0 -> m #

foldr :: (a0 -> b -> b) -> b -> Node w a a0 -> b #

foldr' :: (a0 -> b -> b) -> b -> Node w a a0 -> b #

foldl :: (b -> a0 -> b) -> b -> Node w a a0 -> b #

foldl' :: (b -> a0 -> b) -> b -> Node w a a0 -> b #

foldr1 :: (a0 -> a0 -> a0) -> Node w a a0 -> a0 #

foldl1 :: (a0 -> a0 -> a0) -> Node w a a0 -> a0 #

toList :: Node w a a0 -> [a0] #

null :: Node w a a0 -> Bool #

length :: Node w a a0 -> Int #

elem :: Eq a0 => a0 -> Node w a a0 -> Bool #

maximum :: Ord a0 => Node w a a0 -> a0 #

minimum :: Ord a0 => Node w a a0 -> a0 #

sum :: Num a0 => Node w a a0 -> a0 #

product :: Num a0 => Node w a a0 -> a0 #

Traversable (Node w a) Source # 
Instance details

Defined in Control.Monad.Heap

Methods

traverse :: Applicative f => (a0 -> f b) -> Node w a a0 -> f (Node w a b) #

sequenceA :: Applicative f => Node w a (f a0) -> f (Node w a a0) #

mapM :: Monad m => (a0 -> m b) -> Node w a a0 -> m (Node w a b) #

sequence :: Monad m => Node w a (m a0) -> m (Node w a a0) #

(Eq a, Eq w, Eq b) => Eq (Node w a b) Source # 
Instance details

Defined in Control.Monad.Heap

Methods

(==) :: Node w a b -> Node w a b -> Bool #

(/=) :: Node w a b -> Node w a b -> Bool #

(Data w, Data a, Data b) => Data (Node w a b) Source # 
Instance details

Defined in Control.Monad.Heap

Methods

gfoldl :: (forall d b0. Data d => c (d -> b0) -> d -> c b0) -> (forall g. g -> c g) -> Node w a b -> c (Node w a b) #

gunfold :: (forall b0 r. Data b0 => c (b0 -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Node w a b) #

toConstr :: Node w a b -> Constr #

dataTypeOf :: Node w a b -> DataType #

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (Node w a b)) #

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Node w a b)) #

gmapT :: (forall b0. Data b0 => b0 -> b0) -> Node w a b -> Node w a b #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Node w a b -> r #

gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Node w a b -> r #

gmapQ :: (forall d. Data d => d -> u) -> Node w a b -> [u] #

gmapQi :: Int -> (forall d. Data d => d -> u) -> Node w a b -> u #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> Node w a b -> m (Node w a b) #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Node w a b -> m (Node w a b) #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Node w a b -> m (Node w a b) #

(Ord a, Ord w, Ord b) => Ord (Node w a b) Source # 
Instance details

Defined in Control.Monad.Heap

Methods

compare :: Node w a b -> Node w a b -> Ordering #

(<) :: Node w a b -> Node w a b -> Bool #

(<=) :: Node w a b -> Node w a b -> Bool #

(>) :: Node w a b -> Node w a b -> Bool #

(>=) :: Node w a b -> Node w a b -> Bool #

max :: Node w a b -> Node w a b -> Node w a b #

min :: Node w a b -> Node w a b -> Node w a b #

(Read a, Read w, Read b) => Read (Node w a b) Source # 
Instance details

Defined in Control.Monad.Heap

Methods

readsPrec :: Int -> ReadS (Node w a b) #

readList :: ReadS [Node w a b] #

readPrec :: ReadPrec (Node w a b) #

readListPrec :: ReadPrec [Node w a b] #

(Show a, Show w, Show b) => Show (Node w a b) Source # 
Instance details

Defined in Control.Monad.Heap

Methods

showsPrec :: Int -> Node w a b -> ShowS #

show :: Node w a b -> String #

showList :: [Node w a b] -> ShowS #

Generic (Node w a b) Source # 
Instance details

Defined in Control.Monad.Heap

Associated Types

type Rep (Node w a b) :: Type -> Type #

Methods

from :: Node w a b -> Rep (Node w a b) x #

to :: Rep (Node w a b) x -> Node w a b #

(NFData w, NFData a, NFData b) => NFData (Node w a b) Source # 
Instance details

Defined in Control.Monad.Heap

Methods

rnf :: Node w a b -> () #

type Rep1 (Node w a :: Type -> Type) Source # 
Instance details

Defined in Control.Monad.Heap

type Rep (Node w a b) Source # 
Instance details

Defined in Control.Monad.Heap

Non-transformer form

type Heap w = HeapT w Identity Source #

The Heap type, specialised to the Identity monad.

pattern Heap :: [Node w a (Heap w a)] -> Heap w a Source #

The constructor for the non-transformer Heap type.

runHeap :: Heap w a -> [Node w a (Heap w a)] Source #

Constructing Heaps

fromList :: Applicative m => [(a, w)] -> HeapT w m a Source #

Build a heap from a list of values paired with their weights.

Popping the smallest elements

popMin :: Monus w => Heap w a -> ([a], Maybe (w, Heap w a)) Source #

O(log n). popMin returns a list of those elements in the Heap with a weight equal to mempty, paired with the rest of the heap and the minimum weight in the rest of the heap.

popMinT :: (Monus w, Monad m) => HeapT w m a -> m ([a], Maybe (w, HeapT w m a)) Source #

The monadic variant of popMin.

Popping the smallest element

popMinOne :: Monus w => Heap w a -> Maybe ((a, w), Heap w a) Source #

O(log n). popMinOne returns the smallest weighted element in the heap, along with its weight, along with the rest of the heap.

This function is a more traditional version of popMin, but it has much worse performance in general.

popMinOneT :: forall w m a. (Monus w, Monad m) => HeapT w m a -> m (Maybe ((a, w), HeapT w m a)) Source #

The monadic variant of popMinOne.

Turning into a cons-list

flatten :: Monoid w => Heap w a -> [(a, w)] Source #

O(n). Return all the elements of the heap, not in order of their weights, paired with their weights.

>>> flatten (fromList [('a',5), ('b', 3), ('c',6)])
[('a',5),('b',3),('c',6)]

flattenT :: (Monad m, Monoid w) => HeapT w m a -> ListT m (a, w) Source #

The monadic version of flatten.

Searching the whole heap

search :: Monus w => Heap w a -> [(a, w)] Source #

O(n log n). Return all of the elements in the heap, in order, paired with their weights.

searchT :: (Monad m, Monus w) => HeapT w m a -> m [(a, w)] Source #

The monadic variant of search.

Returning one element

best :: Monus w => Heap w a -> Maybe (w, a) Source #

O(log n). Return the lowest-weight element in the heap, paired with its weight.

bestT :: (Monad m, Monus w) => HeapT w m a -> m (Maybe (w, a)) Source #

The monadic variant of best.