"Согласование шаблонов" конструкторов данных алгебраического типа

Рассмотрим тип данных со многими конструкторами:

data T = Alpha Int | Beta Int | Gamma Int Int | Delta Int

Я хочу написать функцию, чтобы проверить, производятся ли два значения с одним и тем же конструктором:

sameK (Alpha _) (Alpha _) = True
sameK (Beta _) (Beta _) = True
sameK (Gamma _ _) (Gamma _ _) = True
sameK _ _ = False

Поддержание sameK не очень забавно, оно не может быть легко проверено на правильность. Например, когда новые конструкторы добавляются в T, легко забыть обновить sameK. Я пропустил одну строку, чтобы привести пример:

-- it’s easy to forget:
-- sameK (Delta _) (Delta _) = True

Вопрос в том, как избежать шаблона в sameK? Или как убедиться, что он проверяет все конструкторы T?

Обходной путь, который я нашел, - использовать отдельные типы данных для каждого из конструкторов, вызывая Data.Typeable и объявляя общий тип класса, но мне не нравится это решение, потому что оно гораздо менее читаемо и в противном случае просто для меня работает простой алгебраический тип:

{-# LANGUAGE DeriveDataTypeable #-}

import Data.Typeable

class Tlike t where
  value :: t -> t
  value = id

data Alpha = Alpha Int deriving Typeable
data Beta = Beta Int deriving Typeable
data Gamma = Gamma Int Int deriving Typeable
data Delta = Delta Int deriving Typeable

instance Tlike Alpha
instance Tlike Beta
instance Tlike Gamma
instance Tlike Delta

sameK :: (Tlike t, Typeable t, Tlike t', Typeable t') => t -> t' -> Bool
sameK a b = typeOf a == typeOf b

Ответы

Ответ 1

Посмотрите на модуль Data.Data, в частности, на функцию toConstr. Наряду с {-# LANGUAGE DeriveDataTypeable #-}, вы получите однострочное решение, которое работает для любого типа, являющегося экземпляром Data.Data. Вам не нужно определять все SYB!

Если по какой-то причине (застряли с Hugs?), это не вариант, то вот очень уродливый и очень медленный взлом. Он работает только в том случае, если ваш тип данных Show способен (например, с помощью deriving (Show) - это означает, что не существует типов функций внутри, например).

constrT :: T -> String
constrT = head . words . show
sameK x y = constrT x == constrT y

constrT получает строковое представление внешнего конструктора значения T, показывая его, разбивая его на слова и затем получая первый. Я даю явную подпись типа, поэтому у вас не возникает соблазна использовать ее на других типах (и уклоняться от ограничения мономорфизма).

Некоторые заметные недостатки:

  • Это разрушает ужасно, когда ваш тип имеет конструкторы infix (например, data T2 = Eta Int | T2 :^: T2)
  • Если некоторые из ваших конструкторов имеют общий префикс, это будет медленнее, так как нужно сравнить большую часть строк.
  • Не работает с типами с пользовательским Show, например, со многими типами библиотек.

Тем не менее, это Haskell 98... но это единственная приятная вещь, которую я могу сказать об этом!

Ответ 2

Другой возможный способ:

sameK x y = f x == f y
  where f (Alpha _)   = 0
        f (Beta _)    = 1
        f (Gamma _ _) = 2
        -- runtime error when Delta value encountered

Ошибка выполнения не идеальна, но лучше, чем молча давать неверный ответ.

Ответ 3

Вам понадобится использовать универсальную библиотеку, такую ​​как Scrap Your Boilerplate или uniplate, чтобы сделать это в целом.

Если вы не хотите быть таким сильным, вы можете использовать решение Dave Hinton вместе с пустым ярлыком:

...
where f (Alpha {}) = 0
      f (Beta {}) = 1
      f (Gamma {}) = 2

Значит, вам не нужно знать, сколько аргументов у каждого конструктора. Но он, очевидно, все еще оставляет желать лучшего.

Ответ 5

Вы можете определенно использовать дженерики для устранения шаблона. Ваш код - пример учебника, почему я (и многие другие никогда не используют подстановочный знак _ на верхнем уровне). Хотя утомительно записывать все случаи, это менее утомительно, чем иметь дело с ошибками.

В этом счастливом примере я бы не только использовал решение Дэйва Хинтона, но и ударил прагму INLINE для вспомогательной функции f.