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

Итак, я немного читал о шаблоне 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

Но когда я попробовал это с некоторыми простыми структурами данных, такими как список:

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


person rampion    schedule 18.05.2009    source источник
comment
Как насчет добавления экземпляра Monad с использованием застежки-молнии в качестве переменной состояния. Затем, чтобы поменять местами два элемента, вы говорите x ‹- получить; опускаться; y ‹- получить; положить x; подниматься; положи y   -  person Paul Johnson    schedule 21.05.2009
comment
Именно это я и сделал сегодня вечером :) gist.github.com/115203   -  person rampion    schedule 21.05.2009


Ответы (2)


(Кроме того: ваша go'up схема именования ... изобретательна. В стиле Haskell обычно используется camelCase.)

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

{-# 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, что явно слишком ограничительно.

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

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

См. классы типов с несколькими параметрами. Это расширение, появившееся после Haskell'98, но реализации Haskell широко его поддерживают.

person ephemient    schedule 18.05.2009
comment
+1 / принято - большое спасибо! Я медленно изучаю Haskell и на самом деле еще не изучил соглашения об именах, но я доберусь туда. - person rampion; 18.05.2009
comment
ОТ: когда мне следует использовать апостроф в именах? - person rampion; 18.05.2009
comment
Я видел его только в качестве основного. Как в let x' = x + 1. Его следует использовать для именования значений, которые представляют собой небольшие модификации старых значений. - person Christian Klauser; 18.05.2009
comment
После использования en.wikipedia.org/wiki/Prime_(symbol) в математике, апостроф используется только в конце имен и используется для обозначения связанного значения. - person ephemient; 18.05.2009
comment
Он не всегда используется для обозначения измененных старых значений, хотя это обычное дело. В стандартной библиотеке foldl 'является более строгим вариантом foldl. - person ephemient; 18.05.2009
comment
Возможно, стоит добавить в Zippable функциональную зависимость t- ›z. В противном случае вы столкнетесь с неоднозначностью типов при попытке использовать эти классы ... (см. Также haskell.org/ haskellwiki / Functional_dependencies) - person sth; 19.05.2009
comment
@sth: То, что я предоставил, было минимальным изменением, чтобы получить существующий код для проверки типов, но да, class (Zipper z) => Zippable z t | t -> z сделает код более удобным. Я надеялся, что OP перейдет по ссылке на классы многопараметрических типов и прочитает Без функциональных зависимостей или связанных типов эти классы многопараметрических типов могут вызвать слишком большую двусмысленность для прохождения проверки типов, но, возможно, было бы лучше быть более явным. - person ephemient; 19.05.2009
comment
Большое спасибо, что помогло мне преодолеть стену, о которой я бился головой. - person rampion; 21.05.2009

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

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

Функции типов - это отличное введение в семейства синонимов типов для людей, уже знакомых с Haskell. Я также написал статью о том, как печатать некоторое время назад вместо функциональных зависимостей часто можно было использовать семейства синонимов.

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

person Martijn    schedule 19.05.2009
comment
Семейства типов были введены около GHC 6.10.1 или около того? Я еще не использовал их, но они кажутся удобными. - person ephemient; 19.05.2009