haskell / haskell/containers

Implement mapM for sequences

Open
#838 0 comments 0 reactions 0 assignees View on GitHub
performance Seq
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

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.