Quand utiliser une classe de type, quand utiliser un type

Question

Je revisitais un morceau de code que j'ai écrit pour faire de la recherche combinatoire il y a quelques mois, et j'ai remarqué qu'il y avait une autre façon, plus simple, de faire quelque chose que j'avais précédemment réalisé avec une classe de type.

Plus précisément, j'avais précédemment une classe de type pour le type de problèmes de recherche qui ont un état de type s des actions (opérations sur les états) de type a Il s'agit d'un état initial, d'un moyen d'obtenir une liste de paires (action, état) et d'un moyen de tester si un état est une solution ou non :

class Problem p s a where
    initial   :: p s a -> s
    successor :: p s a -> s -> [(a,s)]
    goaltest  :: p s a -> s -> Bool

C'est quelque peu insatisfaisant, car cela nécessite l'extension MultiParameterTypeClass, et nécessite généralement FlexibleInstances et éventuellement TypeSynonymInstances lorsque vous voulez créer des instances de cette classe. Cela encombre également les signatures de vos fonctions, par ex.

pathToSolution :: Problem p => p s a -> [(a,s)]

J'ai remarqué aujourd'hui que je peux me débarrasser entièrement de la classe et utiliser un type à la place, en suivant le modèle suivant

data Problem s a {
    initial   :: s,
    successor :: s -> [(a,s)],
    goaltest  :: s -> Bool
}

Cela ne nécessite aucune extension, les signatures des fonctions sont plus jolies :

pathToSolution :: Problem s a -> [(a,s)]

et, surtout, j'ai constaté qu'après avoir remanié mon code pour utiliser cette abstraction au lieu d'une classe de type, je me suis retrouvé avec 15 à 20 % de lignes en moins qu'auparavant.

La plus grande victoire se situe dans le code qui crée des abstractions à l'aide de la classe de types. Auparavant, je devais créer de nouvelles structures de données qui enveloppaient les anciennes d'une manière compliquée, puis les transformer en instances de la classe de types. Problem (qui nécessitait plus d'extensions de langage) - beaucoup de lignes de code pour faire quelque chose de relativement simple. Après le remaniement, j'avais juste quelques fonctions qui faisaient exactement ce que je voulais.

Je regarde maintenant le reste du code, en essayant de repérer les cas où je peux remplacer les classes de type par des types, et faire plus de gains.

Ma question est la suivante : dans quelle situation cette refactorisation va-t-elle no travail ? Dans quels cas est-il préférable d'utiliser une classe de types plutôt qu'un type de données, et comment reconnaître ces situations à l'avance, afin d'éviter une refonte coûteuse ?

Answer 1

Considérons une situation où le type et la classe existent tous deux dans le même programme. Le type peut être une instance de la classe, mais c'est plutôt trivial. Ce qui est plus intéressant, c'est que vous pouvez écrire une fonction fromProblemClass :: (CProblem p s a) => p s a -> TProblem s a .

Le remaniement que vous avez effectué est à peu près équivalent à un inlining manuel. fromProblemClass partout où vous construisez quelque chose qui sert de CProblem et faire en sorte que chaque fonction qui accepte une instance CProblem au lieu d'accepter TProblem .

Puisque les seules parties intéressantes de cette refactorisation sont la définition de TProblem et la mise en œuvre de fromProblemClass Si vous pouvez écrire un type et une fonction similaires pour n'importe quelle autre classe, vous pouvez également la remanier pour éliminer complètement la classe.

Quand cela fonctionne-t-il ?

Pensez à la mise en œuvre de fromProblemClass . En fait, vous appliquerez partiellement chaque fonction de la classe à une valeur du type instance et, ce faisant, vous éliminerez toute référence à la classe p (qui est ce que le type remplace).

Toute situation où le remaniement d'une classe de type est simple va suivre un modèle similaire.

Quand cela est-il contre-productif ?

Imaginez une version simplifiée de Show avec seulement le show fonction définie. Cela permet le même remaniement, en appliquant show et en remplaçant chaque instance par... un String . Il est clair que nous avons perdu quelque chose ici - à savoir, la possibilité de travailler avec les types originaux et de les convertir en un String à différents moments. La valeur de Show est qu'il est défini sur une grande variété de types non liés.

En règle générale, s'il existe de nombreuses fonctions différentes spécifiques aux types qui sont des instances de la classe, et que celles-ci sont souvent utilisées dans le même code que les fonctions de la classe, retarder la conversion est utile. S'il y a une ligne de démarcation nette entre le code qui traite les types individuellement et le code qui utilise la classe, les fonctions de conversion peuvent être plus appropriées, la classe de type étant une commodité syntaxique mineure. Si les types sont utilisés presque exclusivement par les fonctions de la classe, la classe de type est probablement complètement superflue.

Quand cela est-il impossible ?

Par ailleurs, le remaniement est similaire à la différence entre une classe et une interface dans les langages OO ; de même, les classes de type pour lesquelles ce remaniement est impossible sont celles qui ne peuvent pas être exprimées directement du tout dans de nombreux langages OO.

Plus précisément, quelques exemples de choses que vous ne pouvez pas traduire facilement, voire pas du tout, de cette manière :

• Le paramètre de type de la classe apparaissant uniquement en position covariante comme le type de résultat d'une fonction ou comme une valeur non fonctionnelle. Les principaux contrevenants sont mempty para Monoid y return para Monad .

• Le paramètre de type de la classe apparaît plus d'une fois dans le type d'une fonction. ne rend pas la chose vraiment impossible, mais elle complique sérieusement les choses. Les principaux contrevenants sont Eq , Ord et pratiquement toutes les classes numériques.

• Utilisation non triviale de types supérieurs dont je ne suis pas sûr de pouvoir préciser les détails, mais (>>=) para Monad est un contrevenant notable dans ce domaine. D'autre part, le p dans votre classe n'est pas un problème.

• Utilisation non triviale des classes de type multi-paramètres Je ne suis pas non plus certain de savoir comment la définir et elle devient horriblement compliquée en pratique de toute façon, étant comparable à la distribution multiple dans les langages OO. Encore une fois, votre classe n'a pas de problème ici.

Notez que, compte tenu de ce qui précède, cette refactorisation n'est même pas posible pour la plupart des classes de type standard, et serait contre-productive pour les quelques exceptions. Ce n'est pas une coïncidence :]

Qu'est-ce que vous abandonnez en appliquant ce remaniement ?

Vous renoncez à la capacité de distinguer les types originaux. Cela semble évident, mais c'est potentiellement significatif - s'il existe des situations où vous vraiment Si vous avez besoin de contrôler lequel des types d'instance de la classe originale a été utilisé, l'application de ce remaniement perd un certain degré de sécurité de type, que vous ne pouvez récupérer qu'en passant par le même genre de cerceaux utilisés ailleurs pour assurer les invariants au moment de l'exécution.

Inversement, s'il y a des situations où vous avez vraiment besoin de rendre les différents types d'instance interchangeable --L'emballage alambiqué que vous avez mentionné en est un symptôme classique : vous gagnez beaucoup à vous débarrasser des types originaux. C'est le plus souvent le cas lorsque vous ne vous souciez pas vraiment des données originales en elles-mêmes, mais plutôt de la façon dont elles vous permettent d'opérer sur d'autres données ; ainsi, l'utilisation directe des enregistrements de fonctions est plus naturelle qu'une couche supplémentaire d'indirection.

Comme indiqué plus haut, cela est étroitement lié à la POO et au type de problèmes auxquels elle est le mieux adaptée, et représente l'"autre côté" du problème de l'expression par rapport à ce qui est typique des langages de type ML.

Answer 2

Votre refactoring est étroitement lié à cet article de blog de Luke Palmer : "Antipattern Haskell : Existential Typeclass" .

Je pense que nous pouvons prouver que votre refactoring fonctionnera toujours. Pourquoi ? Intuitivement, parce que si un type Foo contient suffisamment d'informations pour que nous puissions en faire une instance de votre Problem nous pouvons toujours écrire une classe Foo -> Problem fonction qui "projette" Foo Les informations pertinentes de l'entreprise dans un Problem qui contient exactement les informations nécessaires.

De manière un peu plus formelle, nous pouvons esquisser une preuve que votre refactoring fonctionne toujours. Tout d'abord, pour préparer le terrain, le code suivant définit une traduction d'un fichier Problem en une instance de classe concrète CanonicalProblem type :

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-}

class Problem p s a where
    initial   :: p s a -> s
    successor :: p s a -> s -> [(a,s)]
    goaltest  :: p s a -> s -> Bool

data CanonicalProblem s a = CanonicalProblem {
    initial'   :: s,
    successor' :: s -> [(a,s)],
    goaltest'  :: s -> Bool
}

instance Problem CanonicalProblem s a where
    initial = initial'
    successor = successor'
    goaltest = goaltest'

canonicalize :: Problem p s a => p s a -> CanonicalProblem s a
canonicalize p = CanonicalProblem {
    initial' = initial p,
    successor' = successor p,
    goaltest' = goaltest p
}

Maintenant, nous voulons prouver ce qui suit :

1. Pour tout type Foo tal que instance Problem Foo s a il est possible d'écrire un canonicalizeFoo :: Foo s a -> CanonicalProblem s a qui produit le même résultat que canonicalize lorsqu'il est appliqué à n'importe quel Foo s a .
2. Il est possible de réécrire toute fonction qui utilise la fonction Problem en une fonction équivalente qui utilise CanonicalProblem à la place. Par exemple, si vous avez solve :: Problem p s a => p s a -> r vous pouvez écrire un canonicalSolve :: CanonicalProblem s a -> r qui est équivalent à solve . canonicalize

Je vais juste esquisser des preuves. Dans le cas de (1), supposons que vous ayez un type Foo avec ceci Problem instance :

instance Problem Foo s a where
    initial = initialFoo
    successor = successorFoo
    goaltest = goaltestFoo

Ensuite, étant donné x :: Foo s a vous pouvez prouver trivialement ce qui suit par substitution :

-- definition of canonicalize
canonicalize :: Problem p s a => p s a -> CanonicalProblem s a
canonicalize x = CanonicalProblem {
                     initial' = initial x,
                     successor' = successor x,
                     goaltest' = goaltest x
                 }

-- specialize to the Problem instance for Foo s a
canonicalize :: Foo s a -> CanonicalProblem s a
canonicalize x = CanonicalProblem {
                     initial' = initialFoo x,
                     successor' = successorFoo x,
                     goaltest' = goaltestFoo x
                 }

Et cette dernière peut être utilisée directement pour définir nos canonicalizeFoo fonction.

Dans le cas de (2), pour toute fonction solve :: Problem p s a => p s a -> r (ou des types similaires qui impliquent Problem ), et pour tout type Foo tal que instance Problem Foo s a :

• Définir canonicalSolve :: CanonicalProblem s a -> r' en prenant la définition de solve et en substituant toutes les occurrences de Problem avec leurs CanonicalProblem les définitions des instances.
• Prouvez que pour tout x :: Foo s a , solve x est équivalent à canonicalSolve (canonicalize x) .

Les preuves concrètes de (2) nécessitent des définitions concrètes de solve ou des fonctions connexes. Une preuve générale pourrait suivre l'une de ces deux voies :

• Induction sur tous les types qui ont Problem p s a contraintes.
• Prouvez que tous les Problem peuvent être écrites en termes d'un petit sous-ensemble des fonctions, prouvez que ce sous-ensemble a CanonicalProblem équivalents, et que les différentes façons de les utiliser ensemble préservent l'équivalence.

Answer 3

Si vous êtes du milieu de la POO. Vous pouvez considérer les classes de types comme des interfaces en Java. Elles sont généralement utilisées lorsque vous souhaitez fournir la même interface à différents types de données, ce qui implique généralement des implémentations spécifiques pour chaque type de données.

Dans votre cas, il est inutile d'utiliser une classe de type, cela ne fera que compliquer votre code. Pour plus d'informations, vous pouvez toujours vous référer au haskellwiki pour une meilleure compréhension. http://www.haskell.org/haskellwiki/OOP_vs_type_classes

La règle générale est la suivante : si vous n'êtes pas certain d'avoir besoin de classes de type, alors vous n'en avez probablement pas besoin.