Finding whether or not an item is contained within an k-ary tree

Question

I have a data type

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

I would like to write a function that returns either true or false as to whether an item is contained within my tree.

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

So I realise I need to find whether the node itself is the item and then recursively call ktreeContains for the nodes children but I don't understand how to do this because each node can have many children.

I think the code I have so far is right, but feel free to correct me if not.

Any help appreciated, Thanks.

Answer 1

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

Answer 2

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

Just out of interest, what's the difference between Leaf x and Node x []?

Answer 3

I was bored so I decided to generalise the solution using the Data.Foldable typeclass.

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 and ktreeContainsF are identical functions except that in the ktreeContainsF the traversal of the KTree is handled by the Data.Foldable class. Since foldMap returns a Monoid it's possible to use the Any monoid to combine the search results.

---

If it helps to understand this a bit better, ktreeContainsF is a more generalised version of ktreeContainsMonoid which is defined as

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