List of custom type and instance of class

Question

Hi,

I'm playing around in Haskell to try and get the hang of it. I'm running into problems with my typeclasses. What I'm trying to do is to make a generalized a* module by defining classes and methods and then I'm trying to use those in a program. My problem is that when I try to make a list of my Box data types an instance of my Board class (that represents the map) I'm getting the following error:

Illegal instance declaration for `Board [Box]'
    (All instance types must be of the form (T a1 ... an)
     where a1 ... an are type *variables*,
     and each type variable appears at most once in the instance head.
     Use -XFlexibleInstances if you want to disable this.)
In the instance declaration for `Board [Box]'

I've been googling around for a solution to this but so far I've only found one page which describes a solution which I just can't understand here: http://www.haskell.org/haskellwiki/List_instance. It describes how to use the XFlexibleInstances generated from the error message above, however, when I try that I get an error message when I try to use one element of the list as a Box data type.

Couldn't match expected type `t' against inferred type `Box'
  `t' is a rigid type variable bound by
      the type signature for `!!' at <no location info>

I don't know if this is some weird mistake I'm making or if my design simply wasn't a good one. The relevant code is here:

class Tile a where
  tilePosition :: a -> (Int, Int)
  tileStatus   :: a -> Status

The board class should be a list of tiles (or some collection of them)

class Board b where
  surroundingTiles :: Tile t => b -> (Int, Int) -> [t]
  startingPosition :: b -> Maybe (Int, Int)
  targetPosition   :: b -> Maybe (Int, Int)
  (!!)             :: Tile t => b -> (Int, Int) -> Maybe t

This seems to compile, but in another file where I try to make instances of these classes is where I'm getting the errors

instance Board [Box] where
  boxes !! pos  = foldl (\acc b -> if boardPos b == pos then Just b else acc) Nothing boxes
  ...

Any hints in the right direction would be appreciated.

Answer 1

For [Box] the function !! must have type Tile t => [Box] -> (Int, Int) -> Maybe t, meaning for each type t which is an instance of Tile you need to be able to get a t out of a [Box].

However your implementation has the type [Box] -> (Int, Int) -> Maybe Box, which means you can only get a Box out of a [Box], so that does not work.

What you could do to get what you want is something like this:

class Board b where
  surroundingTiles :: Tile t => b t -> (Int, Int) -> [t]
  startingPosition :: Tile t => b t -> Maybe (Int, Int)
  targetPosition   :: Tile t => b t -> Maybe (Int, Int)
  (!!)             :: Tile t => b t -> (Int, Int) -> Maybe t

instance Board [] where
  ...

This way you can use lists of any instance of Tile as Boards (lists of anything else are also Boards, but you can't use them as such because all the functions require t to be an instance of Tile).

If you need to say "A list of Tiles is a Board of Tiles" without also making all other lists into Boards, you need to enable multi-parameter typeclasses which allow you to say things like:

class Tile t => Board b t where
  surroundingTiles :: b t -> (Int, Int) -> [t]
  startingPosition :: b t -> Maybe (Int, Int)
  targetPosition   :: b t -> Maybe (Int, Int)
  (!!)             :: b t -> (Int, Int) -> Maybe t

instance Board [Tile] Tile where
  ...