IntersectMBO / IntersectMBO/cardano-base

Efficient implementation for `StrictSeq` operations

Open
#595 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Haskell
Stars
105
Forks
54
Avg merge
9d 2h
Merged PRs (30d)
4

Description

Many operations on `StrictSeq` simply rely on the underlying lazy `Seq` implementation that is simply followed by a forcing all of the elements.

I haven't checked, but I am sure most of the can be implemented in a more efficient manner.

For example `Functor` instance can do an `fmap` in one pass, instead of two, since `Seq` does have a `Monad` instance:
```diff
instance Functor StrictSeq where
fmap f (StrictSeq s) = StrictSeq (f <$!> s)
```
Another example from a PR review:

This is a sub-optimal implementation IMHO, since `forceElemsToWHNF` and consequently `forceToStrict` cause a redundant iteration over the resulting data structure, just to force the elements. It would be beneficial to have custom implementation instead.

As far as this PR is concerned, there is no need to change anything. I'll turn this comment into a ticket instead that someone can work on and do proper testing and performance analysis.
```suggestion
scanl f z0 (StrictSeq xs) =
z0 <| StrictSeq $! (snd (mapAccumL (\ x z -> let !x' = f x z in (x', x')) z0 xs))
```

_Originally posted by @lehins in https://github.com/IntersectMBO/cardano-base/pull/592#discussion_r2641337016_

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.