haskell / haskell/containers

Fuse Map.map with foldrFB and foldlFB

Open
#189 0 comments 0 reactions 0 assignees View on GitHub
Map performance
Dominant language
Haskell
Stars
355
Forks
194
Avg merge
3d 4h
Merged PRs (30d)
4

Description

We have a rule

``` haskell
{-# RULES "Map.toAscList" [~1] forall m . toAscList m = build (\c n -> foldrFB (\k x xs -> c (k,x) xs) n m) #-}
```

and a similar one for `toDescList`. I think we probably want to add rules like

``` haskell
{-# RULES "Map.foldrFB/map" forall (m :: Map k v) (f :: Int -> v' -> r -> r) (g :: v -> v') (n :: r) .
foldrFB f n (map g m) = foldrFB (\i x r -> f i (g x) r) n m #-}
{-# RULES "Map.foldrFB/mapWithKey" forall (m :: Map k v) (f :: Int -> v' -> r -> r) (g :: Int -> v -> v') (n :: r) .
foldrFB f n (mapWithKey g m) = foldrFB (\i x r -> f i (g i x) r) n m #-}
```

and similarly for `foldlFB`. These will ensure, for example, that mapping over a `Map` and then converting the result to a list will not produce intermediate structures.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.