Haskell Typeclass Composition

Question

Let's say I want to write a Sudoku solution with some representative abstraction using typeclasses. So I would like to make typeclass for row and 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 these functions are enough for me to have problems. Now let's say that I want to implement this using nested lists. Attempt:

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

lands 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 ns = s !! (n - 1) In the instance declaration for `Sudoku [r]' 

Second hit with:

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

tariffs are not 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 ns = s !! (n - 1) In the instance declaration for `Sudoku [[Int]]' 

Something seems to be missing. What is the correct way to simulate a simple scenario like this?

Answer 1

Your Sudoku class does not indicate any relationship between a and r . It is currently said that if you have sudoku, you can get any type of string from it. Your instances show how to get one particular string type from sudoku, so this does not meet the requirement that any string type work.

There are two general ways to solve this problem. One way is to use type types to bind a string type to a 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 ns = s !! (n - 1) 

You can also get the same result using functional dependencies . Then we add the string type as an additional parameter to the Sudoku class and specify the relation that sudoku determines the string type using the functional dependency | a -> r | a -> r :

 {-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies, FlexibleInstances #-} class Row r where (!) :: r -> Int -> Int instance Row [Int] where r ! n = r !! (n - 1) class Sudoku ar | a -> r where row :: (Row r) => Int -> a -> r instance Row r => Sudoku [r] r where row ns = s !! (n - 1)