[Haskell-cafe] Trying to sort out multiparameter type classes and their instances

[Daniel Fischer]

Am Dienstag 01 Dezember 2009 23:34:46 schrieb Jeremy Fitzhardinge:
> I'm playing around with some types to represent a game board (like Go,
> Chess, Scrabble, etc).
>
> I'm using a type class to represent the basic Board interface, so I can
> change the implementation freely:
>
> class Board b pos piece where
>     -- Update board with piece played at pos
>     play :: b pos piece -> pos -> piece -> b pos piece

So the parameter b of the class is a type constructor taking two types and constructing a 
type from those.
IOW, it's a type constructor of kind (* -> * -> *), like (->) or Either.
(* is the kind of types [Int, Char, Either Bool (), Double -> Rational -> Int, ...]

>     -- Query pos to get piece (Nothing if off board)
>     at :: b pos piece -> pos -> Maybe piece
>     -- Empty board
>     empty :: b pos piece
>
> and a Position on the board is represented thus:
>
> class Position p where
>     up :: p -> p
>     down :: p -> p
>     left :: p -> p
>     right :: p -> p
>
> With a concrete implementation using a tuple:
>
> instance (Enum c,Enum r) => Position (c,r) where
>     up = second pred
>     down = second succ
>     left = first pred
>     right = first succ
>
>
> My initial Board is a function: position -> Maybe piece, but I'm having
> a hard time writing the instance for it.  My first attempt is:
>
> instance Board (pos -> Maybe piece) pos piece where
>     empty = \_ -> Nothing
>     at = ($)
>     play b pos piece = move
>         where move pos' | pos' == pos = Just piece
>
>                         | otherwise   = b pos'
>
> but ghci complains:
> board.hs:34:15:
>     Kind mis-match
>     Expected kind `* -> * -> *', but `pos -> Maybe piece' has kind `*'
>     In the instance declaration for `Board (pos
>                                             -> Maybe piece) pos piece'
>

Yes, as said above.
(pos -> Maybe piece) is a *type*, but the type class expects a type constructor of kind 
(* -> * ->*) here.

>
> Playing around with parentheses on the instance line got various similar
> messages, but I couldn't get anything to work.
>
> What am I missing here?
>
> One thing that strikes me is that "Board (pos -> Maybe piece) pos piece"
> has a lot of redundancy, and I'm wondering if I'm defining the Board
> type class wrong in the first place.
>
> Given that the "b" type parameter necessarily defines the position and
> pieces, I tried using dependent types:
>
> class Board b | b -> pos, b -> piece where ...

Method 1: The class above, with a modified instance.

newtype Brd pos piec = Brd { mpiece :: pos -> Maybe piece }

instance (Eq pos) => Board Brd pos piece where
    play b pos piece = Brd $ \p -> if p == pos then Just piece else mpiece b pos
    ...

Perhaps not truly satisfying.

Method 2: Multiparameter type class with functional dependencies and suitable kinds

class Board b pos piece | b -> pos, b -> piece where
    play :: b -> pos -> piece -> b
    at :: b -> pos -> Maybe piece
    empty :: b

instance (Eq pos) => Board (pos -> Maybe piece) pos piece where
    play b pos piece = \p -> if p == pos then Just piece else b p
    at = id
    empty = const Nothing

requires {-# LANGUAGE FlexibleInstances #-}

Not necessarily ideal either.

Method 3: Associated type families

{-# LANGUAGE TypeFamilies, FlexibleInstances #-}
module Board where

class Board b where
    type Pos b :: *
    type Piece b :: *
    play :: b -> Pos b -> Piece b -> b
    at :: b -> Pos b -> Maybe (Piece b)
    empty :: b

instance (Eq pos) => Board (pos -> Maybe piece) where
    type Pos (pos -> Maybe piece) = pos
    type Piece (pos -> Maybe piece) = piece
    play b pos piece = \p -> if p == pos then Just piece else b p
    at b p = b p
    empty _ = Nothing

I would try that first.
Choose your pick.