Блог

Допустим, я хочу написать решатель судоку с некоторой репрезентативной абстракцией, используя классы типов. Итак, я хотел бы создать класс типов для строки и матрицы:

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

Кажется, я чего-то не понимаю. Каков правильный способ моделирования такого простого сценария, как этот?

Ваш Sudoku класс не указывает на какую-либо связь между a и r . В настоящее время говорится, что если у вас есть судоку, вы можете получить из него строку любого типа. Ваши экземпляры показывают только, как получить один определенный тип строки из sudoku, так что это не соответствует требованию, согласно которому должен работать любой тип строки.

Есть два распространенных способа решить эту проблему. Один из способов — использовать семейства типов, чтобы связать тип строки с типом sudoku:

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