Haskell：ジッパーのタイプクラスを作成する

Question

ハスケル（そして他の関数型言語のジッパーパターン）について、データ構造を横断して変更する方法について少しお読みになりました。これは良いことだと思いました クラスは、横断されたデータ構造とは無関係に、コードを記述するための共通のトラバーサルインタフェースを提示することができるので、私はHaskellで型クラスを作成する技術を磨くことができます。

私はおそらく二つのクラス必要があるだろうと思った - ルートデータ構造のための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: 
    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つのインスタンス を一緒にバインドしようとしていることが問題だと思います。

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 

（Zipper z与えられたすべてのタイプ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 
    ... 

参照multi-parameter type classes：

あなたのコードは、次の最小限の変更でです。TypeCheckます。これは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を書きました。

希望すると便利です。