Copyright	(c) Donnacha Oisín Kidney 2021
Maintainer	mail@doisinkidney.com
Stability	experimental
Portability	non-portable
Safe Haskell	None
Language	Haskell2010

Control.Monad.Heap

Contents

Heap Type
- Non-transformer form
Constructing Heaps
Popping the smallest element
Turning into a cons-list
Searching the whole heap
Returning one element

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

newtype HeapT w m a = HeapT {
- runHeapT :: ListT m (Node w a (HeapT w m a))
}
data Node w a b
- = Leaf a
- | !w :< b
type Heap w = HeapT w Identity
pattern Heap :: [Node w a (Heap w a)] -> Heap w a
runHeap :: Heap w a -> [Node w a (Heap w a)]
fromList :: Applicative m => [(a, w)] -> HeapT w m a
popMin :: Monus w => Heap w a -> ([a], Maybe (w, Heap w a))
popMinT :: (Monus w, Monad m) => HeapT w m a -> m ([a], Maybe (w, HeapT w m a))
flatten :: Monus w => Heap w a -> [(w, [a])]
flattenT :: (Monad m, Monus w) => HeapT w m a -> ListT m (w, [a])
search :: Monus w => Heap w a -> [(a, w)]
searchT :: (Monad m, Monus w) => HeapT w m a -> m [(a, w)]
best :: Monus w => Heap w a -> Maybe (w, a)
bestT :: (Monad m, Monus w) => HeapT w m a -> m (Maybe (w, a))

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 runHeapT :: ListT m (Node w a (HeapT w m a))

Instances

Instances details

(Monad m, Monus 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 => 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 #
(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. 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.1.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))))))

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 Rep1 (Node w a :: Type -> Type) = D1 ('MetaData "Node" "Control.Monad.Heap" "monus-weighted-search-0.1.0.0-inplace" 'False) (C1 ('MetaCons "Leaf" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a)) :+: C1 ('MetaCons ":<" ('InfixI 'RightAssociative 5) 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 w) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) Par1))
type Rep (Node w a b) Source #
Instance details Defined in Control.Monad.Heap type Rep (Node w a b) = D1 ('MetaData "Node" "Control.Monad.Heap" "monus-weighted-search-0.1.0.0-inplace" 'False) (C1 ('MetaCons "Leaf" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a)) :+: C1 ('MetaCons ":<" ('InfixI 'RightAssociative 5) 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'SourceStrict 'DecidedStrict) (Rec0 w) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 b)))

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 element

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.

Turning into a cons-list

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

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

The weights returned are the differences, not the absolute weights.

>>> flatten (fromList [('a',5), ('b', 3), ('c',6)])
[(0,""),(3,"b"),(2,"a"),(1,"c")]

flattenT :: (Monad m, Monus w) => HeapT w m a -> ListT m (w, [a]) 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.