Buscando una estructura similar a una matriz eficiente que admita "replace-one-member" y "append"

Question

Como ejercicio escribí an implementation del longest increasing subsequence algorithm, inicialmente en Python pero me gustaría traducir esto a Haskell. En pocas palabras, el algoritmo implica un pliegue sobre una lista de enteros, donde el resultado de cada iteración es una matriz de enteros que es resultado de cambiando un elemento de o añadiendo un elemento a el resultado anterior.

Por supuesto, en Python solo puede cambiar un elemento de la matriz. En Haskell, podrías reconstruir la matriz al reemplazar un elemento en cada iteración, pero eso parece un desperdicio (copiar la mayor parte de la matriz en cada iteración).

En resumen lo que estoy buscando es una estructura eficiente de datos Haskell que es una colección ordenada de objetos 'n' y apoya las operaciones: lookup i, replace i foo y append foo (donde i está en [0..n- 1]). Sugerencias?

Answer 1

Quizás el tipo Seq estándar de Data.Sequence. No es O bien (1), pero es bastante bueno:

• index (su lookup) y adjust (su replace) son O (log (min (índice,   longitud   -   índice)))

• (><) (su append) es O (log (min (length1,   longitud2)))

Está basado en una estructura de árbol (en concreto, un árbol 2-3 dedo), por lo que debe tener buenas propiedades para compartir (lo que significa que no va a copiar toda la secuencia de modificaciones incrementales, y las realizará más rápido también). Tenga en cuenta que Seq s son estrictas, a diferencia de las listas.

Answer 2

Me gustaría tratar de usar matrices mutables en este caso, preferiblemente en la mónada ST.

Las principales ventajas serían hacer la traducción más sencilla y hacer las cosas simples y eficientes.

La desventaja, por supuesto, es perder en pureza y capacidad de compilación. Sin embargo, creo que esto no debería ser tan importante, ya que no creo que haya muchos casos en los que le gustaría mantener los estados intermedios de algoritmo.