在Haskell中寻找自由幂等元的极小形式

Question

自由幂等幺半群类似于自由幺半群，但由方程x 2=x所商；例如，aa = a，bcbcb = b(cb)(cb) = bcb，

然而，要在单面图中找到单词的最小形式，通常需要展开(x =x 2)和收缩(x 2= x)，因此并非语言中的每个无平方字都是最小的。例如，bacbcabc = bacabc。结果表明，有限个生成元上的自由幂等幺半群是有限的。

我要寻找的是Haskell中的一个算法，该算法在单面图中取一个有限单词，在这里表示为Seq，并返回它的极小形式，其中极小的定义是：

1. 最短的长度
2. 在相同长度的词汇中最小的。

因此，此方法的签名将是：

minimizeIdempotent :: Ord a => Seq a -> Seq a
minimizeIdempotent w = ...

从这里开始，Semigroup和Monoid实例的定义是：

newtype Idempotent a = Idempotent (Seq a)
  deriving (Eq, Ord, Show)

instance Ord a => Semigroup (Idempotent a) where
  Idempotent x <> Idempotent y
    | null x = Idempotent y
    | null y = Idempotent x
    | otherwise = Idempotent (minimizeIdempotent (x <> y))

  stimes n x = case compare n 0 of
    LT -> error "stimes (Idempotent): negative count"
    EQ -> Idempotent mempty
    GT -> x

instance Ord a => Monoid (Idempotent a) where
  mempty = Idempotent mempty
  mappend = (<>)

Answer 1

Lothaire在“词的组合论”中定理2.4.1的证明似乎有一些相关的线索。对于一个给定的词，我们取出其中的四块：

1. 最长的前缀，它不包含整个单词所做的所有字母。
2. 下一封信
3. 最长的后缀，它不包含整个单词所做的所有字母。
4. 上一封信。

当p和q分别是w的适当前缀和后缀时，写w .= (p，a，b，q)，a和b分别是下一个字母和前一个字母。例如，bacbcabc .= (ba，c，a，bc)，aaabaa .= (aaa，b，b，aa)和abc .= (abc，d，a，bcd)。

如果w1 .= ( p1，a1，b1，q1)和w2 .= (p2，a2，b2，q2)在第34页的索赔(iii)中证明了w1 ~ w2 iff p1~ p2，a1 =p1=和on 20##。(我用~表示方程x~ xx导出的同余关系，这样我就能区分精确的相等和商相等。)我们可以使用它来创建计算给定单词w的规范形式的算法，如下所示：

1. 计算p，a，b，q使w .= (p，a，b，q)。
2. 递归计算p‘表示p，q’表示q。(基本情况:空词的规范形式是空词。)
3. 查找p‘的最长后缀，它是bq’的前缀；调用这个s和剩菜t，这样p‘= ts。
4. 返回tbq‘。

通过一个相对简单的归纳论证，我相信这个算法是正确的。所谓“正确”，我指的是w1 ~ w2当且仅当f(w1) = f(w2)，其中f是上面描述的函数。还不清楚f是否通过您提议的顺序来生成等价类的最小代表，但也许在这个意义上的正确性已经满足了您的需要。

(严格地说，上面的步骤3和4对于正确性来说并不是完全必要的。你只需返回p‘’abq‘就可以得到同样的保证。但是，与上面提出的算法相比，产生的代表将是非常长的。

这个算法不是很有效！您可以认为这是两个递归调用，每个调用的单词都少了一个唯一的字母，所以这需要时间，至少是原始单词的字母表的指数大小。啊呀。你可能会想出几个简单的快速路径的例子。例如，当所有重复的字母都彼此相邻时，删除相邻的重复字母就会规范化。另一条可能有用的快速路径是:当您知道w和x已经被规范化时，如果在递归过程中碰巧到达它们，那么w和x本身就可以成为基本情况，而且您可能会想出一些方法来廉价地识别w和x的其他子字符串，这些都是合适的大小写。