CODEWITHSUNDEEP
haskellfunctional-programmingpolymorphism
Julian
Julian

Reputation: 146

Haskell class with instance of polymorph data definition

I have a question regarding class definition with polymorphic data types. Lets say the defined datatype is:

data BTree a = BLeaf a | BNode a (BTree a) (BTree a) deriving(Show)

Lets say I want to retrieve the value of the root of the tree, but within an instance of a class called Tree:

class Tree a where
             getRoot:: a -> (?)  --<- Type of Leave value as return type

and an instance:

instance Tree (BTree a) where
                        getRoot BLeaf a = a
                        getRoot BNode a _ _ = a

I can't figure out the type of the function (see questionmark), since its not a and the class doesn't know the parameter of the instance.

Upvotes: 1

Views: 152

Answers (2)

Phil Kiener
Phil Kiener

Reputation: 778

First things first, keep in mind that your BTree is a type with kind * -> *, which basically means it needs another type as argument to be created - your a. Because of that, having the type variable of your class called a as well can lead to confusion. Let's exchange that for outer to put it more clearly.

You'd then have:

class Tree outer where
    getRoot :: ???

On to the quest of finding that function's type. Knowing that the tree-type needs another type, we know getRoot must be passed something like BTree Int, which would be outer inner in variables. You want the function to return something which has that inner type, so your class would be:

class Tree outer where
    getRoot :: outer inner -> inner

Now that makes sense! You pass a tree to that function, and it presents you something with that inner type.

You'd then implement your instance as before:

instance Tree (BTree a) where
    getRoot (BLeaf x)     = x
    getRoot (BNode x _ _) = x

Upvotes: 1

castletheperson
castletheperson

Reputation: 33496

Make the type variable in the class Tree declaration refer to a type constructor of kind * -> *, and then you can refer to the type of the values of the tree in the type signature of getRoot.

class Tree t where
    getRoot :: t a -> a

instance Tree BTree where
    getRoot (BLeaf a)     = a
    getRoot (BNode a _ _) = a

Another, slightly more complex solution that allows the tree structure to be of kind * would be to use a multi-parameter type class along with functional dependencies.

{-# LANGUAGE FunctionalDependencies, FlexibleInstances #-}

class Tree t a | t -> a where
    getRoot :: t -> a

instance Tree (BTree a) a where
    getRoot (BLeaf a)     = a
    getRoot (BNode a _ _) = a

Or you could use a type family.

{-# LANGUAGE TypeFamilies #-}

class Tree t where
    type Value t
    getRoot :: t -> Value t

instance Tree (BTree a) where
    type Value (BTree a) = a
    getRoot (BLeaf a)     = a
    getRoot (BNode a _ _) = a

Upvotes: 6

Related Questions