镜头和拉链有什么区别？

Question

这是使用Haskell中的zipper的示例：

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中的zipper的示例：

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

现在看来，镜头和拉链都是遍历嵌套数据结构的功能性方法。

我的问题是：镜头和拉链之间有什么区别？有没有一种更适合特定的用例？

- hawkeye

---

你能在拉链里移动吗？一般来说，拉链具有“向左走”、“向上走”等基本操作；通常无法将镜头稍微向左移动。它们之间密切相关。 - drquicksilver

镜头在概念上只是一个getter/setter对，可以深入到数据结构中（实际上甚至比这更通用）。拉链是一种特定类型的数据结构，您可以（至少）向左和向右/向上和向下移动。 - David Young

Answer 1

拉链与光标类似：它们允许以有序方式遍历树。它们的常见操作是up、down、left、right和edit。(名称可能因实现而异)

镜头是一种广义键(如"关联数据结构的键")。结构不需要被排序。它们的常见操作是fetch和putback，非常类似于get和assoc。(名称可能因实现而异)

所以，正如您所看到的，拉链非常关注层次结构(up/down)和顺序(left/right)，而镜头只关注数据的聚焦(因此得名)，这甚至可能是一个投影(即在原始结构中不存在的东西)。

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

- cgrand

Answer 2

拉链是一种数据类型的变体，它将类型展开为其本地上下文和所有方向的范围。在拉链上，您可以实现有效的移动和本地更新。

镜头是数据类型特定组件的一流检查。它们专注于数据结构的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

然而，镜头始终是访问数据结构中特定点的一流方法。它们可以组合在一起，从而在类型中产生“动态效果”，但如果您真的想要这样做，那么您应该使拉链变换并使用真正的拉链类型。

- J. Abrahamson

Answer 3

Lenses和zippers不是互斥的看待世界的方式。您可以在lenses之上构建“可移动焦点”数据类型，通过将一系列lenses具象化为类型对齐的堆栈来实现。跟踪您在结构下行时访问的类型意味着您知道在返回时将要查看哪些类型。

这个“可移动焦点”的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的“当前焦点”的类型是列表中最右边的元素。

给定一个在某个结构中聚焦于a的Path，您可以使用down附加一个Traversal' a b，以返回一个聚焦于b的Path（即，Traversal的第一个结果）。然后，您可以向上返回up，它会弹出最近添加的Traversal，并将Path返回回聚焦于a的状态。 left和right在最上层的Traversal中移动焦点。

你还需要一种将 Path 转换为实际的 Traversal 以访问 Path 缩放的实际值的方法。 flatten 组合器可以实现此功能。 Top 和 Bottom 是一对类型家族，分别查找 snoc-list 的最左侧和最右侧元素。

---

“那么它是如何实现的？”，保留了HTML格式。

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 构造函数关注于 Traversal 的特定元素 - 它包含父级 Path，该父级 Path 关注于一个 a，一个从 a 到 b 的 Traversal，以及一个表示 Path 关注的 Traversal 的特定元素的 Int。

empty 创建一个空路径。

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

up 接受一个非空路径（由类型保证），并从中弹出最顶部的 Traversal。

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

down 接受一个 Traversal 并将其附加到 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到真正的zipper并不是一大跃进。zippers包提供了真正的zipper——具有对实际结构的聚焦部分进行高效访问的光标，基于这种类型对齐的序列和镜头的想法进行通用化。当您通过一个结构下降时，Zipper将每个遍历解包为类似于您的Loc的数据结构。然后，当您向上upward时，它使用Traversal将新值写回到结构中。

- Benjamin Hodgson

Answer 4

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

拉链是固定的静态数据结构内部的可移动焦点。将组合实体化为类型对齐序列使您能够重新掌控，同时仍然确保最终组合，因此您可以在操作序列上添加操作。但是，这些操作的词汇，left、right、up、down是从所述固定数据结构派生的词汇。

- nicolas