Sum of tree in haskell

Question

I tried the following code but I get an error that a is not matched with the expected type "Integer".

data Tree a = Tip | Bin (Tree a) a (Tree a)

sumTree :: Num a => Tree a -> a

sumTotal = 0
sumTree Tip = 0
sumTree (Bin l a r) = (sumTotal+ a)+ sumTree l + sumTree 

Answer 1

In Haskell there are no mutable variables, so sumTotal and sumTotal + make no sense. Normally in Haskell one makes use of recursion as mechanism to visit the items in the tree. You thus can implement sumTree as:

sumTree :: Num a => Tree a -> a
sumTree Tip = 0
sumTree (Bin l a r) = a + sumTree l + sumTree r

For a tree with two levels, this will thus perform recursion on the left and right subtrees. For a tree like Bin (Bin Tip 1 (Bin Tip 4 Tip)) 2 (Bin Tip 5 Tip) this will thus evaluate this as:

   sumTree Bin (Bin Tip 1 (Bin Tip 4 Tip)) 2 (Bin Tip 5 Tip)
 → 2 + sumTree (Bin Tip 1 (Bin Tip 4 Tip)) + sumTree (Bin Tip 5 Tip)
 → 2 + (1 + sumTree Tip + sumTree (Bin Tip 4 Tip)) + sumTree (Bin Tip 5 Tip)
 → 2 + (1 + 0 + (4 + sumTree Tip + sumTree Tip)) + sumTree (Bin Tip 5 Tip)
 → 2 + (1 + 0 + (4 + 0 + sumTree Tip)) + sumTree (Bin Tip 5 Tip)
 → 2 + (1 + 0 + (4 + 0 + 0)) + sumTree (Bin Tip 5 Tip)
 → 2 + (1 + 0 + 4) + sumTree (Bin Tip 5 Tip)
 → 2 + 5 + sumTree (Bin Tip 5 Tip)
 → 2 + 5 + (5 + sumTree Tip + sumTree Tip)
 → 2 + 5 + (5 + 0 + sumTree Tip)
 → 2 + 5 + (5 + 0 + 0)
 → 2 + 5 + 5
 → 7 + 5
 → 12

You can also make Tree an instance of Foldable with the DeriveFoldable extension [ghc-doc] (or by implementing the Foldable instance yourself). In that case sumTree is just a special case of sum :: (Foldable f, Num a) => f a -> a:

{-# LANGUAGE DeriveFoldable #-}

data Tree a = Tip | Bin (Tree a) a (Tree a) deriving Foldable

sumTree :: Num a => Tree a -> a
sumTree = sum

Answer 2

The error is caused by the reference to sumTotal which gets a monomorphic type while being used in the polymorphic function sumTree.

You also have a copy-paste typo in the post, in

sumTree (Bin l a r) = (sumTotal+ a)+ sumTree l + sumTree

but you actually must have

sumTree (Bin l a r) = (sumTotal+ a)+ sumTree l + sumTree r

in your code or else you'd be getting a different error.

---

But sumTotal is actually not needed at all, as it is always 0, so it changes nothing. You can just remove it altogether from everywhere, and when you do, the error will go away, and the function will just work.

But adding 0 shouldn't hurt, you ask? Right, but with the restriction, the variable sumTotal gets a monomorphic i.e. specific type, like Integer. And your function sumTree is declared polymorphic, so stays that way. Adding a fixed type value to a flexible type value makes no sense.

In Haskell there are no type casts changing a value at run-time. All types are known in advance. When we add two "flexible", polymorphic type values together, the result is the same type, so when it is actually decided what specifically that type will be, it will be assigned to all three occurrences in unison. But when you use a specific type from the get go in one of them, you prevent that synchronicity.

But still, adding 0 shouldn't break things, you say. What could be done to avoid the error without changing the code?

For that, you need to disable the monomorphism restriction.

In GHCi, use

> :set -XNoMonomorphismRestriction

and then enter your definitions anew, in multi-line input mode, with :{ and :} commands.

Or in your source code file add

{-# LANGUAGE NoMonomorphismRestriction #-}

at the very top.