Haskell and multi-parameter models

Question

I have a simple problem when it comes to writing cool classes that inherit from each other. I am trying to create a hierarchy of class types in order to achieve a certain level of abstract abstraction. Let me say that I need a collection collection class:

{-# LANGUAGE MultiParamTypeClasses #-} {-# LANGUAGE FlexibleInstances #-} class Collection ca where isMember :: a -> c -> Bool 

And I determined the type of tree:

 data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show, Eq) 

I want to make my tree a collection, so:

 inOrder :: Tree a -> [a] inOrder Empty = [] inOrder (Node alr) = (inOrder l) ++ [a] ++ (inOrder r) instance (Eq a) => Collection (Tree a) a where isMember ac = a `elem` (inOrder c) 

This is not entirely correct:

 *Main> (isMember '2' Empty) <interactive>:1:1: No instance for (Collection (Tree a) Char) arising from a use of `isMember' at <interactive>:1:1-18 Possible fix: add an instance declaration for (Collection (Tree a) Char) In the expression: (isMember '2' Empty) In the definition of `it': it = (isMember '2' Empty) 

Presumably, the value of typeclass would be lost if I had to create an implementation for each particular type. Therefore, I am not writing the instance declaration correctly. But I can’t understand how to act.

Answer 1

The problem is that by default each parameter of a type class is independent of the others. Just applying isMember to Char , and a tree of an unknown element type is not enough to allow it to infer that it should use a (seemingly obvious) instance.

This is clearly not how you want it to work, and a bit silly to download, but it is how it works. To solve this problem, you need to give it a connection method for which other extensions exist: FunctionalDependencies is more common, and TypeFamilies is newer and much nicer to use, but still has some rough edges.

With functional dependencies, you must indicate that a subset of the parameters of a class of a type fully defines others, for example. Collection ca | c -> a Collection ca | c -> a . It has its pitfalls, but in many cases it works quite well.

With type types, you are likely to reduce this to a class with one parameter associated with the element type, for example:

 class Collection c where type Elem c isMember :: Elem c -> c -> Bool 

Answer 2

You need to add a functional dependency to indicate that the type of container determines the type of element:

 {-# LANGUAGE FunctionalDependencies #-} class Collection ca | c -> a where ... 

There are other ways to do this, for example, using type families, but I think this is the easiest solution in this case.

Answer 3

The problem is that the Empty type is Tree a , and ghc does not have enough information to know that you want a be Char in this case. If you manually specify the type, it will work:

 isMember '2' (Empty::Tree Char) 

The reason ghc cannot be that a should be Char , since theoretically you could have one Collection (Tree Char) Char instance and another Collection (Tree Int) Char . In this case, there would be no way to conclude which one should be used if you did not specify this explicitly.