haskell - 在 Haskell 中寻找自由幂等幺半群的元素的最小形式

Question

free idempotent monoid类似于自由幺半群，但由方程 x² = x 商；例如，aa = a，bcbcb = b(cb)(cb) = bcb,

但是，要在幺半群中找到单词的最小形式，扩展 (x = x²) 以及收缩 (x² = x) 通常是必需的，因此并非语言中的每个 squarefree 词都是最小的。例如，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

M. Lothaire 的“Combinatorics on Words”中定理 2.4.1 的证明似乎有一些相关的线索。对于给定的单词，我们提取它的四个部分:

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

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

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

1. 计算 p, a, b, q 使得 w .= (p, a, b, q)。
2. 递归计算p 的规范形式p' 和q 的q'。 (基本情况:空词的规范形式是空词。)
3. 找到作为bq'前缀的p'a的最长后缀；称这个为 s，剩余的为 t，因此 p'a = ts。
4. 返回tbq'。

通过相对简单的归纳论证，我相信该算法是正确的。 “正确”是指 w1 ~ w2 iff f(w1) = f(w2)，其中 f 是上述函数.尚不清楚 f 按您建议的顺序生成等价类的最小代表，但也许这种意义上的正确性足以满足您的需求。

(严格来说，上面的第 3 步和第 4 步对于正确性来说并不是完全必要的。您可以只返回 p'abq' 并获得相同的保证。但是生成的代表会很长与上面提出的算法的比较。)

这个算法效率不高!您可以将此视为进行两次递归调用，每次调用的单词都少了一个唯一字母，因此这需要的时间至少是原始单词字母表大小的指数级。哎呀。您可能想考虑一些简单的快速路径案例。例如，当所有重复的字母彼此紧邻时，删除相邻的重复字母规范化。另一个可能有用的快速路径:规范化 wx 时，您知道 w 和 x 已经规范化，然后 w 和 x 如果您在递归期间碰巧遇到它们，它们本身可以是基本情况，并且您可能可以想出一些方法来廉价地识别 w 的其他子串和 x 是合适的基本情况。