Excessive Laziness
- Dominant language
- Haskell
- Stars
- 42
- Forks
- 26
- PR merge metrics
- No merged PRs in 30d
Description
Currently, `scatter` is in some cases excessively lazy in a way which can cause space leaks. For example, a typical definition of `liftA2` for infinite streams would be
```haskell
data Stream a = Cons { shead :: a, stail :: Stream a }
liftA2 :: (a -> b -> c) -> Stream a -> Stream b -> Stream c
liftA2 f = go
where
go (Cons a as) (Cons b bs) = Cons (f a b) (go as bs)
```
but `liftR2`, implemented in terms of `scatter`, currently instead gives the equivalent of
```haskell
liftR2 f = go
where
go as bs =
Cons
(f (shead as) (shead bs))
(go (stail as) (stail bs))
```
(i.e. the previous definition but with lazy patterns).
With the first definition, forcing the spine of the result forces the traversal of `as` and `bs`, whereas with the second it instead builds thunks which essentially duplicate the input streams, and the traversal is only forced when the elements of the output stream are forced. The latter isn't what one would ordinarily want or expect, and can cause space leaks.
To fix this, implementations of `scatter` need to be able to strictly `ffmap` `w`. This could be achieved either by adding an operation on `w` (either as a parameter to `scatter`, or via a type class), or by using strict `FFunctor`s with explicit laziness, including replacing `Identity` with `Solo`. E.g. the latter would look something like
```haskell
class Functor f => Representable f where
scatter :: FFunctor w => (w Solo -> a) -> (g ~> f) -> w g -> f a
distrib :: (Representable f, FFunctor w) => w f -> (w Solo -> a) -> f a
distrib wf k = scatter k id wf
-- strict FFunctor
data F2 a b f = F2 !(f a) !(f b)
instance FFunctor (F2 a b) where
ffmap f (F2 x y) = F2 (f x) (f y)
liftR2 :: Representable f => (a -> b -> c) -> f a -> f b -> f c
liftR2 f as bs = distrib (F2 as bs) \(F2 (Solo a) (Solo b)) -> f a b
instance Representable Stream where
scatter f phi wg = go (ffmap phi wg)
where
go w =
-- strictly split w
let !heads = ffmap (\(Cons x xs) -> Solo x) w
!tails = ffmap (\(Cons x xs) -> Compose $ Solo xs) w
in Cons (f heads) (go $ ffmap (getSolo . getCompose) tails)
```
and results in `liftR2` for `Stream` optimizing to the same code as the typical definition of `liftA2`.
Contributor guide
No contributing guide indexed for this repository
Research direction
Start by locating the definitions of scatter, liftR2, and the Stream Representable instance in the repository. Read how FFunctor, Identity, and related representations are currently implemented, then check whether existing tests cover laziness or space usage. Done means preventing scatter from unnecessarily retaining input streams while preserving the intended Stream behavior.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- haskell
- Domain
- performance
- Issue type
- Bug
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 30/100