Эмпирические правила для ограничений типа.

  • Предпочитайте манипулировать данными через интерфейсы, а не напрямую.
  • Если один класс типов может реализовать второй класс типов, первый класс типов является подтипом второго.

В какой-то момент мне нужно было реализовать простую структуру стека в Haskell:

import Data.List
type Stack a = [a]
push :: a -> Stack a -> Stack a
push = (:)
pop :: Stack a -> Maybe (a, Stack a)
pop = uncons

Красиво и просто. Впоследствии мне нужно было реализовать стек где-то еще, используя другую структуру данных. В интересах повторного использования и простоты кода я решил реализовать интерфейс:

import Data.List
class Stack s where
    push :: a -> s a -> s a
    pop :: s a -> Maybe (a, s a)
instance Stack [] where
    push = (:)
    pop = uncons

Который лишь немного длиннее оригинала, всего с одной дополнительной строкой кода. Обычно лучше реализовать интерфейс и использовать его вместо прямого использования структуры данных. Мы получаем следующие преимущества:

  • Повторное использование кода для всех членов класса типов.
  • Меньше способов написать некорректную программу, если мы можем взаимодействовать со структурой данных только через ее интерфейс.
  • Меньше загрязнения пространства имен.
  • Только чуть дольше.

Теперь мы можем реализовать второй экземпляр (или больше).

data Deque a = Deque [a] [a]
instance Stack Deque where
    push y (Deque xs ys) = Deque xs (y: ys)
    pop (Deque [] []) = Nothing
    pop (Deque xs (y: ys)) = Just (y, Deque xs ys)
    pop (Deque xs []) = pop (Deque [] (reverse xs))

Реализация не важна, можно с уверенностью сказать, что она ведет себя как стек.

Я также хотел свернуть структуры стека. Для этого нам нужно реализовать Foldable для всех членов Stack. Минимальное полное определение для Foldable — foldr. Пример реализации foldr может быть следующим:

foldrStack :: Stack s => (a -> b -> b) -> b -> s a -> b
foldrStack f z s = case pop s of
    Nothing -> z
    Just (x, s') ->  x `f` (foldrStack f z s')

Что работает для любого типа Stack. Моей первоначальной мыслью было автоматически реализовать foldr для каждого члена Stack автоматически:

-- Error.
instance (Stack a) => Foldable a where
    foldr = foldrStack

Что не работает. Если бы это сработало, мы могли бы сделать следующее:

instance (Stack a) => Foldable a where
    -- code
instance (OtherClass a) => Foldable a where
    -- code

Если у нас есть что-то, что содержит как экземпляры Stack, так и OtherClass, компилятор не сможет узнать, какую версию Foldable использовать.

Мы знаем, что каждый экземпляр Stack может также реализовать Foldable, потому что мы можем написать для него реализацию по умолчанию. Поэтому мы должны изменить наше определение класса типов Stack:

-- make `Foldable` a prerequisite for `Stack`.
class (Foldable s) => Stack s where
    push :: a -> s a -> s a
    pop :: s a -> Maybe (a, s a)
instance Foldable Deque where
    foldr = foldrStack
-- Any other type of `Stack` can implement `Foldable` easily.
instance Foldable OtherStack where
    foldr = foldrStack

Единственным недостатком сейчас является то, что мы должны вручную реализовать Foldable для каждого члена Stack. С нашей реализацией по умолчанию это обычно довольно легко сделать.

Резюме

  • Старайтесь не писать функции для структур данных напрямую, вместо этого попробуйте получить к ним доступ через интерфейс. Таким образом, мы можем повторно использовать функции в нескольких экземплярах.
  • Если вы можете написать реализацию по умолчанию для одного класса типов, используя функции из другого класса типов, сделайте ее ограничением типа. (например, мы можем сделать реализацию по умолчанию для Foldable, используя функции из Stack, поэтому мы делаем Foldable ограничением типа).

Первоначально опубликовано на https://andymac-2.github.io/notepad/