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

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

type Parser a = StateT [a] (Heap Prob)
eof :: Parser a ()
anyChar :: Parser a a
satisfy :: (b -> Bool) -> Parser a b -> Parser a b
condition :: (b -> Prob) -> Parser a b -> Parser a b
parse :: Parser a b -> [a] -> [(b, Prob)]

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.