I've been wondering if there is a way to define and work with finite state transducers in Haskell in an idiomatic way.
You can approach FSTs as generators (it generates an output of type {x1,x2}), or as recognizers (given an input of type {x1,x2} it recognizes it if it belongs to the rational relation), or as translators (given an input tape, it translates it into an output tape). Would the representation change depending on the approach?
Would it also be possible to model a FST in a way that you can produce one by specifying rewriting rules? E.g creating a DSL to model rewriting rules, and then creating a function createFST :: [Rule] -> FST
.
The closest I could find is Kmett, Bjarnason and Cough's machines
library:
https://hackage.haskell.org/package/machines
But I can't seem to realize how to model a FST with a Machine
. I'd suppose that the correct way of doing it would be similar to how they define Moore and Mealy machines: define a FST as a different entity, but provide an instance of Automaton
to be able to use it as a machine.
I found some other options too, but they define it in a straightforward way (like in https://hackage.haskell.org/package/fst ). That doesn't convince me much, as I wonder if there's a better way to do so idiomatically using the strengths of Haskell's type system (like how Moore and Mealy machines are defined in the machines
library).
A
Mealy
machine alternately reads ana
from a stream of inputsa
and outputs ab
to a stream of outputs. It reads first and then outputs once after each read.A
Moore
machine alternately outputs ab
to a stream of outputs and reads an inputa
from a stream of inputs. It starts with an output ofb
and then reads once after each output.An FST either reads from it's input, writes to its output, or stops. It can read as many times in a row as it wants or write as many times in a row as it wants.
The equivalent of an
FST
from machines isProcess
. It's definition is a little spread out. To simplify the discussion we are going to forget aboutProcess
for now and explore it from the inside-out.The base functor
To describe what a
Process
is, we're going to first notice a pattern in all three machines so far. Each of them recursively refers to itself for "what to do next". We are going to replace "what to do next" with any typenext
. TheMealy
machine, while mapping an input to an output, also provides thenext
machine to run.The
Moore
machine, after outputting and requesting an input, figures out thenext
machine to run.We can write the
FST
the same way. When weRead
from the input we'll figure out what to donext
depending on the input. When weWrite
to the output we'll also provide what to donext
after outputting. When weStop
there's nothing to do next.This pattern of eliminating explicit recursion shows up repeatedly in Haskell code, and is usually called a "base functor". In the machines package the base functor is
Step
. Compared to our code,Step
has renamed the type variable for the output too
, what to do next tor
, reading toAwait
, and writing toYield
.Await
ing is a little more complicated thanRead
because aMachine
can read from multiple sources. ForProcess
es that can only read from a single source,k
isIs
applied to a specific type, which is a proof the second typeIs
the first type. For aProcess
reading inputsa
,k
will beIs a
.The existential quantification
forall t.
is an implementation detail for dealing withSource
s. After witnessing thata ~ t
this becomes.If we unify
t
witha
and remove theRefl
constructor which is always the same, this looks like ourFSTF
.The extra
r
for what to do next inAwait
is what to do next when there's no more input.The machine transformer `MachineT`
The machine transformer,
MachineT
, makesStep
look almost like ourFST
. It says, "A machine operating over some monadm
is what to do in that monad to get the nextStep
. Thenext
thing to do after each step is anotherMachineT
."Overall, specialized for our types, this looks like
Machine
is a pureMachineT
.Universal quantification over all
Monad
sm
is another way of saying a computation doesn't need anything from an underlyingMonad
. This can be seen by substitutingIdentity
form
.Processes
A
Process
orProcessT
is aMachine
orMachineT
that only reads a single type of inputa
,Is a
.A
Process
has the following structure after removing all the intermediate constructors that are always the same. This structure is exactly the same as ourFST
, except it has an added "what to do next" in the case that there's no more input.The
ProcessT
variant has anm
wrapped around it so that it can act in the monad at each step.Process
models state transducers.