Haskell class with instance of polymorph data definition

Question

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.

I think you'd have to leave it as a universal. (eg: getRoot :: a -> b, or more explicitly, getRoot :: forall b. a -> b). Unless you know that the data type itself takes a typevariable, you can't really know the internal type. So you don't really have a choice but to just make "b" universally quantified. — Rahul Manne
– Rahul Manne, Commented Dec 15, 2017 at 0:19
Independent of answering this question, it is worth pushing back a bit. Why do you want a type class at all? I suspect you are bringing another language's idioms with you as you learn a new language. If you try to continue that way, you will be fighting the language the whole way. — Daniel Wagner
– Daniel Wagner, Commented Dec 15, 2017 at 3:20

castletheperson · Accepted Answer · 2017-12-15 00:34:32Z

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

Phil Kiener · Accepted Answer · 2017-12-16 13:08:28Z

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

Collectives™ on Stack Overflow

Haskell class with instance of polymorph data definition

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related