ハスケル:ジッパーの型クラスの作成
-
22-08-2019 - |
質問
だから私はジッパーHaskellではパターンについて少し読んでいるデータ構造を横断し、修正するために(および他の関数型言語を、私は考えます)、そして私はこれは私が自分のスキルを磨くためのための良い機会になると思いました以来、Haskellで型クラスを作成するに 私はコードを書くためのクラスが共通トラバーサルインタフェースを提示できたし、データ構造の独立したが横断ます。
ルートデータ構造のための1、および作成された特殊なデータ構造のための1 -私は、私はおそらく2つのクラスを必要とするだろうと思って 最初を横断する:
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'
だから私はどこここから行くのか分かりません。私は私の問題は、私はこれらの2つのインスタンスをバインドしようとしているということであると思われます
一緒に、とき(Zipper z) =>
宣言はちょうどz
は任意のZipper
になりたいと思っています。
解決
(脇:あなたの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
を定義するトリングています。
あなたのコードは、次の最小限の変更でです。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
...
クラスをマルチパラメータタイプを参照してください。これは、ポストHaskell'98延長だが、Haskellの実装が広く、それをサポートしています。
他のヒント
また、型シノニムの家族の代わりに、マルチパラメータ型クラスと機能の依存関係を使用することができます。このようなケースでは、彼らは、クリーンかつ容易に理解できるソリューションを提供します。その場合には、クラスとインスタンスはなるます:
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 = ...
/ A>ハスケルとすでに慣れている人のための同義語の家族を入力するための優れた紹介です。私はまた、どのタイプの記事を書きました同義語の家族は、多くの場合、しばらく前に代わりに関数従属性を使用することができます。
この情報がお役に立てば幸い!