Haskell: Création de classes de type pour les fermetures à glissière

Question

J'ai donc lu un peu sur le motif Zipper dans Haskell (et d'autres langages fonctionnels, je suppose) pour traverser et modifier une structure de données, et je pensais que ce serait un bon chance pour moi de perfectionner mes compétences dans la création de classes de types dans Haskell, puisque la classe pourrait présenter une interface de traversée commune pour que j'écrive du code, indépendamment de la structure de données traversée.

Je pensais que je serais probablement besoin de deux cours - un pour la structure de données racine, et une pour la structure de données spéciale créée pour traverser la première:

module Zipper where 

class Zipper z where 
    go'up :: z -> Maybe z 
    go'down :: z -> Maybe z 
    go'left :: z -> Maybe z 
    go'right :: z -> Maybe z 

class Zippable t where 
    zipper :: (Zipper z) => t -> z 
    get :: (Zipper z) => z -> t 
    put :: (Zipper z) => z -> t -> z 

Mais quand j'ai essayé ces derniers avec quelques simples datastructures comme une liste:

-- store a path through a list, with preceding elements stored in reverse 
data ListZipper a = ListZipper { preceding :: [a], following :: [a] } 

instance Zipper (ListZipper a) where 
    go'up ListZipper { preceding = [] } = Nothing 
    go'up ListZipper { preceding = a:ps, following = fs } = 
     Just $ ListZipper { preceding = ps, following = a:fs } 
    go'down ListZipper { following = [] } = Nothing 
    go'down ListZipper { preceding = ps, following = a:fs } = 
     Just $ ListZipper { preceding = a:ps, following = fs } 
    go'left _ = Nothing 
    go'right _ = Nothing 

instance Zippable ([a]) where 
    zipper as = ListZipper { preceding = [], following = as } 
    get = following 
    put z as = z { following = as } 

Ou un arbre binaire:

-- binary tree that only stores values at the leaves 
data Tree a = Node { left'child :: Tree a, right'child :: Tree a } | Leaf a 
-- store a path down a Tree, with branches not taken stored in reverse 
data TreeZipper a = TreeZipper { branches :: [Either (Tree a) (Tree a)], subtree :: Tree a } 

instance Zipper (TreeZipper a) where 
    go'up TreeZipper { branches = [] } = Nothing 
    go'up TreeZipper { branches = (Left l):bs, subtree = r } = 
     Just $ TreeZipper { branches = bs, subtree = Node { left'child = l, right'child = r } } 
    go'up TreeZipper { branches = (Right r):bs, subtree = l } = 
     Just $ TreeZipper { branches = bs, subtree = Node { left'child = l, right'child = r } } 
    go'down TreeZipper { subtree = Leaf a } = Nothing 
    go'down TreeZipper { branches = bs, subtree = Node { left'child = l, right'child = r } } = 
     Just $ TreeZipper { branches = (Right r):bs, subtree = l } 
    go'left TreeZipper { branches = [] } = Nothing 
    go'left TreeZipper { branches = (Right r):bs } = Nothing 
    go'left TreeZipper { branches = (Left l):bs, subtree = r } = 
     Just $ TreeZipper { branches = (Right r):bs, subtree = l } 
    go'right TreeZipper { branches = [] } = Nothing 
    go'right TreeZipper { branches = (Left l):bs } = Nothing 
    go'right TreeZipper { branches = (Right r):bs, subtree = l } = 
     Just $ TreeZipper { branches = (Left l):bs, subtree = r } 

instance Zippable (Tree a) where 
    zipper t = TreeZipper { branches = [], subtree = t } 
    get TreeZipper { subtree = s } = s 
    put z s = z { subtree = s } 

Je ne pouvais pas le compiler, je viens d'obtenir beaucoup d'erreurs comme celui-ci pour chacun de mes Zippable définitions d'exemple:

 
Zipper.hs:28:14: 
    Couldn't match expected type `z' 
      against inferred type `ListZipper a' 
     `z' is a rigid type variable bound by 
      the type signature for `zipper' at Zipper.hs:10:20 
    In the expression: ListZipper {preceding = [], following = as} 
    In the definition of `zipper': 
     zipper as = ListZipper {preceding = [], following = as} 
    In the definition for method `zipper' 

Je ne suis pas sûr où aller d'ici. Je soupçonne que mon problème est que j'essaie de lier ces deux instances ensemble, lorsque la déclaration (Zipper z) => veut simplement z être un Zipper.

Answer 1

(A part:. Votre schéma de nommage est ... inventive de style Haskell est généralement camelCase.)

Vous êtes sur la bonne voie. Ce que vous avez écrit est équivalent à ce qui suit.

{-# LANGUAGE RankNTypes #-} 
instance Zippable [a] where 
    zipper = ... :: forall z. (Zipper z) => [a] -> z 
    get = ... :: forall z. (Zipper z) => z -> [a] 
    set = ... :: forall z. (Zipper z) => z -> [a] -> z 

(Pour tous les types z, étant donné Zipper z, il existe un zipper :: [a] -> z.)

Vous Tring pour définir zipper = ... :: [a] -> ListZipper a, ce qui est manifestement trop restrictive.

Votre code typer avec les modifications minimales suivantes:

{-# LANGUAGE MultiParamTypeClasses #-} 
class (Zipper z) => Zippable z t where 
    zipper :: t -> z 
    get :: z -> t 
    set :: z -> t -> z 
instance Zippable (ListZipper a) [a] where 
    ... 
instance Zippable (TreeZipper a) (Tree a) where 
    ... 

Voir multi-parameter type classes. C'est une extension post-Haskell'98, mais les implémentations Haskell la supportent largement.

Answer 2

Vous pouvez également utiliser des familles de synonymes de type au lieu de classes de types multi-paramètres et de dépendances fonctionnelles. Dans de tels cas, ils offrent une solution plus propre et plus facile à comprendre. Dans ce cas, la classe et l'instance deviendraient:

class Zippable t where 
    type ZipperType t :: * 
    enter :: t -> ZipperType t 
    focus :: ZipperType t -> t 

instance Zippable [a] where 
    type ZipperType [a] = ListZipper a 
    enter = ... 
    focus = ... 

Fun with type functions est une excellente introduction à saisir les familles de synonymes pour les personnes déjà familières avec Haskell. J'ai également écrit an article sur la façon dont les familles de types de synonymes peuvent souvent être utilisées à la place des dépendances fonctionnelles il y a un certain temps.

Espérons que cela aide!