[Haskell-beginners] Adapting code from an imperative loop

[Chaddaï Fouché]

Le ven. 19 juin 2015 à 19:03, Michael Orlitzky <michael at orlitzky.com> a
écrit :

> loop :: [Int] -> (Map Int Int) -> (Map Int Int)
> loop elems initial_map =
>   foldr update_map initial_map elems
>   where
>     update_map :: Int -> (Map Int Int) -> (Map Int Int)
>     update_map x m =
>       let k = key_from_elem x in
>                 case (M.lookup k m) of
>                   Nothing -> insert k x m
>                   Just v  -> insert k (v + x) m
>

 While this code will do the right thing, it won't do it efficiently, at
all !

First (and huge) problem is using foldr : starting from the end of the list
is the wrong move here if you want to consume your Int stream efficiently
(which you probably do and which is vital if the stream is big). So you
should be using foldl' and the strict version of Map (Data.Map.Strict).
Also, though less important, looking up a key then updating the value with
insert is wasteful : you will be doing the search twice, instead of using
one of the nice combinators of Data.Map which find and update a value in
one pass like "insertWith (+) k x m"

In other words :

import qualified Data.Map.Strict as M

countingMap :: [(key, Int)] -> Map key Int
countingMap kvs = foldl' update M.empty kvs
   where update (k,v) m = M.insertWith (+) k v m

Since this is a very common need, there's even a combinator to do this :

countingMap :: [(key, Int)] -> Map key Int
countingMap kvs = M.fromListWith (+) kvs

At which point you may even use directly this code and forgo creating a
function for it (except if you're using it several times or as a minor step
in a big pipeline where you would like to label each step clearly).

-- 
Jedaï
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20150619/876fcafd/attachment-0001.html>