Implement mapM for sequences
Nobody has claimed this yet.
Assessment
- Difficulty
- 5/5
- Estimated time
- Over a week
- Newbie friendliness
- 25/100
Research direction
No file or test path is named. Start by locating the sequence Traversable instance and the Node2 and Deep constructors shown in the issue, then compare their default mapM behavior with the proposed strict construction. Done means an optimized implementation exists for the relevant sequence shapes and its behavior is covered by the project's existing tests.
Written by the indexing model from the issue text.
Description
The Traversable class includes a method
class Traversable t where
...
mapM :: Monad m => (a -> m b) -> t a -> m (t b)
This is normally allowed to take its default definition of mapM = traverse. However, I think it typically makes more sense to use this method as an opportunity to optimize for common, non-Identity, "strict" monads, such as IO and strict StateT. What does this mean in practice? Instead of building up an enormous pile of closures that will eventually be evaluated to produce the result sequence, we can build the result as we go. It could look something like this:
mapM f (Node2 n (Elem a) (Elem b)) = liftA2 (\a' b' -> Node2 n (Elem a') (Elem b')) (f a) (f b)
mapM f (Node2 n (a :: Node _) b) = do
!a' <- f a
!b' <- f b
pure (Node2 n a' b')
-- Similar for top-level and other Digits
mapM f (Deep n pr m sf) = do
!pr' <- mapM f pr
!m' <- mapM (mapM f) m
!sf' <- mapM f sf
pure (Deep n pr' m' sf')
The idea is that we build each node as soon as its children are available, rather than risking waiting until all actions are performed to construct anything.
- Dominant language
- Haskell
- Stars
- 356
- Forks
- 195
- Avg merge
- 2d 17h
- Merged PRs (30d)
- 2
Getting set up
- No Dockerfile or Docker Compose file
- No pull request template
- Read the contributing guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from haskell/containers
-
major-release strictness Tree
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
haskell/containers#1260 ·
-
Map performance Set
Difficulty 5/5 Over a week Newbie friendliness 35/100
haskell/containers#1263 · 5 comments ·
-
low-hanging-fruit performance Seq
Difficulty 4/5 3-5 days Newbie friendliness 43/100
haskell/containers#1262 · 2 comments ·
-
Difficulty 5/5 Over a week Newbie friendliness 35/100
haskell/containers#1261 · 11 comments ·
-
IntSet low-hanging-fruit performance
Difficulty 3/5 1-2 days Newbie friendliness 58/100
haskell/containers#1251 ·
All issues in haskell/containers
Similar issues
-
Difficulty 2/5 1-3 hours Newbie friendliness 62/100
haskell-beam/beam#828 ·
-
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
simplex-chat/simplex-chat#7755 ·
Maintainers usually reply within 1 day
-
bug core-libs
Difficulty 2/5 1-3 hours Newbie friendliness 68/100
-
content good first issue
Difficulty 2/5 Under an hour Newbie friendliness 88/100
StudentSuite/awesome-skills-plugins-for-students#312 ·
Maintainers usually reply within 1 day
-
Difficulty 1/5 Under an hour Newbie friendliness 96/100
alunduil/collection-json.hs#415 ·
Maintainers usually reply within 1 day