I have the following definition of a binary tree and a function that fetches the leftmost element, or return Nothing if the tree is an Empty tree, however it is saying x
(with type a
) is an infinite type because it returns Maybe a
?
Thanks any help would be appreciated :)
data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Eq)
leftistElement :: (Ord a) => Tree a -> Maybe a
leftistElement EmptyTree = Nothing
leftistElement (Node x left _) =
if left == EmptyTree
then x
else leftistElement left
types.hs:55:10: error:
• Occurs check: cannot construct the infinite type: a ~ Maybe a
• In the expression: x
In the expression:
if left == EmptyTree then x else leftistElement left
In an equation for ‘leftistElement’:
leftistElement (Node x left _)
= if left == EmptyTree then x else leftistElement left
• Relevant bindings include
left :: Tree a (bound at types.hs:53:24)
x :: a (bound at types.hs:53:22)
leftistElement :: Tree a -> Maybe a (bound at types.hs:52:1)
|
55 | then x
| ^
Failed, no modules loaded.
CodePudding user response:
x
has type a
, but you try to return it as a value of type Maybe a
. Because a
is type variable, though, the type checker attempts to see if there is some instance of Maybe
that makes a
and Maybe a
unify, which leads to the infinite-type error.
Use pure
(or Just
) to return a value of the correct type.
leftistElement (Node x left _) =
if left == EmptyTree
then pure x
else leftistElement left