Нахождение минимальной формы для элемента свободного идемпотентного моноида в Haskell

Question

Свободный идемпотентный моноид подобен свободному моноиду, но определяется соотношением x ² = x ; например, aa = a , bcbcb = b (cb) (cb) = bcb ,

Однако, чтобы найти минимальную форму слова в моноиде, расширение ( x = x ²), а также сокращение ( x ² = x) часто требуется, поэтому не каждое квадратное слово в языке минимально. Например, bacbcab c = bacab c. В результате свободный идемпотентный моноид на конечном числе образующих конечен.

Я ищу алгоритм в 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

Доказательство теоремы 2.4.1 в «Комбинаторике слов» М. Лотера, по-видимому, имеет некоторые важные подсказки. Для данного слова мы вытащим четыре его части:

1. Самый длинный префикс, который не содержит всех букв, которые содержит целое слово.
2. Следующая буква.
3. Самый длинный суффикс, который не содержит всех букв, которые содержит целое слово.
4. Предыдущая буква.

Запись w. = (P, a , b, q) , когда p и q - соответствующие префикс и суффикс, соответственно, w и a и b - следующая и предыдущая буква соответственно. Например, bacbcab c. = (Ba, c, a, b c) , aaabaa. = (Aaa, b, b, aa) , и abcd. = (Ab c, d, a, bcd) .

Если w1. = (P1, a1, b1, q1) и w2. = (p2, a2, b2, q2) , в пункте (iii) на стр. 34 они доказывают, что w1 ~ w2 тогда и только p1 ~ p2 , a1 = a2 , b1 = b2 и q1 ~ q2 . (Я использую ~ для конгруэнтного отношения, индуцированного уравнением x ~ xx , чтобы я мог различить guish между точным равенством слов и частным равенством.) Мы можно использовать это для создания алгоритма вычисления канонической формы для заданного слова w следующим образом:

1. Вычислить p, a, b, q , например что w. = (p, a, b, q) .
2. Рекурсивное вычисление канонических форм p ' для p и q ' для q . (Базовый случай: канонической формой для пустого слова является пустое слово.)
3. Найдите самый длинный суффикс p'a , который является префиксом bq ' ; назовите это s и остатки t , так что p'a = t * .
4. Return tbq ' .

Я полагаю, что этот алгоритм верен относительно простым индуктивным аргументом. Под «правильным» я подразумеваю, что w1 ~ w2 , если f (w1) = f (w2) , где f - функция, описанная выше. Не ясно, что f дает минимальный представитель класса эквивалентности по предложенному вами порядку, но, возможно, правильности в этом смысле достаточно для ваших нужд.

(Строго говоря, шаги 3 и 4, приведенные выше, не являются абсолютно необходимыми для корректности. Вы можете просто вернуть p'abq ' и получить ту же гарантию. Но получающиеся в результате представители будут очень длинными по сравнению с предложенным выше алгоритмом.)

Этот алгоритм не очень эффективен! Вы можете думать об этом как о двух рекурсивных вызовах, каждый из которых содержит слова с наименьшим количеством уникальных букв, поэтому для этого требуется время, которое по крайней мере экспоненциально по размеру алфавита исходного слова. Хлоп. Возможно, вы захотите подумать о нескольких простых случаях для быстрого пути. Например, когда все повторяющиеся буквы непосредственно примыкают друг к другу, удаление соседних дубликатов канонизируется. Еще один быстрый путь, который может быть полезен: при канонизации wx , где вы знаете, w и x уже канонизированы, тогда w и x сами по себе могут быть базовыми случаями, если вы достигнете их во время рекурсии, и может случиться так, что вы можете подумать о некоторых способах дешевой идентификации дополнительных подстрок w и x , которые подходят базовые случаи.