Haskell类型组合

Question

假设我想使用类型类编写一个带有一些表示抽象的数独求解器.所以我想为行和矩阵创建一个类型类:

{-# LANGUAGE FlexibleInstances #-}

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

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

显然,我会添加更多,但只是这些功能足以让我遇到麻烦.现在让我们说我想用嵌套列表来实现它.试:

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

让我在热水中:

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]'

第二次刺伤:

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

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

票价不错:

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]]'

我似乎错过了一些东西.建模像这样的简单场景的正确方法是什么？

Answer 1

你的Sudoku班级没有表明a和之间有任何关系r.它目前说如果你有一个数独,你可以从它获得任何类型的行.您的实例仅显示如何从数独中获取一种特定类型的行,因此不符合任何行类型应该起作用的要求.

有两种常见的方法可以解决这个问题.一种方法是使用类型族将行类型与数独类型相关联:

{-# 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)

您还可以使用功能依赖项获得相同的结果.然后,我们将行类型作为附加参数添加到Sudoku类中,并通过使用函数依赖关系指示sudoku确定行类型的关系| 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)