Couldn't match expected type `Int' with actual type `a'

Question

import Data.List

data Tree a = Leaf a | Node (Tree a) a (Tree a) deriving Show

toTree :: Ord a => [a] -> Tree a
toTree xs = Node (balancedTree (take n xs')) (xs'!!n) (balancedTree (drop n xs'))
    where 
        xs' = sort xs
        n = middle xs

middle :: Num a => [a] -> a
middle xs = fromIntegral ((length xs `div` 2) + 1)

balancedTree :: Ord a => [a] -> Tree a
balancedTree (x:[]) = Leaf x
balancedTree xs = Node (balancedTree (take n xs')) (xs'!!n) (balancedTree (drop n xs'))
    where 
        xs' = sort xs
        n = middle xs

This is my code for converting from a list to a binary tree. I know there are many mistakes but I just want to get the types errors sorted before I start debugging. I get the following errors in both the "toTree" method and the "balancedTree" method as they are both really the same and will be condensed into one when the errors are sorted out.

ex7.hs:6:38: error:
    * Couldn't match expected type `Int' with actual type `a'
      `a' is a rigid type variable bound by
        the type signature for:
          toTree :: forall a. Ord a => [a] -> Tree a
        at ex7.hs:5:1-32
    * In the first argument of `take', namely `n'
      In the first argument of `balancedTree', namely `(take n xs')'
      In the first argument of `Node', namely
        `(balancedTree (take n xs'))'
    * Relevant bindings include
        xs' :: [a] (bound at ex7.hs:8:9)
        n :: a (bound at ex7.hs:9:9)
        xs :: [a] (bound at ex7.hs:6:8)
        toTree :: [a] -> Tree a (bound at ex7.hs:6:1)
  |
6 | toTree xs = Node (balancedTree (take n xs')) (xs'!!n) (balancedTree (drop n xs'))
  |                                      ^

I have tried for hours to fix it by searching stackOverflow but I can't figure it out. The type declaration of "toTree" must stay the same. Also the definition of Tree should stay the same.

My understanding is that "take" required an "Int" and I am giving it an "a". I do not know how I can fix this.

Did you try to read and understand the error message? What is not clear about the error? — Willem Van Onsem
Your tree structure is wrong. It cannot represent a tree with two data items for example. — n. 1.8e9-where's-my-share m.
I recommend starting with a function insert :: Ord a => a -> Tree a -> Tree a. Gets a tree with N items, returns one with N+1 items. Don't muck with sorting and indices. — n. 1.8e9-where's-my-share m.
If you are talking to someone specific, use the @username convention, then they will get a notification. If you were asking me, I mean exactly what I say. Your tree data structure cannot represent a tree with two data items. You want to try and draw such a tree on a piece of paper, and see why it is impossible. — n. 1.8e9-where's-my-share m.

Willem Van Onsem Willem Van Onsem · Accepted Answer · 2019-11-11T15:07:48

The problem is that middle returns an a, not an Int. Indeed:

middle :: Num a => [a] -> a
middle xs = fromIntegral ((length xs `div` 2) + 1)

But in your balancedTree, you use it as if it is an index, and take n, drop n, and !! n require n to be an Int, indeed:

balancedTree :: Ord a => [a] -> Tree a
balancedTree (x:[]) = Leaf x
balancedTree xs = Node (balancedTree (take n xs')) (xs'!!n) (balancedTree (drop n xs'))
    where 
        xs' = sort xs
        n = middle xs

The type signature does not make much sense either. You can calculate the length over any list, not only from lists that consist out of numbers. You thus should construct a function that returns the index in the middle of the list and use that. For example:

middle :: [a] -> Int
middle = (length xs `div` 2) + 1

That being said, using length, etc. is usually not a good idea in Haskell. length requires O(n) time, and furthermore for infinite lists, it will get stuck in an infinite loop. Often if you use functions like length, there is a more elegant solution.

Instead of using a "top-down" approach, it might be better to look at a "bottom-up" approach, where you iterate over the items, and on the fly construct Leafs, and group these together in Nodes until you reach the top.

Couldn't match expected type `Int' with actual type `a'

1 Answers