gistfile1.txt

{{
Un árbol se representa como una lista de arrays
    
    type Row = Array U DIM1 Int

aunque parezca feo, realmente es precioso, porque abstrae el tipo
de almacenamiento, tipos de índices soportados y el tipo de dato.
    
En C# sería algo como
    
    class Array<U, D, T> ...

Estos array tienen varias operaciones, la obvia de recuperar un dato
dado un índice
    
    miArray ! miIndice

que en C# sería algo como

    miArray [ miIndice ]

Pero resulta que índice no tiene porqué ser un simple número entero,
de ahí que hay que construirlo, como

    miIndice = Z :. 34

que en C# sería algo como

    miIndice = new Indice(34)

Calcular los costes mínimos (para llegar abajo) de todos los nodos es

    costsTree :: Monad m => Tree -> m (Row, Tree) 

lo de la mónada podemos ignorarlo y básicamente dado un árbol, nos dará
la lista de costes de la primera fila (los corredores) y todo el árbol con
los costes mínimos de cada nodo.

La operación de reducción es acumular los costes de abajo del árbol a arriba.

Pero claro, los costes acumulados de la última fila con sus mismos costes, de ahí

    costsTree (x:[]) = return (x, [x])

es decir, cuando es la última fila, los costes de la "primera" fila es ella misma y
el árbol es sólo ella misma.

Pero si no es la última fila,

    costsTree (x:xs) = do

lo que hacemos es calcular todo lo que hay abajo

        (y, ys) <- costsTree xs

y a nuestra fila le sumamos los totales obtenidos

        z       <- x <+ y 

y así el árbol es el subárbol añadiendo nuestra fila

        return (z, z:ys) 

Esa operación de "suma de filas", lo que hace es acumular el mejor coste parcial que
haya abajo hacia arriba, es decir, si tenemos

    A:            a    b    c

    B:         S1   S2   S3   S4

donde `a..c` son los costes aun no totalizados y `S1..S4` los totales ya
calculados "de abajo", si los índices en ambas filas empiezan en 0, tenemos
que es

        Ai = Ai + If Si <= Si+1 Then Si Else Si+1

la función compuesta `computeP $ traverse` computa en paralelo el "atravesar" (recorrer)
el array que sea (en este caso A), por lo que podemos leer la función (puesta como
operador) de la siguiente forma

Acumular los costes hacia arriba consiste en combinar dos filas y obtener una nueva

    (<+) :: Monad m => Row -> Row -> m Row 

que resulta de obtener la "best" (mejor) alternativa para cada elemento de "A"

    a <+ b = computeP $ traverse a id best 

el mejor elemento es aquell con menor coste entre el Bi y el Bi+1

             where best _ z@(Z :. i) = a!z + if cL <= cR then cL else cR 
                                       where cL  = b!z 
                                             cR  = b!(Z :. (i + 1)) 

el `_` es porque no usamos el primer argumento que nos dan (no lo usamos).
el `Z :. i` es porque un índice en el array no es un simple número, hay que construir el índice.
el `z@(Z :. i)` es un "pattern match" con la arroba, lo que conseguimos es tener a la vez todo
                el índice ya construido y el número `i` que contiene (así en `a!z` y `b!z` no
                tenemos que construirlo otra vez).

}}