haskell - レンズとジッパーの違いは何ですか？

Question

これは、Haskell でジッパーを使用する例です。

data Tree a = Fork (Tree a) (Tree a) | Leaf a
data Cxt a = Top | L (Cxt a) (Tree a) | R (Tree a) (Cxt a)
type Loc a = (Tree a, Cxt a)

left :: Loc a -> Loc a
left (Fork l r, c) = (l, L c r)

right :: Loc a -> Loc a
right (Fork l r, c) = (r, R l c)

top :: Tree a -> Loc a 
top t = (t, Top)

up :: Loc a -> Loc a
up (t, L c r) = (Fork t r, c)
up (t, R l c) = (Fork l t, c)

upmost :: Loc a -> Loc a
upmost l@(t, Top) = l
upmost l = upmost (up l)

modify :: Loc a -> (Tree a -> Tree a) -> Loc a
modify (t, c) f = (f t, c)

これは、Clojure でジッパーを使用する例です。

(use 'clojure.zip)
(require '[clojure.zip :as z])

user> (def z [[1 2 3] [4 [5 6] 7] [8 9]])
#'user/z

user> (def zp (zipper vector? seq (fn [_ c] c) z))
#'user/zp

user> zp
[[[1 2 3] [4 [5 6] 7] [8 9]] nil]

user> (-> zp down)
[[1 2 3] {:l [], :pnodes [[[1 2 3] [4 [5 6] 7] [8 9]]], :ppath nil, :r ([4 [5 6] 7] [8 9])}]

user> (first (-> zp down))
[1 2 3]

これは、Haskell で Lens を使用する例です。

data Person = P { name :: String 
                , addr :: Address 
                }
data Address = A { street :: String
                 , city :: String
                 , postcode :: String 
                 }

setPostcode :: String -> Person -> Person
setPostcode pc p = p { addr = addr p { postcode = pc }}

これは、Clojure で Lens を使用する例です。

(use 'lens)

(defrecord Address [street city postcode])
(defrecord Person [name age address])
(defrecord User [uid username identity password])

(def -postcode (mklens :postcode))
(def -city (mklens :city))
(def -street (mklens :street))
(def -address (mklens :address))
(def -age (mklens :age))
(def -name (mklens :name))
(def -uid (mklens :uid))
(def -username (mklens :username))
(def -identity (mklens :identity))
(def -password (mklens :password))

(-get -postcode home)

(-set -postcode home 500)

現在、レンズとジッパーの両方が、ネストされたデータ構造をトラバースする機能的な方法であるようです。

私の質問は:レンズとジッパーの違いは何ですか? 特定のユースケースに適していますか?

Answer 1

ジッパーはカーソルに似ています:順序付けられた方法でツリーをトラバースすることができます。通常の操作はup、down、left、rightおよびeditです。(名前は impl によって異なる場合があります)

レンズはある種の一般化されたキーです (「連想データ構造のキー」のように)。構造を注文する必要はありません。それらの通常の操作はfetchおよびであり、putbackおよび と非常によく似ていgetますassoc。(名前は impl によって異なる場合があります)

ご覧のとおり、ジッパーは階層 (上/下) と順序 (左/右) に非常に関心がありますが、レンズはデータの一部に焦点を当てているだけです (名前の由来)。元の構造では単独では存在しませんでした)。

たとえば、進行中のEnlivenの作業では、HTML ドキュメント内の単一のクラスまたはスタイル属性に焦点を当てることができるレンズがあります。

Answer 2

ジッパーは、型をそのローカル コンテキストと全方向のエクステントに展開するデータ型のバリアントです。Zipper の上に、効率的なモーションとローカル更新を実装できます。

レンズは、データ型の特定のコンポーネントの第一級の検査です。それらは、データ構造の 0、1、または多数のサブパーツに焦点を当てています。特に、Haskell のレンズの例は、実際にはレンズではなく、ファースト クラスではありません。

ジッパーのある部分に焦点を合わせたレンズを構築することは完全に理にかなっています。たとえば、例よりもさらに単純なジッパーは、コンス リスト ジッパーです。

data Cons a = Empty | Cons a (Cons a)

data ConsZ a = ConsZ { lefts :: Cons a; here :: a; rights :: Cons a }

zip :: Cons a -> Maybe (ConsZ a)
zip Empty = Nothing
zip (Cons a as) = ConsZ Empty a as

unzip :: ConsZ a -> Cons a
unzip (ConsZ Empty a as) = Cons a as
unzip (ConsZ (Cons l ls) a as) = unzip (ConsZ ls) l (Cons a as)

フォーカスを左または右に移動して、この構造を段階的に変更できます。

moveRight :: ConsZ a -> Maybe (ConsZ a)
moveRight (ConsZ _ _ Empty) = Nothing
moveRight (ConsZ ls x (Cons a as)) =  ConsZ (Cons x ls) a as

現在のローカル ポイントを変更します。

modify :: (a -> a) -> ConsZ a -> ConsZ a
modify f (ConsZ ls x rs) = ConsZ ls (f x) rs

ジッパー構造の各部分にアクセスするレンズを構築することもできます。

type Lens s a = forall f . Functor f => (a -> f a) -> (s -> f s)

_lefts :: Lens (ConsZ a) a
_lefts inj (ConsZ ls x rs) = (\ls -> ConsZ ls' x rs) <$> inj ls

_here :: Lens (ConsZ a) a
_here inj (ConsZ ls x rs) = (\x' -> ConsZ ls x' rs) <$> inj x

さらに、それらを使用してジッパー アクションを効果的に構築します。

over :: ((a -> Identity a) -> s -> Identity s) -> (a -> a) -> (s -> s)
over l f s = runIdentity (l (Identity . f) s)

modify = over _here

ただし、最終的には、レンズは常にデータ構造内の特定のポイントへのファースト クラス アクセスです。それらは構成することができ、タイプに「動き」の錯覚を与えますが、本当にそれが必要な場合は、ジッパーを変形させて本物のジッパー タイプを使用する必要があります。

Answer 3

レンズとジッパーは、相互に排他的な世界の見方ではありません。レンズのチェーンをタイプアラインされたスタックとして具体化することにより、レンズの上に「可動フォーカス」データタイプを構築できます。構造をたどる途中で訪れた型を追跡することは、戻ったときにどの型を見ているかを知っていることを意味します。

この「可動フォーカス」の API は、おおよそ次のようになります。

empty :: Path (E :> a)
up :: Path (as :> a :> b) -> Path (as :> a)
down :: Path (as :> a) -> Traversal' a b -> Path (as :> a :> b)
left :: Path (as :> a :> b) -> Path (as :> a :> b)
right :: Path (as :> a :> b) -> Path (as :> a :> b)

flatten :: Path as -> Traversal' (Top as) (Bottom as)

Pathタイプのsnoc-listによってパラメータ化されます。の「現在のフォーカス」のタイプはPath、リストの一番右の要素です。

ある構造体Pathの に焦点を当てた が与えられた場合、を使用して a を追加し、 aに焦点を当てたを取得できます(つまり、 の最初の結果)。次に戻ることができます。これにより、最後に追加されたものがポップされ、再びに焦点を当てたa が返されます。一番上の の内側にフォーカスを移動します。adownTraversal' a bPathbTraversalupTraversalPathaleftrightTraversal

ズームインする実際の値にアクセスするには、 Pathback を actualに変換する方法も必要です。コンビネータはこれを行います。とは、snoc-list の左端と右端の要素をそれぞれ見つける型ファミリのペアです。TraversalPathflattenTopBottom

---

それで、それはどのように実装されていますか？

infixl 5 :>
data Snoc a = E | Snoc a :> a

type family Top as where
    Top (E :> a) = a
    Top (as :> _) = Top as
type family Bottom as where
    Bottom (_ :> a) = a

data Path as where
    Top :: Path (E :> a)
    Child :: Path (as :> a) -> Traversal' a b -> Int -> Path (as :> a :> b)

Path積み上げ型のGADTです。Topコンストラクターは空 (任意の値からそれ自体へのパス) を作成しPathます。Childコンストラクターは a の特定の要素に焦点を当てます。これには、に焦点を当てるTraversal親、fromから、およびが焦点を当てるの特定の要素を表す が含まれます。PathaTraversalabIntTraversalPath

empty空のパスを作成します。

empty :: Path (E :> a)
empty = Top

up空でないパス (タイプによって保証されます) を取り、Traversalそこから最上位をポップします。

up :: Path (as :> a :> b) -> Path (as :> a)
up (Child p _ _) = p

downの左端の結果に焦点を当てて、 a を取り、Traversalそれを a に追加します。PathTraversal

down :: Path (as :> a) -> Traversal' a b -> Path (as :> a :> b)
down p t = Child p t 0

left焦点を当てている構造のレベルを変更しrightないでください-スタックからトラバーサルを追加または削除する必要はありません-パスが指す最上位のトラバーサルの要素を変更するだけです。

left :: Path (as :> a :> b) -> Path (as :> a :> b)
left (Child p t n) = Child p t (n - 1)

right :: Path (as :> a :> b) -> Path (as :> a :> b)
right (Child p t n) = Child p t (n + 1)

flatten各トラバーサルを順番に見て、elementOfトラバーサルの特定の要素に焦点を当てるために使用します。を使用してそれらをすべてまとめて構成します.。

flatten :: Path as -> Traversal' (Top as) (Bottom as)
flatten Top = id
flatten (Child p t n) = flatten p . elementOf t n

---

Path正確にはジッパーではありません。ジッパーをジッパーにする重要な部分は、全体をトラバースしたり再構築したりせずに、フォーカスとその近傍を効率的に表示または編集できることです。Path特定の構造を参照せずにトラバーサルを構成するだけなので、トラバーサル全体を操作するのと同じくらい非効率的です。

Pathしかし、それは真のジッパーへの大きな飛躍ではありません。このzippersパッケージは、一般的に、レンズの型が整列されたシーケンスのこの考えに基づいて、真のジッパー (実際の構造のフォーカスされた部分への効率的なアクセスを備えたカーソル) を提供します。構造をたどると、 はZipper各トラバーサルを のようなデータ構造にアンパックしますLoc。次に戻るupwardと、 を使用して新しい値を構造体に書き戻しますTraversal。