data structures - learn - Diferenciación de Estructura de Datos, Edificio de Intuición

syntax haskell

Question

De acuerdo con este documento, la diferenciación funciona en las estructuras de datos.

De acuerdo con esta respuesta :

La diferenciación, la derivada de un tipo de datos D (dado como D '') es el tipo de estructuras D con un único "agujero", es decir, una ubicación distinguida que no contiene ningún dato. Eso sorprendentemente satisface las mismas reglas que para la diferenciación en cálculo.

Las reglas son:

 1 = 0
X′ = 1
(F + G)′ = F'' + G′
(F • G)′ = F • G′ + F′ • G
(F ◦ G)′ = (F′ ◦ G) • G′

El documento al que se hace referencia es demasiado complejo para que tenga una intuición. ¿Qué significa esto en la práctica? Un ejemplo concreto sería fantástico.

Answer 1

¿Qué es un contexto de un agujero para una X en una X? No hay elección: es (-), representable por el tipo de unidad.

¿Qué es un contexto de un agujero para una X en una X * X? Es algo así como (-, x2) o (x1, -), por lo que es representable por X + X (o 2 * X, si lo desea).

¿Qué es un contexto de un agujero para una X en una X * X * X? Es algo así como (-, x2, x3) o (x1, -, x3) o (x1, x2, -), representable por X * X + X * X + X * X, o (3 * X ^ 2, si te gusta).

De manera más general, una F * G con un agujero es una F con un agujero y una G intacta, o una F intacta y una G con un agujero.

Los tipos de datos recursivos a menudo se definen como puntos fijos de polinomios.

data Tree = Leaf | Node Tree Tree

realmente dice Árbol = 1 + Árbol * Árbol. La diferenciación del polinomio te dice los contextos para subárboles inmediatos : no hay subárboles en una hoja; en un Nodo, es un agujero a la izquierda, un árbol a la derecha o un árbol a la izquierda, un agujero a la derecha.

data Tree'' = NodeLeft () Tree | NodeRight Tree ()

Ese es el polinomio diferenciado y presentado como un tipo. Un contexto para un subárbol en un árbol es, por lo tanto, una lista de los pasos de ese árbol.

type TreeCtxt = [Tree'']
type TreeZipper = (Tree, TreeCtxt)

Aquí, por ejemplo, se encuentra una función (código no procesado) que busca en un árbol subárboles que pasan un subárbol de prueba determinado.

search :: (Tree -> Bool) -> Tree -> [TreeZipper]
search p t = go (t, []) where
go :: TreeZipper -> [TreeZipper]
go z = here z ++ below z
here :: TreeZipper -> [TreeZipper]
here z@(t, _) | p t = [z]
| otherwise = []
below (Leaf, _) = []
below (Node l r, cs) = go (l, NodeLeft () r : cs) ++ go (r, NodeRight l () : cs)

El rol de "abajo" es generar los habitantes de Tree ''relevantes para el árbol dado.

La diferenciación de los tipos de datos es una buena forma de hacer que los programas como "búsqueda" sean genéricos .

Answer 2

Mi interpretación es que, la derivada (cremallera) de T es el tipo de todas las instancias que se asemeja a la "forma" de T, pero con exactamente 1 elemento reemplazado por un "agujero".

Por ejemplo, una lista es

List t = 1 []
+ t [a]
+ t^2 [a,b]
+ t^3 [a,b,c]
+ t^4 [a,b,c,d]
+ ... [a,b,c,d,...]

si reemplazamos cualquiera de esos ''a'', ''b'', ''c'' etc. por un agujero (representado como @ ), obtendremos

List'' t = 0 empty list doesn''t have hole
+ 1 [@]
+ 2*t [@,b] or [a,@]
+ 3*t^2 [@,b,c] or [a,@,c] or [a,b,@]
+ 4*t^3 [@,b,c,d] or [a,@,c,d] or [a,b,@,d] or [a,b,c,@]
+ ...

Otro ejemplo, un árbol binario es

data Tree t = TEmpty | TNode t (Tree t) (Tree t)
-- Tree t = 1 + t (Tree t)^2

entonces agregar un agujero genera el tipo:

{-
Tree'' t = 0 empty tree doesn''t have hole
+ (Tree X)^2 the root is a hole, followed by 2 normal trees
+ t*(Tree'' t)*(Tree t) the left tree has a hole, the right is normal
+ t*(Tree t)*(Tree'' t) the left tree is normal, the right has a hole
@ or x or x
/ / / / / /
a b @? b a @?
// // / / // // //
c d e f @? @? e f c d @? @?
-}
data Tree'' t = THit (Tree t) (Tree t)
| TLeft t (Tree'' t) (Tree t)
| TRight t (Tree t) (Tree'' t)

Un tercer ejemplo que ilustra la regla de la cadena es el rosal (árbol variadic):

data Rose t = RNode t [Rose t]
-- R t = t*List(R t)

la derivada dice R'' t = List(R t) + t * List''(R t) * R'' t , que significa

{-
R'' t = List (R t) the root is a hole
+ t we have a normal root node,
* List'' (R t) and a list that has a hole,
* R'' t and we put a holed rose tree at the list''s hole
x
|
[a,b,c,...,p,@?,r,...]
|
[@?,...]
-}
data Rose'' t = RHit [Rose t] | RChild t (List'' (Rose t)) (Rose'' t)

Tenga en cuenta que data List'' t = LHit [t] | LTail t (List'' t) data List'' t = LHit [t] | LTail t (List'' t) .

(Estos pueden ser diferentes de los tipos convencionales donde una cremallera es una lista de "direcciones", pero son isomorfas).

La derivada es una forma sistemática de registrar cómo codificar una ubicación en una estructura, por ejemplo, podemos buscar con: (no del todo optimizado)

locateL :: (t -> Bool) -> [t] -> Maybe (t, List'' t)
locateL _ [] = Nothing
locateL f (x:xs) | f x = Just (x, LHit xs)
| otherwise = do
(el, ctx) <- locateL f xs
return (el, LTail x ctx)
locateR :: (t -> Bool) -> Rose t -> Maybe (t, Rose'' t)
locateR f (RNode a child)
| f a = Just (a, RHit child)
| otherwise = do
(whichChild, listCtx) <- locateL (isJust . locateR f) child
(el, ctx) <- locateR f whichChild
return (el, RChild a listCtx ctx)

y mutar (conectar el agujero) usando la información de contexto:

updateL :: t -> List'' t -> [t]
updateL x (LHit xs) = x:xs
updateL x (LTail a ctx) = a : updateL x ctx
updateR :: t -> Rose'' t -> Rose t
updateR x (RHit child) = RNode x child
updateR x (RChild a listCtx ctx) = RNode a (updateL (updateR x ctx) listCtx)