  Automata learning has been successfully applied in the verification of
hardware and software. The size of the automaton model learned is a bottleneck
for scalability, and hence optimizations that enable learning of compact
representations are important. This paper exploits monads, both as a
mathematical structure and a programming construct, to design, prove correct,
and implement a wide class of such optimizations. The former perspective on
monads allows us to develop a new algorithm and accompanying correctness
proofs, building upon a general framework for automata learning based on
category theory. The new algorithm is parametric on a monad, which provides a
rich algebraic structure to capture non-determinism and other side-effects. We
show that our approach allows us to uniformly capture existing algorithms,
develop new ones, and add optimizations. The latter perspective allows us to
effortlessly translate the theory into practice: we provide a Haskell library
implementing our general framework, and we show experimental results for two
specific instances: non-deterministic and weighted automata.
