<div dir="ltr"><div class="gmail_quote"><div dir="ltr">Le ven. 19 juin 2015 à 19:03, Michael Orlitzky <<a href="mailto:michael@orlitzky.com">michael@orlitzky.com</a>> a écrit :<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
loop :: [Int] -> (Map Int Int) -> (Map Int Int)<br>
loop elems initial_map =<br>
  foldr update_map initial_map elems<br>
  where<br>
    update_map :: Int -> (Map Int Int) -> (Map Int Int)<br>
    update_map x m =<br>
      let k = key_from_elem x in<br>
                case (M.lookup k m) of<br>
                  Nothing -> insert k x m<br>
                  Just v  -> insert k (v + x) m<br></blockquote><div><br></div><div> While this code will do the right thing, it won't do it efficiently, at all !<br><br></div><div>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"<br><br></div><div>In other words :<br><br></div><div>import qualified Data.Map.Strict as M<br></div><div><br></div><div>countingMap :: [(key, Int)] -> Map key Int<br></div><div>countingMap kvs = foldl' update M.empty kvs<br></div><div>   where update (k,v) m = M.insertWith (+) k v m<br><br></div><div>Since this is a very common need, there's even a combinator to do this :<br><br><div>countingMap :: [(key, Int)] -> Map key Int<br></div>countingMap kvs = M.fromListWith (+) kvs<br><br></div><div>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).<br><br>-- <br></div><div>Jedaï<br></div></div></div>