Haskell: класс типов против передачи функции

Question

Мне кажется, что вы всегда можете передавать аргументы функции, а не использовать класс типов. Например, вместо определения равенства класса типов:

class Eq a where 
  (==)                  :: a -> a -> Bool

И использование его в других функциях для указания аргумента типа должно быть экземпляром Eq:

elem                    :: (Eq a) => a -> [a] -> Bool

Разве мы не можем просто определить нашу elem функцию без использования класса типов и вместо этого передать аргумент функции, который выполняет работу?

Answer 1

Да. Это называется "стиль передачи словаря". Иногда, когда я делаю какие-то особенно сложные вещи, мне нужно отказаться от класса типов и превратить его в словарь, потому что передача словаря более мощная ¹ , но часто довольно громоздкая, что делает концептуально простой код выглядящим довольно сложным. Я иногда использую стиль передачи словаря в языках, которые не Haskell для имитации классов типов (но я узнал, что это, как правило, не такая хорошая идея, как кажется).

Конечно, когда есть разница в выразительной власти есть компромисс. Несмотря на то, что вы можете использовать данный API-интерфейс несколькими способами, если он написан с использованием DPS, он получает больше информации, если вы не можете. На практике это проявляется в Data.Set, который основан на том факте, что для каждого типа существует только один Ord словарь. Set хранит свои элементы, отсортированные в соответствии с Ord, и если вы строите набор с одним словарем, а затем вставляете элемент с использованием другого, как это было бы возможно с DPS, вы могли бы сломать инвариант Set и заставить его взломать sh. Эту проблему уникальности можно решить, используя фантомный экзистенциальный тип для обозначения словаря, но, опять-таки, ценой довольно неприятной сложности в API. Это также проявляется примерно так же в API Typeable.

Бит уникальности появляется не очень часто. Классы типов хороши в написании кода для вас. Например,

catProcs :: (i -> Maybe String) -> (i -> Maybe String) -> (i -> Maybe String)
catProcs f g = f <> g

, который принимает два «процессора», которые принимают входные данные и могут выдавать выходные данные, и объединяет их, сглаживая Nothing, должен быть записан в DPS примерно так:

catProcs f g = (<>) (funcSemi (maybeSemi listSemi)) f g

По сути, нам снова пришлось прописать тип, в котором мы его используем, хотя мы уже прописали его в сигнатуре типа, и даже это было избыточно, потому что компилятор уже знает все типы. Поскольку существует только один способ создания данного Semigroup для типа, компилятор может сделать это за вас. Это имеет эффект типа «сложный интерес», когда вы начинаете определять множество экземпляров параметризации c и использовать для вычисления структуру ваших типов, как в Data.Functor.* комбинаторах, и это привык к большому эффекту с deriving via, где вы можете по существу получить всю «стандартную» алгебраическую c структуру вашего типа, написанную для вас.

И даже не заводите меня на MPT C и функциях, которые возвращают информацию обратно в проверку типов и вывод. Я никогда не пытался преобразовать такую ​​вещь в DPS - я подозреваю, что это потребовало бы передачи большого количества доказательств равенства типов - но в любом случае я уверен, что это будет намного больше работы для моего мозга, чем мне было бы удобно с.

-

¹ U , если вы не используете reflection, и в этом случае они становятся эквивалентными по мощности - но reflection также может быть громоздким в использовании.

Answer 2

Да. Это (называется передачей словаря) - это то, что компилятор делает с классами типов в любом случае. Для этой функции, выполненной буквально, это будет выглядеть примерно так:

elemBy :: (a -> a -> Bool) -> a -> [a] -> Bool
elemBy _ _ [] = False
elemBy eq x (y:ys) = eq x y || elemBy eq x ys

Вызов elemBy (==) x xs теперь эквивалентен elem x xs. И в этом конкретном c случае вы можете go сделать шаг вперед: eq каждый раз имеет один и тот же первый аргумент, так что вы можете взять на себя ответственность вызывающего абонента за его применение, и в итоге получите:

elemBy2 :: (a -> Bool) -> [a] -> Bool
elemBy2 _ [] = False
elemBy2 eqx (y:ys) = eqx y || elemBy2 eqx ys

Вызов elemBy2 (x ==) xs теперь эквивалентен elem x xs.

... Ой, подождите. Это просто any. (А на самом деле в стандартной библиотеке elem = any . (==).)