Repetitions as an Hylomorphism

Question

So I've been trying to convert this Haskell function thats checks if a list doesn't have any repetitions into an Hylomorphism, but there's something odd about it.

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

I'll be glad if anyone can help! Thx

Answer 1

Well a hylomoprhism is a function h : A → C that can be defined in an anamoprhism (g and p) and catamorphism (c and ⊕) part.

The anamorphism part consists of a function g : A → B × A that "unfolds" the object into smaller parts, and p : A → Bool a predicate that determines if we are done unfolding.

The catamorphism part consists of a value c ∈ C and an operator ⊕ : B × C → C.

(this text is a slightly modified version of the Wikipedia page)

In your case the unfolding means that we unfold a list in some value (of type B, and a recursive part, that is here the tail of the list.

The predicate p can be derived out of your definition: if the list is empty, then we have terminated. It is clear that in that case we return True, so that means c is True.

So now what would the B part be? Well if we look at your function we need access to both the head and the tail of the list, so B can be seen as a 2-tuple containing the head (as first element), and a tail (as second element).

So now the remaining question is what ⊕ does? It takes as input a 2-tuple of type E×[E] (pseudo-Haskell notation), and a boolean (type C which is a Bool). As we can see, it checks if the head is en element of the tail. If that is the case, it returns False, and ignores the recursive part, otherwise it returns the recursive part.

So we can write this in Haskell like:

-- 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 is thus a straighforward implementation based on the definition where we thus take the functions p, c, plus and g as "building blocks".