«Сопоставление с образцом» конструкторов данных алгебраического типа - PullRequest
Новая
       34

«Сопоставление с образцом» конструкторов данных алгебраического типа

13 голосов
/ 13 апреля 2010

Давайте рассмотрим тип данных с множеством конструкторов: 

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

Ответы [ 5 ]

14 голосов
/ 13 апреля 2010

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

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

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

10 голосов
/ 13 апреля 2010

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

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

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

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

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

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

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

10 голосов
/ 13 апреля 2010

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

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

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

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

2 голосов
/ 13 апреля 2010

В некоторых случаях библиотека Scrap Your Boilerplate поможет.

http://www.haskell.org/haskellwiki/Scrap_your_boilerplate

1 голос
/ 14 апреля 2010

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

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

...