Haskell 类型类组合

Question

假设我想使用类型类进行某种表示抽象来编写数独求解器。因此，我想为行和矩阵创建一个类型类：

```html

假设我想使用类型类进行某种表示抽象来编写数独求解器。因此，我想为行和矩阵创建一个类型类：

```

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

我似乎漏掉了一些东西。如何正确地建模像这样的简单场景？

- Ara Vartanian

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 类中，并使用一个功能依赖 | 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)

- hammar

---

@hammar。很好的回答。您是否知道在类型族上指定类约束是否可能？换句话说，是否可以说对于Sudoku a，RowType a必须是Row的实例？ - Lambdageek

@Lambdageek 你可以写成 row :: Row (RowType a) => Int -> a -> RowType a，如果我没记错的话。 - fuz

@hammar。谢谢你的解释，非常好。我明白了我的第二个例子（instance Sudoku [[Int]]）指定了一个特定的Row实例，因此无法满足Sudoku类型类的合约。但是我仍然不理解第一个实例的问题。对我来说，它表达的是Sudoku是一个Row列表，而row函数只是从该列表中提取索引。也许问题在于作为一个实例，它根本没有说明Row的类型？ - Ara Vartanian

@Ara：你的类定义说，如果我有一列行 Row r => [r]，对于某些行类型 r，我可以获得任何行类型 r2 的 Row r2 => r2，因为在类定义中它们之间没有依赖关系。但是你的实例只展示了如何获取 _相同类型的行_，所以它比要求的多态性要少。 - hammar

@FUZxxl：没错，我只是在琢磨如何实现这个（https://gist.github.com/1019376）。我不知道是否有一种方法可以直接将约束放在关联类型上？ - hammar

@hammar。谢谢！太完美了，现在我懂了。 - Ara Vartanian