Haskell: creazione di classi di tipo per chiusure lampo

Question

Così ho letto un po 'sul modello Zipper in Haskell (e altri linguaggi funzionali, suppongo) per attraversare e modificare una struttura di dati, e ho pensato che questo sarebbe una buona occasione per me di affinare le mie capacità a creare classi tipo a Haskell, poiché la classe potrebbe presentare un'interfaccia comune attraversamento per me scrivere codice, indipendente dalla struttura di dati attraversato.

Ho pensato che probabilmente avrei bisogno di due classi - una per la struttura di dati radice, e uno per la struttura di dati speciale creata per attraversare il primo:

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

Ma quando ho provato questi con alcune strutture di dati semplici come una lista:

-- 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 }

O un albero binario:

-- 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 }

non ho potuto farlo per compilare, avevo appena ricevo un sacco di errori come questo per ciascuno dei miei Zippable definizioni istanza:

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'

Quindi non sono sicuro dove andare da qui. Ho il sospetto che il mio problema è che io sto cercando di legare queste due istanze insieme, quando la dichiarazione (Zipper z) => vuole solo z essere qualsiasi Zipper.

Answer 1

(A parte:.. Il vostro schema di denominazione go'up è ... inventiva stile Haskell è di solito camelCase)

Sei sulla strada giusta. Quello che hai scritto è equivalente al di sotto.

{-# 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

(Per tutti i tipi z, data Zipper z, esiste un zipper :: [a] -> z.)

Stai Tring definire zipper = ... :: [a] -> ListZipper a, che è chiaramente troppo restrittiva.

Il tuo codice TYPECHECK con le seguenti modifiche minime:

{-# 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
    ...

classi di tipo multi-parametro . Si tratta di un'estensione post-Haskell'98, ma le implementazioni Haskell ampiamente supporta.

Answer 2

È inoltre possibile utilizzare le famiglie sinonimo tipo invece di classi di tipo multi-parametro e dipendenze funzionali. In casi come questi offrono una soluzione più pulita e più facile da capire. In tal caso, la classe e l'istanza sarebbe diventato:

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 = ...

Divertimento con funzioni di tipo è un eccellente introduzione di digitare famiglie sinonimo di persone che già familiarità con Haskell. Ho anche scritto un articolo su come tipo famiglie sinonimo spesso possono essere utilizzati al posto di dipendenze funzionali qualche tempo fa.

Spero che questo aiuti!