[Haskell-cafe] Strict version of Data.Map.map

[Felipe Lessa]

On Thu, Feb 26, 2009 at 2:13 PM, Edsko de Vries <devriese at cs.tcd.ie> wrote:
> On Thu, Feb 26, 2009 at 12:45:09PM -0300, Felipe Lessa wrote:
>> I'd advise you to see Control.Parallel.Strategies, specially the
>> NFData class and the rnf function.
>
> What is the time complexity of running rnf on a Data.Map? If it is O(n),
> then surely running rnf on my map after every 'map' operation is hardly
> going to speed things up?

I guess so. Maybe using mapAccum helps:

  import qualified Data.Map as M

  strictMap :: (a -> b) -> M.Map k a -> M.Map k b
  strictMap f m = case M.mapAccum f' () m of
                    ((), m') -> m'
      where f' () x = x' `seq` ((), x') where x' = f x

  testStrictness mapper = m `seq` "Not strict."
      where m = mapper (const e) (M.singleton () ())
            e = error "Strict!" :: ()


Testing:

*Main> testStrictness M.map
"Not strict."
*Main> testStrictness strictMap
"*** Exception: Strict!

Don't know about efficiency, though :).

HTH,

-- 
Felipe.