В чем разница между линзами и молниями?

Застежки-молнии похожи на курсоры: они позволяют перемещаться по деревьям упорядоченно. Их обычные операции: up, down, left, right и edit. (названия могут отличаться в зависимости от реализации)

Линзы — это своего рода обобщенные ключи (как в «ключах ассоциативной структуры данных»). Структуру не нужно заказывать. Их обычные операции fetch и putback очень похожи на get и assoc. (названия могут отличаться в зависимости от реализации)

Итак, как вы видите, молнии очень сильно озабочены иерархией (вверх/вниз) и порядком (влево/вправо), в то время как линзы просто фокусируются (отсюда и название) на фрагменте данных, который может быть даже проекцией (это что-то что не существовало само по себе в исходной структуре).

Например, в моей текущей работе над Enliven у меня есть линзы, которые позволяют мне сосредоточиться на одном атрибуте класса или стиля в документе HTML. .

Застежки-молнии — это вариант типа данных, который разворачивает тип в его локальный контекст и его экстенты во всех направлениях. Поверх 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

В конечном счете, линза — это всегда первоклассный доступ к определенной точке структуры данных. Их можно комбинировать, что создает иллюзию «движения» шрифта, но если вы действительно этого хотите, вам следует преобразовать застежку-молнию и использовать настоящий тип застежки-молнии.

Линзы и молнии не являются взаимоисключающими способами смотреть на мир. Вы можете создать тип данных «подвижный фокус» поверх линз, реформировав цепочку линз в виде стека, выровненного по типу. Отслеживание типов, которые вы посетили, спускаясь по структуре, означает, что вы знаете, какие типы вы увидите, когда вернетесь обратно.

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 в некоторой структуре, вы можете использовать down для добавления Traversal' a b, чтобы вернуть Path, который фокусируется на b (а именно, первый результат Traversal). Затем вы можете вернуться к up, который извлекает последний добавленный Traversal, чтобы вернуть вам Path, который снова фокусируется на a. left и right перемещают фокус внутри самого верхнего Traversal.

Вам также нужен способ превратить Path обратно в фактическое Traversal, чтобы получить доступ к фактическому значению, которое увеличивает ваш Path. Это делает комбинатор flatten. Top и Bottom — это пара семейств типов, которые находят крайний левый и крайний правый элементы списка snoc соответственно.

Так как же это реализовано?

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, который фокусируется на a, Traversal от a до b и Int, представляющий конкретный элемент Traversal, на который фокусируется Path.

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 к настоящей застежке-молнии. Пакет zippers предоставляет настоящие застежки-молнии - курсоры с эффективным доступом к сфокусированной части реальной структуры - в общем, на основе этой идеи последовательности линз, выровненной по типу. Когда вы спускаетесь по структуре, Zipper распаковывает каждый обход в структуру данных, похожую на вашу Loc. Затем, когда вы вернетесь назад, upward он записывает новые значения обратно в структуру, используя Traversal.

lens – это путь в некоторой структуре данных. Вы можете составить этот путь, точно так же, как вы можете составить структуру данных, составив список дерева списка и т. д. Выравнивание типов проверяется системой типов на любом этапе: вы можете предоставить линзу для своей структуры данных, используя другие народный объектив. все полагаются на авторитет родного компилятора.

zipper — это подвижный фокус внутри фиксированной статической структуры данных. Преобразование композиции в последовательность, выровненную по типу, позволяет вам снова взять на себя ответственность, но в то же время гарантирует, что в конечном итоге все будет компоноваться, поэтому вы можете добавить операцию к созданной вами последовательности операций. но словарь для таких операций, left, right, up, down, является словарем производным от указанного фиксированного структура данных.