Is there a correct way of composing moore machines?

Question

A mealy machine is just a stateful function. Hence, two mealy machines can be composed using simple function composition. A moore machine is a restricted mealy machine with an initial output value. Is there a way to compose two moore machines? This is what I tried in Haskell:

type Mealy a b = a -> b -- a stateful function, probably using unsafePerformIO

type Moore a b = (b, Mealy a b) -- output must be consistent with current state

composeMoore :: (c, b -> c) -> (b, a -> b) -> (c, a -> c)
composeMoore (x, f) (_, g) = (x,   f . g) --    is this correct?
composeMoore (_, f) (y, g) = (f y, f . g) -- or is this correct?

I believe that they are both wrong. In fact, I believe that it's not possible to compose two moore machines. However, I might be wrong. Is there a correct way of composing moore machines?

Defintion: The composition of moore machines is an operation of the type (.) :: Moore b c -> Moore a b -> Moore a c for which the law of associativity (i.e. h . (g . f) = (h . g) . f) holds true.

Note: This is just a theoretical question. I am not actually using Haskell to write stateful functions.

Answer 1

No, there's no correct way of composing two moore machines. Composition has no meaning without an identity element. This is because composition along with its identity element must together form a monoid in order to be meaningful. This is the mathematical definition of a category.

A category C consists of:

1. A class, ob(C), of sets called objects.
2. A class, hom(C), of morphisms between the objects. The hom-class, hom(a, b), is the collection of all the morphisms from a to b (each morphism f is denoted as f : a -> b).
3. A binary operation hom(b, c) * hom(a, b) -> hom(a, c) called the composition of morphisms, for every three objects a, b and c.

In addition, they must satisfy the following laws:

1. Associativity: For all f : a -> b, g : b -> c and h : c -> d, the relation h . (g . f) = (h . g) . f must hold true.
2. Left identity: For all objects x there must be a morphism id_x : x -> x called the identity morphism for x such that for all f : a -> x the relation id_x . f = f holds true.
3. Right identity: For all objects x there must be a morphism id_x : x -> x called the identity morphism for x such that for all g : x -> b the relation g . id_x = g holds true.

There's no way of composing two moore machines simply because there's no identity element for the composition of two moore machines. Hence, moore machines do not form a category. A moore machine is defined as a 6-tuple (s, s0, a, b, t, g) consisting of:

1. A finite set of states s.
2. A start state s0 which is an element s.
3. A finite set a called the input alphabet.
4. A finite set b called the output alphabet.
5. A transition function t : s * a -> s.
6. An output function g : s -> b.

The reason there's no identity element for moore machines is because the output of the moore machine doesn't depend upon its input. It only depends upon the current state. The initial state is s0. Hence, the initial output is g(s0). The initial output would be undefined for the identity element because it would have to match the type of the input which is yet unknown. Therefore, the "identity element" would be unable to satisfy the left and/or the right identity laws.