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.

Answer 1

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.