haskell - 重复作为一个类同态

Question

所以我一直在尝试将这个检查列表是否没有任何重复的 Haskell 函数转换为 Hylomorphism，但它有些奇怪。

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

如果有人可以提供帮助，我会很高兴！谢谢

Answer 1

嗯，hylomorphism是一个函数h : A → C可以在变形（g和p）和变态（c和⊕）部分中定义。

变形部分由一个函数g : A → B × A组成，它将对象“展开”成更小的部分，而p : A → Bool一个谓词，用于确定我们是否完成展开。

catamorphism部分由值c ∈ C和算子⊕ : B × C → C组成。

（本文是维基百科页面的略微修改版本）

在您的情况下，展开意味着我们以某个值（类型B和递归部分，即列表的尾部）展开列表。

谓词p可以从您的定义中派生出来：如果列表为空，那么我们已经终止。很明显，在这种情况下我们返回True，所以这意味着c是True。

那么现在B部分会是什么？好吧，如果我们查看您的函数，我们需要访问列表的头部和尾部，因此B可以被视为包含头部（作为第一个元素）和尾部（作为第二个元素）的 2 元组。

所以现在剩下的问题是⊕做什么？它将一个E×[E]类型的 2 元组（伪 Haskell 表示法）和一个布尔值（类型C，它是 a 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“构建块”。plusg