[Haskell-cafe] Mutable arrays

Chaddaï Fouché chaddai.fouche at gmail.com
Fri Feb 8 09:10:00 EST 2008


Après avoir un peu manipulé la solution de John pour qu'elle fasse la même
chose que la mienne, je peux affirmer qu'elle est légèrement moins rapide
(c'est infime et normal vu que ses leftFold passent plus d'informations),
mais que les deux solutions ont au moins cet avantage d'être rapides (2s sur
10M de Double) et en mémoire parfaitement constante :

----
import Data.Array.MArray
import Control.Monad
import Data.Array.IO
import System

maxArr a = liftM (foldl1' max) (getElems a)

foldlA :: (MArray a e m, Ix i) => (r -> e -> r) -> r -> a i e -> m r
foldlA f a arr = getBounds arr >>=
                 foldM (\a->a `seq` liftM $ f a) a
                           . map (readArray arr) . range

foldl1A :: (MArray a e m, Ix i) => (e -> e -> e) -> a i e -> m e
foldl1A f arr = flip (foldlA f) arr =<< readArray arr . fst =<< getBounds
arr

foldMA :: (MArray a e m, Ix i) => (r -> e -> m r) -> r -> a i e -> m r
foldMA f a arr = getBounds arr >>=
                 foldM (\a->a `seq` (>>= f a)) a
                           . map (readArray arr) . range

modifyArray :: (MArray a e m, Ix i) => (e -> e) -> a i e -> m ()
modifyArray f arr = mapM_ (modifyElement f arr) . range =<< getBounds arr

modifyElement :: (MArray a e m, Ix i) => (e -> e) -> a i e -> i -> m ()
modifyElement f arr i = writeArray arr i . f =<< readArray arr i

main = do
  [n] <- getArgs
  a <- (newListArray (0, 10 ^ read n) [1..] :: IO (IOUArray Int Double))
  maxE <- foldl1A max a
  modifyArray (* (1/maxE)) a
  print =<< readArray a (10 ^ read n)
----

En tout cas il serait agréable d'avoir quelques unes de ces fonctions dans
les librairies standards, vu qu'elles sont généralement utiles et très
efficace. Je n'utilise pas les langages fonctionnels pour avoir à écrire des
boucles explicites sur mes structures de données !! ;-)
(et comme on l'a vu, pour un débutant, l'écriture d'une généralisation
efficace de ces boucles n'est pas si triviale qu'il y paraît).

-- 
Jedaï
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20080208/4f576221/attachment.htm


More information about the Haskell-Cafe mailing list