> 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 undefineds 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}