Implement mapM for sequences
- Dominant language
- Haskell
- Stars
- 355
- Forks
- 194
- Avg merge
- 3d 4h
- Merged PRs (30d)
- 4
Description
The `Traversable` class includes a method
```haskell
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:
```haskell
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.
Contributor guide
Assessment
This issue has not been assessed yet.