haskell - ¿Cuáles son las diferencias entre lentes y cremalleras?

clojure functional-programming

Question

Este es un ejemplo del uso de una cremallera en 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)

Este es un ejemplo del uso de una cremallera en 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]

Este es un ejemplo del uso de una lente en Haskell:

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 }}

Este es un ejemplo del uso de una lente en 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)

Ahora parece que tanto las lentes como las cremalleras son formas funcionales de atravesar estructuras de datos anidadas.

Mi pregunta es: ¿Cuáles son las diferencias entre lentes y cremalleras? ¿Es una adecuada para un caso de uso particular?

Answer 1

Las cremalleras son similares a los cursores: permiten atravesar los árboles de forma ordenada . Sus operaciones habituales son up , down , left , right y edit . (Los nombres pueden variar dependiendo de impl.)

Las lentes son una especie de claves generalizadas (como en "claves de una estructura de datos asociativa"). La estructura no necesita ser ordenada. Sus operaciones habituales son de fetch y putback y son muy similares a get y assoc . (Los nombres pueden variar dependiendo de impl.)

Entonces, como ven, las cremalleras están muy preocupadas por la jerarquía (arriba / abajo) y el orden (izquierda / derecha), mientras que las lentes solo se enfocan (de ahí el nombre) en un dato, que incluso puede ser una proyección (eso es algo que no existía por sí solo en la estructura original).

Por ejemplo, en mi trabajo en curso en Enliven , tengo lentes que me permiten concentrarme en una sola clase o atributo de estilo en un documento HTML.

Answer 2

Las cremalleras son una variante de un tipo de datos que despliega el tipo en su contexto local y su extensión en todas las direcciones. Encima de una cremallera puede implementar un movimiento eficiente y una actualización local .

Las lentes son exámenes de primera clase de un componente particular de un tipo de datos. Se centran en 0, 1 o muchas subpartes de una estructura de datos. Cabe destacar que su ejemplo de lente en Haskell no es en realidad una lente, no es de primera clase.

Es perfectamente razonable construir una lente que se enfoque en alguna parte de la cremallera. Por ejemplo, una cremallera aún más simple que sus ejemplos es una cremallera de lista de contras

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)

Podemos modificar esta estructura incrementalmente, moviendo el foco hacia la izquierda o hacia la derecha.

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

y modificar el punto local actual

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

También podemos construir lentes que acceden a cada parte de la estructura de la cremallera.

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

_lefts :: Lens (ConsZ a) a
_lenfs 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

E incluso utilizarlos para construir nuestras acciones de cremallera con eficacia

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

modify = over _here

En última instancia, sin embargo, una lente siempre es un acceso de primera clase a un punto en particular en una estructura de datos. Se pueden componer, lo que da la ilusión de "movimiento" en un tipo, pero si realmente quieres eso, debes hacer la transformación de la cremallera y utilizar un tipo de cremallera real.

Answer 3

Las lentes y las cremalleras no son formas de mirar el mundo que se excluyen mutuamente. Puede construir un tipo de datos de "enfoque móvil" sobre las lentes, al verificar una cadena de lentes como una pila de tipo alineado. Hacer un seguimiento de los tipos que visitó en su camino hacia una estructura significa que sabe qué tipos verá cuando vuelva a subir.

La API de este "enfoque móvil" se parece aproximadamente a esto:

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 está parametrizada por una lista de tipos de snoc. El tipo de "foco actual" de la Path es el elemento más a la derecha de la lista.

Dado un Path que se enfoca en una a en alguna estructura, puede usar down para agregar un Traversal'' ab , para recuperar un Path que se enfoca en una b (es decir, el primer resultado del Traversal ). Luego puede volver a up , que muestra el Traversal más recientemente agregado para devolverle un Path que se enfoca en un nuevo. left y right mueven el foco dentro del Traversal superior.

También necesita una forma de convertir un Path en un Traversal real, para poder acceder al valor real en el que se enfoca su Path . El combinador flatten hace esto. Top y Bottom son un par de familias de tipos que encuentran los elementos de más a la izquierda y más a la derecha de una lista snoc, respectivamente.

Entonces, ¿cómo se implementa?

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 es un GADT en forma de pila. El constructor Top crea una Path vacía, una ruta desde cualquier valor hacia sí misma. El constructor Child enfoca en un elemento particular de un Traversal : contiene el Path padre que se enfoca en una a , un Traversal de a a b , y un Int representa el elemento particular del Traversal que se enfoca el Path .

empty crea un camino vacío.

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

up toma una ruta no vacía (garantizada por el tipo) y muestra el Traversal superior de ella.

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

down toma un Traversal y lo agrega a un Path , enfocándose en el resultado más a la izquierda del Traversal .

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

left y la right no cambian el nivel de la estructura en la que te estás enfocando, sin agregar o eliminar recorridos de la pila, simplemente cambian a qué elemento del recorrido más alto al que apunta la ruta.

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 mira cada recorrido a su vez y usa elementOf para enfocarse en un elemento particular del recorrido. Los compone todos juntos usando . .

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

Path no es una cremallera, exactamente. Una parte importante de lo que hace que una cremallera sea una cremallera es que puede ver o editar eficientemente el enfoque y sus vecinos sin atravesar o reconstruir todo. Path simplemente compone recorridos sin hacer referencia a una estructura particular, por lo que es tan ineficiente como trabajar con recorridos completos.

Sin embargo, no es un gran salto de Path a una verdadera cremallera. El paquete de zippers proporciona verdaderas cremalleras (cursores con acceso eficiente a una parte enfocada de una estructura real) genéricamente, basándose en esta idea de una secuencia de lentes alineada con el tipo. A medida que desciende a través de una estructura, la Zipper desempaqueta cada recorrido en una estructura de datos como su Loc . Luego, cuando retrocedes upward vuelve a escribir los nuevos valores en la estructura utilizando Traversal .