haskell - victimismo - falsa vivencia

Haskell: falacias corecursivas comunes

Question

Así que estaba pensando en un algoritmo de distancia gráfica esta noche, y se me ocurrió esto mientras conducía el automóvil:

module GraphDistance where
import Data.Map

distance :: (Ord a) => a -> Map a [a] -> Map a Int
distance a m = m'' 
  where m'' = mapWithKey d m
        d a'' as = if a == a'' then 0 else 1 + minimum (Prelude.map (m''!) as)

Al principio, estaba bastante orgulloso de mí mismo, ya que parecía tan elegante. Pero luego me di cuenta de que no funcionaría, la corecursion podría quedar atrapada en un bucle.

Tuve que codificarlo para convencerme a mí mismo:

ghci> distance 1 $ fromList [(0,[1]),(1,[0,2]),(2,[1,3]),(3,[2])]
fromList [(0,1),(1,0),(2,^CInterrupted.

Pero ahora creo que lo he pensado bien.

¿Hay una lista de errores comunes y antipatrones cuando se trata de datos de base que puedo leer, para poder entrenar mi cerebro para que piense de forma central? La experiencia me ha capacitado bastante bien para pensar a través de datos no-académicos, pero me gustaría aprender de los demás si puedo.

Answer 1

Bueno, en realidad solo hay un error fundamental cuando se trata de datos corecursive, ¡y eso es usar descuidadamente la recursión!

Corecursion implica que los datos se generan incrementalmente en algún sentido. Su función de distancia gráfica es instructiva aquí, porque parece que debería funcionar, así que piense dónde debe estar la parte incremental: el punto de partida es una distancia de 0 desde un nodo a sí mismo, de lo contrario uno mayor que la distancia mínima entre su propio vecinos inmediatos. Por lo tanto, esperaríamos que cada valor de distancia fuera incremental, lo que significa que necesitamos que ellos mismos sean adecuadamente correlativos.

La recursión en cuestión, entonces, se produce debido a la combinación de (+) y minimum : al encontrar el mínimo, 1 siempre será menor que 1 + n , sin necesidad de preocuparse por lo que es n ... pero no hay forma para comparar Int s sin calcular todo el valor.

En resumen, el algoritmo espera poder comparar cuántas veces (1 +) se aplicó a 0 solo hasta donde fue necesario; es decir, quiere números naturales perezosos definidos usando "cero" y "sucesor".

Mirad:

data Nat = Z | S Nat

natToInt :: Nat -> Int
natToInt Z = 0
natToInt (S n) = 1 + natToInt n

instance Show Nat where show = show . natToInt

instance Eq Nat where
    Z == Z = True
    (S n1) == (S n2) = n1 == n2
    _ == _ = False

    Z /= Z = False
    (S n1) /= (S n2) = n1 /= n2
    _ /= _ = True


instance Ord Nat where
    compare Z Z = EQ
    compare Z (S _) = LT
    compare (S _) Z = GT
    compare (S n1) (S n2) = compare n1 n2

Y luego en GHCi:

> distance 1 $ fromList [(0,[1]),(1,[0,2]),(2,[1,3]),(3,[2])]
fromList [(0,1),(1,0),(2,1),(3,2)]

Prueba de que su algoritmo funciona ^[0] ; su implementación fue simplemente incorrecta.

Ahora, como una ligera variación, apliquemos su algoritmo a un gráfico diferente:

> distance 1 $ fromList [(0,[1]),(1,[0]),(2,[3]),(3,[2])]

... ¿qué esperamos que haga esto? ¿Cuál es la distancia desde el nodo 1 para los nodos 2 o 3?

Ejecutarlo en GHCi tiene el resultado obvio:

fromList [(0,1),(1,0),(2,^CInterrupted.

Sin embargo, el algoritmo funciona correctamente en este gráfico . ¿Puedes ver el problema? ¿Por qué colgó en GHCi?

En resumen, debe distinguir claramente entre dos formas que no pueden combinarse libremente:

• Datos vagos, posiblemente infinitos, generados corecursively
• Datos finitos, consumidos recursivamente

Ambas formas se pueden transformar de una manera independiente de la estructura (por ejemplo, el map funciona en listas finitas e infinitas). Codata se puede consumir de forma incremental, impulsado por un algoritmo corecursive; los datos se pueden generar recursivamente, limitados por un algoritmo recursivo.

Lo que no se puede hacer es consumir codata de manera recursiva (por ej., Doblar a la izquierda una lista infinita) o generar datos de manera coherente (raro en Haskell, debido a la pereza).

[0] : en realidad, fallará en algunas entradas (por ejemplo, algunos gráficos desconectados), pero ese es un problema diferente.