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

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

4 голосов
/ 18 мая 2009

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

Ответы [ 2 ]

8 голосов
/ 19 мая 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 = ...

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

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

7 голосов
/ 18 мая 2009

(Помимо: ваша 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 широко поддерживают его.

...