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

MonusWeightedSearch.Examples.Parsing

Description

A probabilistic parser, implemented using the Heap monad.

The main interesting thing about this parser is that it is defined by flipping the order of State and Heap in the monad stack (the other way around you get a monad for things like Dijkstra's algorithm, MonusWeightedSearch.Examples.Dijkstra).

The parser itself is a probabilistic parser, meaning that it can have a preference for certain parse trees over others, based on their likelihood. When the parser is run the output is listed in order of each likelihood.

Synopsis

Documentation

type Parser a = StateT [a] (Heap Prob) Source #

A standard parser type.

Compare to type Parser a b = [a] -> [(b, [a])]: we have swapped out the list here for the heap, allowing for efficient ordering of results.

eof :: Parser a () Source #

Parse an empty string.

anyChar :: Parser a a Source #

Parse a single char.

satisfy :: (b -> Bool) -> Parser a b -> Parser a b Source #

Filter the output of a parse.

condition :: (b -> Prob) -> Parser a b -> Parser a b Source #

Assign a parse result a probability: when the parser is run, it will order results from most to least likely.

parse :: Parser a b -> [a] -> [(b, Prob)] Source #

Parse a string, ordering the results from most to least likely.