> I suspect the monoidal preorder compatibility condition can be rephrased in terms of the left and right actions of the monoid. Something like, \\(x \le y \implies L_z(x) \le L_z(y)\\) and \\(x \le y \implies R_z(x) \le R_z(y)\\) for all \\(z\\). So the left and right actions for all elements have to be monotone maps.

I agree. It appears we can say \\(\langle \leq, \otimes, I \rangle\\) is a monoidal preorder if and only if

x \leq y \Longleftrightarrow \forall z. L_z(x) \leq L_z(y) \text{ and } R_z(x) \leq R_z(y)

> Does that complexity reduction have anything to do with difference lists?


Difference lists are precisely *left actions* on lists.

Here's a little implementation:

newtype DList a = DList ([a] -> [a])

toDList :: [a] -> DList a
toDList xs = DList (xs ++)

fromDList :: DList a -> [a]
fromDList (DList leftAction) = leftAction []

But it's not a complete implementation ;-)

**Puzzle MD1**: Give the instance of `Monoid` for `DList a`, ie replace the `undefined`s below:

instance Monoid (DList a) where
(<>) = undefined
mempty = undefined

Remember that we want to obey the laws:

(\texttt{toDList}\, a)\ ⬦\ (\texttt{toDList}\, b) & \equiv \texttt{toDList}\, (a ⧺ b) \\\\
(\texttt{fromDList}\, a) ⧺ (\texttt{fromDList}\, b) & \equiv \texttt{fromDList}\, (a\ ⬦\ b) \\\\
\texttt{fromDList}\, \texttt{mempty} & \equiv [] \\\\
\texttt{mempty} & \equiv \texttt{toDList}\, [] \\\\