Haskell Typeclass Composition

Question

Let's say I want to write a Sudoku solver with some representational abstraction using typeclasses. So I'd like to make a typeclass for the row and the matrix:

{-# LANGUAGE FlexibleInstances #-}

class Row r where
  (!) :: r -> Int -> Int

class Sudoku a where
  row :: (Row r) => Int -> a -> r

Obviously, I would add more, but just these functions are enough to get me in trouble. Now let's say I want to implement this with nested lists. Trying:

instance Row r => Sudoku [r] where
  row n s = s !! (n - 1)

lands me in hot water:

Couldn't match expected type `r1' against inferred type `r'
  `r1' is a rigid type variable bound by
       the type signature for `row' at 96b.hs:7:14
  `r' is a rigid type variable bound by
      the instance declaration at 96b.hs:12:13
In the expression: s !! (n - 1)
In the definition of `row': row n s = s !! (n - 1)
In the instance declaration for `Sudoku [r]'

A second stab with:

instance Row [Int] where
  r ! n = r !! (n - 1)

instance Sudoku [[Int]] where
  row n s = s !! (n - 1)

fares no better:

Couldn't match expected type `r' against inferred type `[Int]'
  `r' is a rigid type variable bound by
      the type signature for `row' at 96b.hs:8:14
In the expression: s !! (n - 1)
In the definition of `row': row n s = s !! (n - 1)
In the instance declaration for `Sudoku [[Int]]'

I appear to be missing something. What's the proper way of modelling a simple scenario like this?

Answer 1

Your Sudoku class does not indicate any relationship between a and r. It is currently saying that if you have a sudoku, you can get any type of row from it. Your instances only show how to get one specific type of row from a sudoku, so that doesn't meet the requirement that any row type should work.

There are two common ways to solve this. One way is to use type families to relate the row type to the sudoku type:

{-# LANGUAGE TypeFamilies, FlexibleInstances #-}

class Sudoku a where
    type RowType a :: *
    row :: Int -> a -> RowType a

instance Row r => Sudoku [r] where
    type RowType [r] = r
    row n s = s !! (n - 1)

You can also obtain the same result by using functional dependencies. We then add the row type as an additional parameter to the Sudoku class, and indicate the relationship that the sudoku determines the row type by using a functional dependency | a -> r:

{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies,
             FlexibleInstances #-}

class Row r where
  (!) :: r -> Int -> Int

instance Row [Int] where
  r ! n = r !! (n - 1)

class Sudoku a r | a -> r where
    row :: (Row r) => Int -> a -> r

instance Row r => Sudoku [r] r where
    row n s = s !! (n - 1)