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 中使用镜头的示例。

(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)

现在看来，lens 和 zippers 都是遍历嵌套数据结构的函数式方法。

我的问题是：镜片和拉链有什么区别？是否适合特定用例？

Answer 1

拉链类似于游标：它们允许以有序的方式遍历树。它们通常的操作是up、down、left和。（名称可能因实现而异）rightedit

镜头是某种通用键（如“关联数据结构的键”）。该结构不需要订购。它们通常的操作是fetchand并且与andputback非常相似。（名称可能因实现而异）getassoc

因此，正如您所见，拉链非常关注层次结构（上/下）和顺序（左/右），而镜头只是关注（因此得名）一条数据，这甚至可能是一个投影（那是什么在原始结构中并不存在）。

例如，在我正在进行的Enliven工作中，我有一些镜头可以让我专注于 HTML 文档中的单个类或样式属性。

Answer 2

拉链是一种数据类型的变体，它将类型展开到它的本地上下文和它的各个方向的范围内。在 Zipper 上，您可以实现高效的运动和本地更新。

镜头是对数据类型的特定组件的一流检查。他们专注于数据结构的 0、1 或许多子部分。值得注意的是，您在 Haskell 中的镜头示例实际上并不是镜头——它不是一流的。

构建一个专注于拉链某些部分的镜头是完全合理的。例如，比您的示例更简单的拉链是 Cons 列表拉链：

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 列表参数化。的“当前焦点”的类型Path是列表最右边的元素。

给定在某个结构中Path专注于a 的 a a，您可以使用down附加 a Traversal' a b，以获取Path专注于 a 的 a b（即 的第一个结果Traversal）。然后，您可以返回up，它会弹出最近附加Traversal的内容以返回 a Path，该 a 再次侧重于 a a。left并将right焦点移到最顶层Traversal。

您还需要一种将 a Pathback 转换为 actual的方法Traversal，以便访问您Path放大的实际值。flatten组合器执行此操作。Top和Bottom是一对类型族，它们分别找到一个 snoc-list 的最左边和最右边的元素。

---

那么它是如何实现的呢？

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 的特定元素-它包含关注aTraversal的父元素、 a from to和表示 a 的特定元素的父元素。PathaTraversalabIntTraversalPath

empty创建一个空路径。

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

up采用非空路径（由类型保证）并Traversal从中弹出最顶部。

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

down接受 aTraversal并将其附加到 a Path，重点关注Traversal.

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.

Answer 4

Alens是某些数据结构中的路径。您可以组成这些路径，就像您可以通过制作列表树的列表等来组成数据结构一样。类型对齐在任何阶段由类型系统验证：您可以为您的数据结构提供一个镜头，使用其他人的镜头。每个人都依赖本机编译器的权限。

Azipper是固定静态数据结构内的可移动焦点。将组合具体化为类型对齐的序列可以让您重新负责，同时仍然确保最终组合，因此您可以在构建的操作序列上添加操作。但此类操作的词汇left, right, up,down是从所述固定数据结构派生的词汇。