Haskell: Typeclass vs passer une fonction

16

Il me semble que vous pouvez toujours passer des arguments de fonction plutôt que d'utiliser une classe de types. Par exemple, plutôt que de définir une classe de types d'égalité:

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

Et son utilisation dans d'autres fonctions pour indiquer un argument de type doit être une instance de Eq:

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

Ne pouvons-nous pas simplement définir notre elemfonction sans utiliser une classe de types et passer à la place un argument de fonction qui fait le travail?

mahdix
la source
2
cela s'appelle le dictionnaire qui passe. Vous pouvez considérer les contraintes de classe de types comme des arguments implicites.
Poscat
2
Vous pouvez le faire, mais il est évidemment beaucoup plus pratique de ne pas avoir à passer une fonction et de simplement utiliser une fonction "standard" en fonction du type.
Robin Zigmond
2
Vous pourriez le dire comme ça, oui. Mais je dirais qu'il y a au moins un autre avantage important: la possibilité d'écrire des fonctions polymorphes qui fonctionnent sur n'importe quel type qui implémente une "interface" particulière ou un ensemble de fonctionnalités. Je pense que les contraintes de typeclass expriment cela très clairement d'une manière qui ne fait pas passer des arguments de fonction supplémentaires. En particulier à cause des "lois" (malheureusement implicites) que de nombreuses classes de types doivent satisfaire. Une Monad mcontrainte me dit plus que de passer des arguments de fonction supplémentaires de types a -> m aet m a -> (a -> m b) -> m b.
Robin Zigmond
1
L' TypeApplicationsextension vous permet de rendre l'argument implicite explicite. (==) @Int 3 5compare 3et 5spécifiquement en tant que Intvaleurs. Vous pouvez considérer @Intcomme une clé dans le dictionnaire des fonctions d'égalité spécifiques au type, plutôt que la Intfonction de comparaison spécifique elle-même.
chepner

Réponses:

19

Oui. C'est ce qu'on appelle le «style de passage du dictionnaire». Parfois, lorsque je fais des choses particulièrement délicates, je dois supprimer une classe de types et la transformer en dictionnaire, car la transmission de dictionnaire est plus puissante 1 , mais souvent assez lourde, ce qui rend le code conceptuellement simple assez compliqué. J'utilise le style de passage de dictionnaire parfois dans des langues qui ne sont pas Haskell pour simuler des classes de caractères (mais j'ai appris que ce n'est généralement pas une aussi bonne idée qu'il y paraît).

Bien sûr, chaque fois qu'il y a une différence de puissance expressive, il y a un compromis. Bien que vous puissiez utiliser une API donnée de plusieurs manières si elle est écrite à l'aide de DPS, l'API obtient plus d'informations si vous ne le pouvez pas. Dans la pratique, cela apparaît dans Data.Set, qui repose sur le fait qu'il n'y a qu'un seul Orddictionnaire par type. Le Setstocke ses éléments triés selon Ord, et si vous créez un ensemble avec un dictionnaire, puis insérez un élément en utilisant un autre, comme cela serait possible avec DPS, vous pourriez casser Setl'invariant et le faire planter. Ce problème d'unicité peut être atténué en utilisant une existentielle fantômetapez pour marquer le dictionnaire, mais, encore une fois, au prix d'une complexité gênante dans l'API. Cela apparaît également à peu près de la même manière dans l' TypeableAPI.

Le bit d'unicité ne revient pas très souvent. Les classes de caractères sont excellentes pour écrire du code pour vous. Par exemple,

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

qui prend deux "processeurs" qui prennent une entrée et pourraient donner une sortie, et les concatène, aplatissant Nothing, devraient être écrits en DPS quelque chose comme ceci:

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

Nous avons essentiellement dû préciser le type dans lequel nous l'utilisons à nouveau, même si nous l'avons déjà précisé dans la signature de type, et même cela était redondant car le compilateur connaît déjà tous les types. Parce qu'il n'y a qu'une seule façon de construire un donné Semigroupà un type, le compilateur peut le faire pour vous. Cela a un effet de type "intérêt composé" lorsque vous commencez à définir un grand nombre d'instances paramétriques et à utiliser la structure de vos types pour calculer pour vous, comme dans les Data.Functor.*combinateurs, et cela est utilisé avec un grand effet avec deriving vialequel vous pouvez essentiellement obtenir toutes les structure algébrique "standard" de votre type écrite pour vous.

Et ne me lancez même pas sur MPTC et fundeps, qui réinjectent des informations dans la vérification typographique et l'inférence. Je n'ai jamais essayé de convertir une telle chose en DPS - je suppose que cela impliquerait de passer beaucoup de preuves d'égalité de type - mais en tout cas je suis sûr que ce serait beaucoup plus de travail pour mon cerveau que je ne serais à l'aise avec.

-

1 A moins que vous ne les utilisiez, reflectionauquel cas elles deviennent équivalentes en puissance - mais reflectionpeuvent également être lourdes à utiliser.

luqui
la source
Je suis très intéressé par les fonds exprimés via DPS. Connaissez-vous des ressources recommandables à ce sujet? Quoi qu'il en soit, explication très compréhensible.
bob
@bob, pas au hasard, mais ce serait une exploration intéressante. Peut-être poser une nouvelle question à ce sujet?
luqui
5

Oui. Cela (appelé passage de dictionnaire) est essentiellement ce que le compilateur fait pour les classes de toute façon. Pour cette fonction, effectuée littéralement, cela ressemblerait un peu à ceci:

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

L'appel elemBy (==) x xséquivaut désormais à elem x xs. Et dans ce cas spécifique, vous pouvez aller plus loin: eqavoir le même premier argument à chaque fois, vous pouvez donc faire en sorte que la responsabilité de l'appelant soit d'appliquer cela, et vous vous retrouvez avec ceci:

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

L'appel elemBy2 (x ==) xséquivaut désormais à elem x xs.

...Oh, attendez. C'est juste any. (Et en fait, dans la bibliothèque standard,.elem = any . (==) )

Joseph Sible-Reinstate Monica
la source
Le passage au dictionnaire AFAIU est l'approche de Scala pour coder les classes de type. Ces arguments supplémentaires peuvent être déclarés comme implicitet le compilateur les injecterait pour vous à partir de la portée.
michid