Opened 5 years ago

Closed 5 years ago

Last modified 5 years ago

#4261 closed proposal (duplicate)

Add strict version of foldlWithKey to Map

Reported by: tibbe Owned by:
Priority: normal Milestone:
Component: libraries (other) Version:
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Revisions:

Description

There's currently no strict left (pre-order) fold for Maps, making it impractical to do simple things like summing all the values in the map. The attached patch adds a strict foldlWithKeys' function that generates optimal core for code like:

module Test (test) where

import qualified Data.Map as M

test :: M.Map Int Int -> Int
test m = M.foldlWithKey' (\n k v -> n + k + v) 0 m

If we look at the core we see that the Int accumulator is unboxed like we'd hope:

test_$s$wgo2 :: Data.Map.Map Int Int -> Int# -> Int#
test_$s$wgo2 =
  \ (sc_smi :: Data.Map.Map Int Int)
    (sc1_smj :: Int#) ->
    case sc_smi of _ {
      Data.Map.Tip -> sc1_smj;
      Data.Map.Bin _ kx_ali x_alj l_alk r_all ->
        case test_$s$wgo2 l_alk sc1_smj of ww_slW { __DEFAULT ->
        case kx_ali of _ { I# y_alD ->
        case x_alj of _ { I# y1_XlT ->
        test_$s$wgo2
          r_all (+# (+# ww_slW y_alD) y1_XlT)
        }
        }
        }
    }

$wtest :: Data.Map.Map Int Int -> Int#
$wtest =
  \ (w_slZ :: Data.Map.Map Int Int) ->
    test_$s$wgo2 w_slZ 0

test :: Data.Map.Map Int Int -> Int
test =
  __inline_me (\ (w_slZ :: Data.Map.Map Int Int) ->
                 case $wtest w_slZ of ww_sm2 { __DEFAULT ->
                 I# ww_sm2
                 })

Discussion deadline: 2 weeks

Attachments (1)

strict-foldl-with-key.dpatch (3.6 KB) - added by tibbe 5 years ago.

Download all attachments as: .zip

Change History (4)

Note: See TracTickets for help on using tickets.