¿Cómo puedo obtener un accumArray estricto?

Question

Tengo una lista de pares clave-valor y quiero contar cuántas veces se produce cada clave y con qué valores ocurre, pero cuando intento, obtengo un desbordamiento de la pila. Aquí hay una versión simplificada del código que estoy ejecutando:

import Array 
add (n, vals) val = n `seq` vals `seq` (n+1,val:vals) 
histo = accumArray add (0,[]) (0,9) [(0, n) | n <- [0..5000000]] 
main = print histo 

Cuando compilo esto con '-O GHC' y ejecutarlo, me sale "Pila espacio de desbordamiento: tamaño actual 8388608 bytes."

Creo que sé lo que está pasando: accumArray tiene las mismas propiedades que foldl, por lo que necesito una versión estricta de accumArray. Lamentablemente, el único que he encontrado está en Data.Array.Unboxed, que no funciona para una matriz de listas.

La documentación dice que cuando la función de acumulación es estricta, entonces accumArray debería ser también, pero no puedo hacer que esto funcione, y la discusión here afirma que la documentación es incorrecta (al menos para GHC).

¿Hay una versión estricta de accumArray que no sea la de Data.Array.Unboxed? ¿O hay una mejor manera de hacer lo que quiero?

Answer 1

Bueno, strict no significa necesariamente que no se creen thunks, simplemente significa que si un argumento está en la parte inferior, el resultado también es inferior. Pero accumArray no es tan estricto, solo escribe fondos en la matriz si se producen. Realmente no puede hacer otra cosa, ya que debe permitir funciones no estrictas que podrían producir valores definidos de fondos intermedios. Y el analizador de rigor no puede reescribirlo para que la función de acumulación se evalúe en WHNF en cada escritura si es estricta, porque eso cambiaría la semántica del programa de una manera bastante drástica (una matriz que contiene algunos fondos vs. abajo) .

Dicho esto, estoy de acuerdo en que hay una desafortunada falta de funciones estrictas y entusiastas en varias áreas.

para su problema, puede utilizar una pila grande (+RTS -K128M no es suficiente aquí, pero lo hizo 256M), o puede utilizar

import Data.Array.Base (unsafeRead, unsafeWrite) 
import Data.Array.ST 
import GHC.Arr 

strictAccumArray :: Ix i => (e -> a -> e) -> e -> (i,i) -> [(i,a)] -> Array i e 
strictAccumArray fun ini (l,u) ies = case iar of 
             Array _ _ m barr -> Array l u m barr 
    where 
    iar = runSTArray $ do 
     let n = safeRangeSize (l,u) 
      stuff = [(safeIndex (l,u) n i, e) | (i, e) <- ies] 
     arr <- newArray (0,n-1) ini 
     let go ((i,v):ivs) = do 
       old <- unsafeRead arr i 
       unsafeWrite arr i $! fun old v 
       go ivs 
      go [] = return arr 
     go stuff 

Con una escritura estricta, los procesadores se mantienen pequeñas, por lo no hay desbordamiento de pila Pero ten cuidado, las listas ocupan mucho espacio, de modo que si tu lista es demasiado larga, es posible que te agotes.

Otra opción sería utilizar una Data.Map (o Data.IntMap, si la versión de containers es 0.4.1.0 o posterior) en lugar de una matriz, ya que viene con insertWith', que fuerza el resultado de la función de combinación en uso. El código podría ser, por ejemplo

import qualified Data.Map as M -- or Data.IntMap 
import Data.List (foldl') 

histo :: M.Map Int (Int,[Int]) -- M.IntMap (Int,[Int]) 
histo = foldl' upd M.empty [(0,n) | n <- [0 .. 15000000]] 
    where 
    upd mp (i,n) = M.insertWith' add i (1,[n]) mp 
    add (j,val:_) (k,vals) = k `seq` vals `seq` (k+j,val:vals) 
    add _ pr = pr -- to avoid non-exhaustive pattern warning 

Las desventajas de usar un Map son

• la función de la combinación debe tener un tipo a -> a -> a, por lo que debe ser un poco más complicado en su caso.
• una actualización es O (tamaño de registro) en lugar de O (1), por lo que para histogramas grandes, será considerablemente más lento.
• Map sy IntMap s tienen cierta sobrecarga de contabilidad, por lo que utilizará más espacio que una matriz. Pero si la lista de actualizaciones es grande en comparación con la cantidad de índices, la diferencia será insignificante (la sobrecarga es k palabras por clave, independientemente del tamaño de los valores) en este caso, donde el tamaño de los valores crece con cada actualizar.