Есть ли в Haskell какой-либо способ выразить, что тип должен быть экземпляром класса типов более чем одним способом?

(Заранее извините, если вопрос глупый или очевидный - у меня нет большого опыта работы с Haskell).

Есть ли способ выразить, что тип должен быть экземпляром класса типов более чем одним способом? Лучше всего это проиллюстрировано на примере (который, вероятно, несколько глуп): в математике мы можем сказать, что полукольцо - это набор, который является коммутативным моноидом при выполнении одной операции (которую мы назовем сложением, тождество 0), и моноидом при выполнении одной операции. другой (который мы назовем умножением) наряду с требованиями, которые умножение распределяет по сложению и что 0 аннигилирует все элементы при умножении. Последние части здесь не важны.

Предположим теперь, что у меня есть класс типов Monoid (не путать с Data.Monoid),

class Monoid m where
    unit :: m 
    operation :: m -> m -> m

и хотел бы создать класс типов Semiring. Из определения, данного выше, я хотел бы сказать, что «если тип r является моноидом двумя (различными) способами, мы назовем его полукольцом». Так что я бы хотел что-то вроде

class (Monoid r, Monoid r) => Semiring r where ...

что, конечно, не работает. По общему признанию, пример становится немного странным, поскольку больше нет функций, которые мы хотели бы требовать для полуколец, поэтому класс типов будет пуст, но я надеюсь, что он иллюстрирует то, о чем я спрашиваю (или просто притворимся, что нам нужна какая-то функция f:r->r для Semiring r).

Итак, в общих настройках я спрашиваю: с учетом класса типов A, есть ли способ параметризовать класс типов B a с требованием, чтобы a был экземпляром A двумя способами (это означает, что a должен реализовывать функции, указанные в A двумя способами)?


typeclass haskell
person gspr    schedule 22.10.2010    source источник
comment
Спасибо всем, кто ответил на данный момент. Практически любой из ответов мог быть принят, но я выбрал тот, который набрал наибольшее количество голосов.   -  person gspr    schedule 23.10.2010

Ответы (5)


arrow_upward
12
arrow_downward

Один из вариантов - определить свои собственные моноиды для двух операций полукольца:

class AdditiveMonoid m where
    zero :: m
    (<+>) :: m -> m -> m

class MultiplicativeMonoid m where
    one :: m
    (<*>) :: m -> m -> m

а затем объедините их:

class (MultiplicativeMonoid m, AdditiveMonoid m) => Semiring m

Проблема в том, что вы не можете выразить моноидные законы или тот факт, что одна операция коммутативна. Лучшее, что вы можете получить, - это определить свойства быстрой проверки для законов.

Для вдохновения посмотрите числовую прелюдию и этот документ.

person Daniel    schedule 22.10.2010
comment
Большое спасибо! Кажется, короткий ответ - нет, тогда вам нужно продублировать код? Я знаю о числовой прелюдии, но она настолько масштабна, что может быть трудно извлечь из нее урок, когда вы новичок. Эта статья кажется очень интересной, спасибо! - person gspr; 23.10.2010

arrow_upward
7
arrow_downward

В частности, для Monoid это делается с помощью оберток типов. Если вы посмотрите в модуль Data.Monoid, вы найдете две разные моноидальные структуры для Bool значений: Any и All, а также две разные структуры для типов, реализующих Num: Sum и Product, и две структуры для типов Maybe: First и Last.

Однако вы столкнетесь с проблемами с вашим примером полукольца, поскольку моноидальные структуры для Sum и Product обе предоставляют реализации mempty (версия Haskell вашего unit) и mappend (версия Haskell вашего operation).

person Mikael Vejdemo-Johansson    schedule 22.10.2010
comment
Хм ... спасибо за информацию, но похоже, что ответ сводится к отрицательному? Это позор :-( - person gspr; 22.10.2010

arrow_upward
5
arrow_downward

В других ответах упоминались newtype оболочки, но не было дано явное решение с их использованием:

-- export these newtypes from the module defining Semiring
newtype Add a = Add a
newtype Multiply a = Multiply a

class (Monoid (Add a), Monoid (Multiply a)) => Semiring a where
  -- empty

instance Monoid (Add Integer) where
  unit = Add 0
  Add a `operation` Add b = Add (a + b)

-- etc.

Вам понадобятся некоторые расширения GHC, например FlexibleContexts.

person Reid Barton    schedule 23.10.2010
comment
Спасибо за явный пример кода. Это делает все намного яснее. Хотя, как бы то ни было, у меня осталось ощущение, что меня часто путает, когда нужно создавать классы типов, а когда - типы. Фактически, чтобы решить эту проблему, я сам создал классы типов Additive и Multiplicative. Ваш способ кажется более приятным, но это означает, что я неправильно понимаю взаимосвязь между классами типов и типами. Может, задам еще вопрос :-) - person gspr; 23.10.2010

arrow_upward
3
arrow_downward

См. Также сообщение Конора Макбрайда в "ритм-секции": http://www.haskell.org/pipermail/libraries/2008-January/008917.html, хотя это на уровне значений и не помогает с классами типов.

Библиотека Monoids Кметта (до того, как он удалил материал Ring) реализовала нечто похожее на подход Дэниела Велкова: http://hackage.haskell.org/package/monoids-0.1.36

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

person sclv    schedule 22.10.2010

arrow_upward
2
arrow_downward

Обычным методом для этого является, как упоминается в других ответах, обертки newtype. Во многих случаях это кажется мне чем-то вроде злоупотребления концепцией типового класса. Классы типов - это логические «аксиомы», которые утверждают, что некоторый факт является истинным для типа; например, может быть, это монада, или что Int - это число, или что списки упорядочены, как и их элементы. Часто, как в случае с Eq и Ord, есть другие разумные определения, но выбранные в некотором роде «канонические». В других случаях, как в случае с Monoid, нет.

В случае Monoid и других подобных высоко абстрактных структур я считаю, что объявление data было бы более полезным. Например, data Monoid a = Monoid {mempty :: a ; mappend :: a -> a -> a}. Затем у нас есть addition :: Num a => Monoid a, liftMaybe :: Monoid a -> Monoid (Maybe a) и т. Д.

Эту же технику можно использовать для реализации вашего Semiring. Например (с использованием типа данных Monoid, как и раньше): data Semiring a = Semiring { addition, multiplication :: Monoid a }.

person mokus    schedule 22.10.2010
comment
Фактически, если я правильно понимаю, это в основном то, что GHC делает под капотом для реализации полиморфизма классов типов. Однако я не уверен в преимуществах кода пользовательского уровня. - person Antal Spector-Zabusky; 23.10.2010