I tried the following code but I 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
CodePudding user response:
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
CodePudding user response:
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 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 to "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 file add
{-# LANGUAGE NoMonomorphismRestriction #-}
at the very top.