Haskell: Création de classes de type pour les tirettes

Question

J'ai lu un peu sur le modèle Fermeture éclair dans Haskell (et d'autres langages fonctionnels, je suppose) pour parcourir et modifier une structure de données, et je pensais que ce serait pour moi une bonne occasion de parfaire mes compétences à la création de classes de type à Haskell, depuis la classe pourrait présenter une interface commune pour moi traversal d'écrire du code pour, indépendamment de la structure de données traversèrent.

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 le premier:

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 quelques datastructures simples 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 définitions d'instance Zippable:

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 pense que mon problème est que je suis en train de lier ces deux instances ensemble, lorsque la déclaration de (Zipper z) => veut juste z être une Zipper.

Answer 1

(En plus:.. Votre schéma de nommage go'up est ... inventive de style Haskell est généralement camelCase)

Vous êtes sur la bonne voie. Qu'est-ce que vous avez écrit est équivalent au-dessous.

{-# 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 classes de type multi-paramètres . Il est une extension post-Haskell'98, mais les mises en œuvre Haskell soutiennent largement il.

Answer 2

Vous pouvez également utiliser les familles de synonymes de type au lieu des classes de type multi-paramètres et dépendances fonctionnelles. Dans des cas comme ceux-ci, 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 avec des fonctions de type est une excellente introduction à saisir les familles de synonymes pour les personnes déjà familières avec Haskell. J'ai également écrit un article sur la façon dont le type familles de synonymes peuvent souvent être utilisés à la place des dépendances fonctionnelles il y a un certain temps.

Hope this helps!