shampoo - Haskell Tree splitting: ¿Puede alguien explicar esta línea?

haskell shampoo

Question

split s (Root x lst rst)
| s < x = let (nlt, nrt) = split s lst in
(nlt, Root x nrt rst)

¿Puede alguien explicar esta línea? Realmente no entiendo la parte de let .

Intenté pensarlo, no tengo idea si lo hice bien: (nlt, nrt) , al resultado de split s lst ; y split s lst será (nlt, Root x nrt rst)

¿Es asi?

Aquí está el código completo:

split :: Ord a => a -> Tree a -> (Tree a, Tree a)
split _ Empty = (Empty, Empty)
split s (Root x lst rst)
| s < x = let (nlt, nrt) = split s lst in
(nlt, Root x nrt rst)
| s > x = let (nlt, nrt) = split s rst in
(Root x lst nlt, nrt)

Answer 1

unimos (nlt, nrt) al resultado de split s lst

Yup - split s lst es un par, y le estamos dando los nombres nlt y nrt a los dos elementos del par.

y split s lst será (nlt, Root x nrt rst)

No, la split s (Root x lst rst) (nlt, Root x nrt rst) split s (Root x lst rst) (el resultado de toda la función) será (nlt, Root x nrt rst) .

¿Pero qué hace toda la función?

split :: Ord a => a -> Tree a -> (Tree a, Tree a)
split _ Empty = (Empty, Empty)
split s (Root x lst rst)
| s < x = let (nlt, nrt) = split s lst in
(nlt, Root x nrt rst)
| s > x = let (nlt, nrt) = split s rst in
(Root x lst nlt, nrt)

Probemos eso en algunos datos de muestra:

> split 300 (Root 512 (Root 256 (Root 128 Empty Empty) (Root 384 Empty Empty)) Empty)
(Root 256 (Root 128 Empty Empty) Empty,Root 512 (Root 384 Empty Empty) Empty)

Así que tomamos un árbol que tenía 512 como raíz, y todos los elementos más pequeños que él en el subárbol izquierdo, y lo dividimos para que el primer árbol esté formado por entradas por debajo de 300, con las más de 300 en el segundo. Eso se parece a esto:

¿Cómo funciona la línea en cuestión?

Primero reescribamos el código con nombres expandidos:

split :: Ord a => a -> Tree a -> (Tree a, Tree a)
split _ Empty = (Empty, Empty)
split s (Root x left_subtree right_subtree)
| s < x = let (new_left_tree, new_right_tree) = split s left_subtree in
(new_left_tree, Root x new_right_tree right_subtree)
| s > x = let (new_left_tree, new_right_tree) = split s right_subtree in
(Root x left_subtree new_left_tree, new_right_tree)

La guardia |s < x significa que estamos en el caso de que este x deba ir a la derecha.

Primero dividimos el subárbol izquierdo split s left_subtree , dándonos un new_left_tree y new_right_tree . El new_left_tree es lo que debería ir a la izquierda, pero el new_right_tree se combina con x y el right_subtree original para formar los bits que van a la derecha de s .

¿Qué podemos aprender acerca de la función de eso?

El right_subtree se queda solo, porque s pertenece a la izquierda de x , por lo que la función se supone que el árbol ya está ordenado en el sentido de que en Root xlr , todo en l está debajo de x y todo en r está arriba de x .

El left_subtree se divide, porque parte de él puede ser menor que s otros bits más que s .

La parte de split s left_subtree que ahora pertenece a la derecha (porque es más que s ) se llama new_right_tree , y porque todo el left_subtree era menor que x y right_subtree , todo el new_right_tree debería estar a la izquierda de x y right_subtree . Es por eso que hacemos que Root x new_right_tree right_subtree sea ​​la respuesta de la mano derecha en el par (y new_left_tree a la izquierda del par).

Aquí hay un diagrama de antes y después:

¿Por qué no tener nombres más descriptivos entonces?

Buena pregunta. Vamos a hacerlo:

split :: Ord a => a -> Tree a -> (Tree a, Tree a)
split _ Empty = (Empty, Empty)
split s (Root this below_this above_this)
| s < this = let (below_this_below_s, below_this_above_s) = split s below_this in
(below_this_below_s, Root this below_this_above_s above_this)
| s > this = let (above_this_below_s, above_this_above_s) = split s above_this in
(Root this below_this above_this_below_s, above_this_above_s)

Bien, creo que responde a mi pregunta: ¡a veces los nombres descriptivos también pueden ser confusos!