title: Finding the minimal form for an element of the free idempotent monoid in Haskell
body: <p>The <a href="http://mathworld.wolfram.com/FreeIdempotentMonoid.html" rel="nofollow noreferrer">free idempotent monoid</a> is like the free monoid, but quotiented by the equation <em>x</em>² = <em>x</em>; for instance, <em>aa</em> = <em>a</em>, <em>bcbcb</em> = <em>b(cb)(cb)</em> = <em>bcb</em>,</p>
  
  <p>However, to find the minimal form of a word in the monoid, expansion (<em>x</em> = <em>x</em>²) as well as contraction (<em>x</em>² = x) is often required, so not every squarefree word in the language is minimal. For instance, <em>bacbcabc</em> = <em>bacabc</em>. As a result, the free idempotent monoid on a finite number of generators is finite.</p>
  
  <p>What I'm looking for is an algorithm in Haskell that takes a finite word in the monoid, represented here as a <a href="https://hackage.haskell.org/package/containers-0.6.2.1/docs/Data-Sequence.html#t:Seq" rel="nofollow noreferrer"><code>Seq</code></a>, and returns its minimal form, where minimal is defined by:</p>
  
  <ol>
  <li>Shortest length, and</li>
  <li>Lexicographically smallest among words of the same length.</li>
  </ol>
  
  <p>So the signature for this method would be:</p>
  
  <pre class="lang-hs prettyprint-override"><code>minimizeIdempotent :: Ord a =&gt; Seq a -&gt; Seq a
  minimizeIdempotent w = ...
  </code></pre>
  
  <p>From there, the definition for the <code>Semigroup</code> and <code>Monoid</code> instances would be:</p>
  
  <pre class="lang-hs prettyprint-override"><code>newtype Idempotent a = Idempotent (Seq a)
    deriving (Eq, Ord, Show)
  
  instance Ord a =&gt; Semigroup (Idempotent a) where
    Idempotent x &lt;&gt; Idempotent y
      | null x = Idempotent y
      | null y = Idempotent x
      | otherwise = Idempotent (minimizeIdempotent (x &lt;&gt; y))
  
    stimes n x = case compare n 0 of
      LT -&gt; error "stimes (Idempotent): negative count"
      EQ -&gt; Idempotent mempty
      GT -&gt; x
  
  instance Ord a =&gt; Monoid (Idempotent a) where
    mempty = Idempotent mempty
    mappend = (&lt;&gt;)
  </code></pre>