Haskell: Создание классов типов для молнии

Question

Итак, я немного читал о шаблоне Zipper в Haskell (и других функциональных языках, я полагаю), чтобы перемещаться и изменять структуру данных, и я думал, что это будет хорошо шанс для меня отточить мои навыки при создании классов типов в Haskell, поскольку класс может представить общий интерфейс обхода для меня, чтобы писать код, независимо от пройденной структуры данных.

я думал, что, вероятно, нужно два класса - один для структуры корневых данных, и один для специальной структуры данных, созданной пройти первый:

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 

Но когда я попытался это с некоторыми простыми datastructures как список:

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

Или бинарное дерево:

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

я не мог заставить его собрать, я просто получаю много ошибок, как это для каждого из моих определений экземпляра 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' 

Так что я не знаю, куда идти отсюда. Я подозреваю, что моя проблема в том, что я пытаюсь связать эти два экземпляра вместе, когда объявление (Zipper z) => просто хочет z быть любым Zipper.

Answer 1

(в стороне:. Ваша схемы именования ... изобретательский Haskell стиль, как правило, верблюжий.)

Вы находитесь на правильном пути. То, что вы написали, эквивалентно приведенному ниже.

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

(Для всех типов z, учитывая Zipper z, существует zipper :: [a] -> z.)

Вы Тринг, чтобы определить zipper = ... :: [a] -> ListZipper a, что явно слишком ограничительными.

Ваш код будет typecheck со следующими минимальными изменениями:

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

См multi-parameter type classes. Это расширение post-Haskell'98, но реализация Haskell широко поддерживает его.

Answer 2

Вы также можете использовать семейства синонимов типа вместо классов с несколькими параметрами и функциональных зависимостей. В таких случаях они предлагают более чистое и понятное решение. В этом случае класс и экземпляр стал бы:

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 является отличным введением в синоним типа семьи для людей, которые уже знакомы с Haskell. Я также написал an article о том, как несколько семейств синонимов типов часто можно использовать вместо функциональных зависимостей некоторое время назад.

Надеюсь, это поможет!