ekmett / ekmett/distributive

Excessive Laziness

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.