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

But it's not a complete implementation ;-)

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

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}

$$

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}

$$