5 ms·

Is there such a thing as a stochastic parser combinator? E.g. to do Viterbi/HMM decoding, etc. Off-topic: I'd really like to get more and more Haskell features

• contravariant 5y ago
  Well here I think the Haskell abstractions chosen here are a bit unfortunate. I mean it's nice to use Applicative and Alternative but when you've got that p <*> (q <|> r) = (p <*> q) <|> (p <*> r) or at least that these are equivalent, then you might want to step back and wonder how on earth distributivity got into it. And after thinking for a few seconds and realizing that the parser which parses the empty string and the parsers which parses nothing correspond to the neutral elements for <*> and <|> respectively you might start to suspect some things. Anyway personally I reckon the proper space for dealing with these questions is by treating the space of parsers as a semiring. Although for parser combinators you break the commutativity of addition, but I can't find a better name than semiring right now. Basically you can show that if you've got something that sends the space of strings to a semiring then you can turn it into a linear map on the semimodule formed by simply multiplying strings and values of the semiring in the obvious way. You then get a semiring of parsers by using composition and addition of linear maps. Parser generators as described in this article are essentially based on the semiring formed by functions with composition as multiplication and f + g = f as addition (note, not commutative). This is wrapped in an 'Either' which also seems to have some semiring structure that I can't be bothered to analyse right now, though I noticed that <*> and <|> translated pretty neatly. Anyway all you have to do to get your Viterbi/HMM equivalent is to use the semiring formed by real numbers with 'max' as multiplication and ordinary multiplication as the addition operator. See also 'Kleene algebra' for more information in this direction.
  • pizza 5y ago
    Awesome, thanks for this info