DFA libraries in Haskell

Since I’m planning to write all the software for my final Master’s Thesis in Haskell, the first natural step is to look for libraries already implementing Probabilistic Discrete Finite Automata in Haskell. The probabilistic condition was too much constraining and I have been only able to find some implementations of simple DFA. Here are the ones I have found:

  • Halex is a library for manipulating regular languages. It’s a library developed at the University of Minho that also serves as the base lexer for the HaGLR (a generalized LR parser). It has the nice feature of generating Graphviz diagrams from the DFAs. It is distributed under the LPGL

  • In this page you can download the software implementation that is explained in this paper (A Collection of Functional Libraries for Theory of Computation). The software is distributed under the LPGL.

  • When browsing through the Haskell Wiki you can find the regular expressions implementations. But the implementation of reference for the DFAs seems that is embedded in a more complex library, theCompiler Toolkit for Haskell.

  • A number of implementations written by Haskell enthusiasts and documented in their blogs like this one and this set of articles.

Given this quick research of the available possibilities, the final choice will be to use the implementation described in the paper A Collection of Functional Libraries for Theory of Computation for the creation of a Probabilistic DFA library. Here are the reasons:

  • This is a LPGL library so I can use it without restrictions. I will try to get a clean code so I could contribute back.

  • The library seems that is focused on the DFA where other options are more focused on creating a good lexer to be included on a bigger piece of code like a parser or similar.

  • It is well documented and can help me to understand the underlying design decisions.

  • It is very small and I won’t get lost in the subtleties of a bigger implementation. Since I am a novice Haskeller this is a plus.