4

だから私はHaskell（そして他の関数型言語だと思います）のZipperパターンについて少し読んで、データ構造をトラバースして変更しました。これは私が型を作成するスキルを磨く良い機会になると思いましたHaskellのクラス。このクラスは、トラバースされるデータ構造に関係なく、コードを書き込むための共通のトラバーサルインターフェイスを提供できるためです。

おそらく2つのクラスが必要だと思いました。1つはルートデータ構造用で、もう1つは最初のクラスをトラバースするために作成された特別なデータ構造用です。

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：
    期待されるタイプ`z'と一致しませんでした
           推論された型`ListZippera'に対して
      `z'はによってバインドされた剛体型変数です
          Zipper.hs:10:20の`zipper'の型署名
    式：ListZipper {preceding = []、following = as}
    `zipper'の定義では：
        zipper as = ListZipper {preceding = []、following = as}
    メソッド`zipper'の定義

だからここからどこへ行けばいいのかわからない。私の問題は、(Zipper z) =>宣言zがいずれかである必要があるときに、これら2つのインスタンスをバインドしようとしていることだと思いますZipper。

4

2 に答える 2

8

マルチパラメータ型クラスや関数従属性の代わりに、型同義語ファミリを使用することもできます。このような場合、それらはよりクリーンで理解しやすいソリューションを提供します。その場合、クラスとインスタンスは次のようになります。

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にすでに精通している人々のためのタイプ同義語ファミリーへの優れた入門書です。また、関数従属性の代わりに型同義語ファミリを使用する方法についての記事も少し前に書きました。

お役に立てれば！

于 2009-05-19T07:03:20.750 に答える
7

（余談ですが、あなたのgo'up命名スキームは...独創的です。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、これは明らかに制限が多すぎます。

コードは、次の最小限の変更でタイプチェックします。

{-# 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の実装は広くサポートしています。

于 2009-05-18T17:32:55.520 に答える