I am currently learning for an exam coming up soon.

We got some functions which we got given for preparing and training.

I want a function giving True if there are excact 2 nodes having the same value.

Given:

data Tree a = Node a [Tree a] | Leaf a

exercise62 :: Eq a => Tree62 a -> Bool
exercise62 = undefined

exercise62 (Node 5 [Node 6 [Leaf 4], Node 4 [Leaf 3]]) ~> True
exercise62 (Node 5 [(Node 5 [Leaf 4])]) ~~> True
exercise62 (Node 5 [Node 6 [Leaf 4], Node 3 [Leaf 2]]) ~~> False

My idea is:

1.) Create a function which will give a list with all values.

2.) Check if there is a value coming twice.

My problem is 1.)

What i tried so far:

exercise62Helper :: Eq a => Tree a -> [a]
exercise62Helper (Leaf a) = [a]
exercise62Helper (Node a b) = [a]    exercise62Helper (head b)

I think my problem is exercise62Helper (head b) as I am only checking the first element of the list instead of all elements in [Tree a].

But I don't understand how I can excactly access them, usally I would access them via tail but its not possible (or I dont know) because the parameter of the function are Tree and not [Tree]

CodePudding user response：

You ca work with concatMap :: Foldable f => (a -> [b]) -> f a -> [b] to map all the elements of b over exercise62Helper, and concatenate the results. Your function also does not require an Eq a type constraint, since regardless whether you can check if two items are equal, you can make a list of these items:

exercise62Helper :: Tree a -> [a]
exercise62Helper (Leaf a) = [a]
exercise62Helper (Node a b) = a : concatMap exercise62Helper b

You can also work with the DeriveFoldable extension, and let Haskell generate a trivial instance of Foldable for your type:

{-# LANGUAGE DeriveFoldable #-}

data Tree a = Node a [Tree a] | Leaf a deriving Foldable

the exercise62Helper is then a special version of toList :: Foldable f => f a -> [a]:

import Data.Foldable(toList)

exercise62Helper :: Tree a -> [a]
exercise62Helper = toList