> 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?

Exactly!

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:

$$
\begin{align}
(\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}\, [] \\\\
\end{align}
$$