Повторения как гиломорфизм

Question

Итак, я пытался преобразовать эту функцию на Haskell, которая проверяет, нет ли в списке повторений, в Hylomorphism, но в этом есть что-то странное.

valid :: [a] -> Bool
valid [] = True
valid (h:t) = if (not (elem h t)) then valid t else False  

Я буду рад, если кто-нибудь может помочь! Спасибо

Answer 1

Хорошо, hylomoprhism - функция h: A → C, которая может быть определена в части анаморфизма (g и p) и катаморфизма (c и ⊕).

Часть анаморфизма состоит из функции g: A → B × A, которая "разворачивает" объект на более мелкие части, и p: A → Bool - предикат, который определяет, закончили ли мы развертывание.

Часть катаморфизма состоит из значения c ∈ C и оператора ⊕: B × C → C.

(этот текст является слегка измененной версией страницы Википедии)

В вашем случае развертывание означает, что мы разворачиваем список с некоторым значением (типа B, и рекурсивной частью, то есть здесь хвост списка).

Предикат p может быть выведен из вашего определения: если список пуст, то мы прекратили. Понятно, что в этом случае мы возвращаемся True, так что это означает, что с True,

Так что же теперь будет за B- часть? Хорошо, если мы посмотрим на вашу функцию, нам нужен доступ как к заголовку, так и к концу списка, поэтому B можно рассматривать как 2-кортеж, содержащий заголовок (как первый элемент) и хвост (как второй элемент).

Итак, теперь остаётся вопрос: что делает? Он принимает в качестве входных данных 2 кортежа типа E × [E] (псевдо-Хаскеллова запись) и логическое значение (тип C, который является Bool). Как мы видим, он проверяет, является ли голова элементом хвоста. Если это так, он возвращает False и игнорирует рекурсивную часть, в противном случае возвращает рекурсивную часть.

Таким образом, мы можем написать это в Haskell как:

-- types
type A e = [e]
type B e = (e, [e])
type C = Bool

-- functions
p :: A e -> Bool
p [] = True
p (_:_) = False

g :: A e -> (B e, A e)
g (h:t) = ((h, t), t)

c :: C
c = True

plus :: Eq e => B e -> C -> C
plus (h, t) r | elem h t = False
              | otherwise = r

hylo :: Eq e => A e -> C
hylo a | p a = c
       | otherwise = plus b (hylo a')
    where (b, a') = g a

hylo Таким образом, это простая реализация, основанная на определении, где мы, таким образом, берем функции p, c, plus а также g как "строительные блоки".