manejar - Haskell: profundidad para cada nodo en árbol binario utilizando la mónada Reader

ejercicio arboles binarios

Question

Escribí el siguiente código. Está funcionando y usando la mónada Reader .

¿Podría darme algunas pistas sobre el estilo del código en Haskell? Principalmente, me refiero a mónadas: soy novato.

import Control.Monad.Reader

data Tree a = Node a (Tree a) (Tree a)
            | Empty

renumberM :: Tree a -> Reader Int (Tree Int)
renumberM (Node _ l r) = ask >>= (/x -> 
                         return (Node x (runReader (local (+1) (renumberM l)) x) 
                                        (runReader (local (+1) (renumberM r)) x)))
renumberM Empty = return Empty

renumber'''' :: Tree a -> Tree Int
renumber'''' t = runReader (renumberM t) 0

Answer 1

No es necesario entrar y salir del Reader la manera que lo hace aquí usando runReader ; en cambio, puedes reescribirlo como

renumberR :: Tree a -> Reader Int (Tree Int)
renumberR (Node _ l r) = do
    x <- ask
    l'' <- local (+1) (renumberR l)
    r'' <- local (+1) (renumberR r)
    return (Node x l'' r'')
renumberR Empty = return Empty

Sin embargo, puedes escribirlo aún mejor usando solo la interfaz de Reader :

renumberR (Node _ l r) =
    Node <$> ask <*> local (+1) (renumberR l) <*> local (+1) (renumberR r)
renumberR Empty = pure Empty

Tenga en cuenta que he cambiado el nombre de su función para renumberR para enfatizar el hecho de que se ejecuta en Reader , pero no necesariamente utilizando su interfaz monádica.

Answer 2

Quiero mostrarte que tu idea es una instancia de un concepto más general: compresión . Aquí hay una versión de su programa que emplea un estilo más simple y más funcional.

Funcionantes Aplicativos

Aquí está la definición de Applicative :

class Functor f => Applicative f where
    pure :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b

Se podría decir que un tipo fx es una estructura f contiene algunos valores x . La función <*> toma una estructura de funciones ( f (a -> b) ) y la aplica a una estructura de argumentos ( fa ) para producir una estructura de resultados ( fb ).

Aplicadores Zippy

Una forma de hacer de Tree un funtor aplicativo es haciendo <*> atravesar los dos árboles en el paso de bloqueo, comprimiéndolos juntos como lo hace zip con las listas. Cada vez que encuentre un Node en el árbol de funciones y un Node en el árbol de argumentos, puede sacar la función y aplicarla al argumento. Tienes que dejar de atravesar cuando llegues al final de cualquiera de los árboles.

instance Applicative Tree where
    pure x = let t = Node x t t in t
    Empty <*> _ = Empty
    _ <*> Empty = Empty
    (Node f lf rf) <*> (Node x lx rx) = Node (f x) (lf <*> lx) (rf <*> rx)

instance Functor Tree where
    fmap f x = pure f <*> x  -- as usual

pure x genera un árbol infinito de x s. Esto funciona bien porque Haskell es un lenguaje perezoso.

     +-----x-----+
     |           |
  +--x--+     +--x--+
  |     |     |     |
+-x-+ +-x-+ +-x-+ +-x-+
|   | |   | |   | |   |
          etc

Entonces la forma del árbol t <*> pure x es la misma que la forma de t : solo dejas de atravesar cuando encuentras un Empty , y no hay ninguno en pure x . (Lo mismo se aplica a pure x <*> t )

Esta es una forma común de hacer que una estructura de datos sea una instancia de Applicative . Por ejemplo, la biblioteca estándar incluye ZipList , cuya instancia Applicative es muy similar a la de nuestro árbol:

newtype ZipList a = ZipList { getZipList :: [a] }
instance Applicative ZipList where
    pure x = ZipList (repeat x)
    ZipList fs <*> ZipList xs = ZipList (zipWith ($) fs xs)

Una vez más, pure genera un ZipList infinito y <*> consume sus argumentos en lock-step.

El zippy prototipo Aplicable, si lo desea, es el "lector" Aplicativo (->) r , que combina funciones al aplicarlas todas a un argumento fijo y recoger los resultados. Por lo tanto, todos los funtores Representable admiten (al menos) una instancia Applicable rápida.

Utilizando alguna maquinaria Aplicable , podemos generalizar el archivo zip del Prelude a cualquier funcionador aplicativo (aunque solo se comportará exactamente como zip cuando el Applicative sea ​​de naturaleza zippy; por ejemplo, con la instancia Applicative regular para [] zipA le dará el Cartesiano producto de sus argumentos).

zipA :: Applicative f => f a -> f b -> f (a, b)
zipA = liftA2 (,)

Etiquetado como Zipping

El plan es comprimir el árbol de entrada junto con un árbol infinito que contenga la profundidad de cada nivel. El resultado será un árbol con la misma forma que el árbol de entrada (porque el árbol de profundidades es infinito), pero cada nodo se etiquetará con su profundidad.

depths :: Tree Integer
depths = go 0
    where go n = let t = go (n+1) in Node n t t

Así es como se ve la depths :

     +-----0-----+
     |           |
  +--1--+     +--1--+
  |     |     |     |
+-2-+ +-2-+ +-2-+ +-2-+
|   | |   | |   | |   |
          etc

Ahora que hemos configurado las estructuras que necesitamos, etiquetar un árbol es fácil.

labelDepths :: Tree a -> Tree (Integer, a)
labelDepths = zipA depths

Volver a etiquetar un árbol tirando las etiquetas originales, como lo especificó originalmente, también es fácil .

relabelDepths :: Tree a -> Tree Integer
relabelDepths t = t *> depths

Una prueba rápida:

ghci> let myT = Node ''x'' (Node ''y'' (Node ''z'' Empty Empty) (Node ''a'' Empty Empty)) (Node ''b'' Empty Empty)
ghci> labelDepths myT
Node (0,''x'') (Node (1,''y'') (Node (2,''z'') Empty Empty) (Node (2,''a'') Empty Empty)) (Node (1,''b'') Empty Empty)

    +--''x''-+                      +--(0,''x'')-+
    |      |    labelDepths       |          |
 +-''y''-+  ''b''       ~~>      +-(1,''y'')-+  (1,''b'')
 |     |                     |         |
''z''   ''a''                 (2,''z'')   (2,''a'')

Puede idear diferentes esquemas de etiquetado variando el árbol que recorre. Aquí hay una que te dice el camino que tomaste para llegar a un nodo:

data Step = L | R
type Path = [Step]
paths :: Tree Path
paths = go []
    where go path = Node path (go (path ++ [L])) (go (path ++ [R]))

         +--------[ ]--------+
         |                   |
    +---[L]---+         +---[R]---+
    |         |         |         |
+-[L,L]-+ +-[L,R]-+ +-[R,L]-+ +-[R,R]-+
|       | |       | |       | |       |
                  etc

(El anidamiento ineficiente de llamadas a ++ arriba puede mitigarse usando listas de diferencias ).

labelPath :: Tree a -> Tree (Path, a)
labelPath = zipA paths

A medida que continúe aprendiendo Haskell, obtendrá una mejor detección cuando un programa sea un ejemplo de un concepto más profundo. La configuración de estructuras generales, como hice con la instancia Applicative anterior, rápidamente paga dividendos en la reutilización del código.