#haskell
#хаскелл #haskell
Вопрос:
Допустим, я хочу написать решатель судоку с некоторой репрезентативной абстракцией, используя классы типов. Итак, я хотел бы создать класс типов для строки и матрицы:
{-# 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]]'
Кажется, я чего-то не понимаю. Каков правильный способ моделирования такого простого сценария, как этот?
Ответ №1:
Ваш 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)
Комментарии:
1. @hammar. Хороший ответ. Вы знаете, возможно ли указать ограничения класса для семейств типов? Другими словами, чтобы сказать, что для
Sudoku a
,RowType a
должен быть экземплярRow
?2. @Lambdageek Ты мог бы написать
row :: Row (RowType a) => Int -> a -> RowType a
, IIRC3. @hammar. Спасибо, это объяснение отличное. Я понимаю, как мой второй пример (instance Sudoku [[Int]]) указывает конкретный экземпляр Row и, таким образом, не соответствует контракту класса типов Sudoku. Но я изо всех сил пытаюсь понять проблему с первым экземпляром. Для меня это говорит о чем-то вроде судоку — это список строк, и функция row просто извлекает индекс из этого списка. Может быть, проблема в том, что в качестве экземпляра он вообще ничего не говорит о типе строки?
4.@Ara: В вашем определении класса сказано, что если у меня есть список строк
Row r => [r]
для некоторого типа строкиr
, я могу получитьRow r2 => r2
для любого типа строки r2, поскольку в определении класса между ними нет зависимости. Ваш экземпляр показывает только, как получить строку того же типа, поэтому он менее полиморфен, чем требуется.5. @FUZxxl: Правильно, я просто выяснял, как это сделать . Я не думаю, что есть способ установить ограничение непосредственно на связанный тип?