1voto
Componentes unidos en Haskell
por

josejuan

hace 20 días

Se da la solución para cualquier representación de grafo, el coste será O(|V|) mas el coste de obtener claves y adyancentes de la representación en cada caso. (El coste realmente es O(n log n) porque se usa Data.Set pero podría usarse un hash, etc...).

0votos
Sistemas de Post en Haskell
por

josejuan

hace 1 mes

Ésta es la más eficiente, tiene coste lineal (en la palabra total generada). Monta un árbol con las bifurcaciones del programa de entrada. De todos modos insisto que ésto es reinventar la rueda, compilándolo a código máquina, tenemos incluso predicción de salto (el pattern matching compila a condiciones de código máquina).

0votos
Sistemas de Post en Haskell
por

josejuan

hace 1 mes

Si no es por no implementar explícitamente los pasos de la máquina, es que usando pattern matching podemos usar Haskell directamente y además no será interpretado, sino que se compilará a código máquina. Pero ahí va.