CODEWITHSUNDEEP
haskell
Anton Sherstiuk
Anton Sherstiuk

Reputation: 11

Getting a „Couldn't match type ‘a’ with ‘[a]’...“ error

I'm a Haskell beginner and I'm having a trouble with this piece of code. The task is to make a BFS function for the given data type. I've tried many variations, but the problem essentially remains the same: type mismatch.

data OrdTree a = OrdTree a [OrdTree a] 
             deriving (Show)

root :: OrdTree a -> a
root (OrdTree x _) = x

children :: OrdTree a -> [OrdTree a]
children (OrdTree _ x) = x

bfsTreeList ::  OrdTree a ->  [a]
bfsTreeList ot = (map root [ot]) ++ (map bfsTreeList (children ot))

DFS seems to work just fine:

dfsTreeList ::  OrdTree a ->  [a]
dfsTreeList ot = root ot : concat (map dfsTreeList (sons ot))

Upvotes: 0

Views: 124

Answers (1)

dkasak
dkasak

Reputation: 2703

Try thinking in terms of levels of the tree. What is a level? It is a list of subtrees.

type Level a = [OrdTree a]

Next you'll need a function that, given a level, produces the next level. You may find the function concatMap useful here but it is not strictly necessary.

nextLevel :: Level a -> Level a
nextLevel = ...

After you have this, you'll want a function that, given a tree, produces a list of its levels. This will probably be an infinite list (since the next level of an empty level is again an empty level), but after a certain point it will only be populated with empty levels. Here you might find the function iterate useful.

levels :: OrdTree a -> [Level a]
levels = ...

Finally, you're able to construct your bfsTreeList function using these pieces. You'll produce a list of levels from your tree using levels, then you'll cut off the portion that only contains empty levels making the list finite, then you'll concatenate the list and retrieve the values stored:

bfsTreeList :: OrdTree a -> [a]
bfsTreeList = map root . concat . takeWhile (not . null) . levels

Here's an example tree you can use as a test case:

exampleTree :: OrdTree Int
exampleTree = OrdTree 1 [ OrdTree 2 [ OrdTree 5 []
                                    , OrdTree 6 []]
                        , OrdTree 3 [ OrdTree 7 []
                                    , OrdTree 8 [OrdTree 9 []]]
                        , OrdTree 4 []]

The result should look like this:

λ. bfsTreeList exampleTree 
[1,2,3,4,5,6,7,8,9]

Upvotes: 1

Related Questions