Поиск того, содержится ли элемент в k-арном дереве

Question

У меня есть тип данных

data KTree a = Empty | Leaf a | Node a [KTree a] deriving (Eq, Show)

Я хотел бы написать функцию, которая возвращает либо true, либо false, относительно того, содержится ли элемент в моем дереве.

ktreeContains :: Eq a => a -> (KTree a) -> Bool
ktreeContains _ Empty = False
ktreeContains y (Leaf x) = (x==y)
-- code for nodes goes here

Итак, я понимаю, что мне нужно выяснить, является ли сам узел элементом, а затем рекурсивно вызвать ktreeContains для дочерних узлов, но я не понимаю, как это сделать, потому что у каждого узла может быть много дочерних элементов.

Я думаю, что код, который у меня есть, правильный, но не стесняйтесь поправлять меня, если нет.

Любая помощь приветствуется, спасибо.

Answer 1

ktreeContains y (Node x ts) = x == y || any (ktreeContains y) ts

Просто из интереса, в чем разница между Leaf x и Node x []?

Answer 2

ktreeContains y (Node x ts) = x == y || (any . ktreeContains) y ts

Answer 3

Мне было скучно, поэтому я решил обобщить решение, используя класс типов Data.Foldable.

import Data.Monoid
import Data.Foldable hiding (any)

data KTree a = Empty | Leaf a | Node a [KTree a] deriving (Ord, Eq, Show)

ktreeContains :: Eq a => a -> (KTree a) -> Bool
ktreeContains _ Empty = False
ktreeContains y (Leaf x) = (x==y)
-- code for nodes goes here
ktreeContains y (Node x ts) = x == y || any (ktreeContains y) ts

example1 = Empty
example2 = Leaf 1
example3 = Node 1 [Leaf 2]
example4 = Node 2 [Leaf 1, Node 4 [Leaf 5, Leaf 3]]

ktreeContainsF :: Eq a => a -> KTree a -> Bool
ktreeContainsF y = getAny . foldMap (Any.(==y))

instance Foldable KTree where
    foldMap f (Empty) = mempty
    foldMap f (Leaf a) = f a
    -- work out a possible ordering thats better than this
    -- it works for now since we are only dealing with Equality
    foldMap f (Node a x) = f a `mappend` (mconcat . map (foldMap f)) x

ktreeContains и ktreeContainsF являются идентичными функциями, за исключением того, что в ktreeContainsF обход KTree обрабатывается классом Data.Foldable. Поскольку foldMap возвращает Monoid, можно использовать моноид Any для объединения результатов поиска.

---

Если это поможет понять это немного лучше, ktreeContainsF - это более обобщенная версия ktreeContainsMonoid, которая определяется как

ktreeContainsMonoid y = getAny . Data.Foldable.foldl
        -- combination function, implicit when using FoldMap
        (\z x-> z `mappend` Any (x == y)) mempty -- also implicit in foldMap