Tying knots with strict constructors

David Feuer david at well-typed.com
Sun Aug 27 03:52:12 UTC 2017


Once in a while, one desires to tie a recursive knot and is stymied by a
strict data constructor. I recently encountered this problem trying to
improve the implementation of `never` in the `streaming` package.
The Stream type is defined thus:

data Stream f m r = Step !(f (Stream f m r))
                  | Effect (m (Stream f m r))
                  | Return r

It would be nice to be able to write

never :: Applicative f => Stream f m r
never = fix (Step . pure)

Unfortunately, if `pure` is strict (e.g., Identity), this won't work. The
Step wrapper attempts to force `pure never` and then apply the Step worker.
This will never work. The streaming package works around the problem
by representing the `never` stream in a different way, at the potential
cost of some efficiency. In other contexts, there may be no (safe) workaround
at all.

This is terribly frustrating, because it seems almost possible to express what
I want in Core, and even possible to express it in Haskell with a really awful
unsafeCoerce. The nasty version looks like this:

data StreamL f m r = StepL (f (StreamL f m r))
                   | EffectL (m (StreamL f m r))
                   | ReturnL r

never :: forall f m r. Applicative f => Stream f m r
never = case loop of
          StepL x -> x `pseq` unsafeCoerce loop
   where
     loop :: StreamL f m r
     loop = StepL (pure loop) in loop
     {-# NOINLINE loop #-}
{-# NOINLINE never #-}

That is, I make a copy of the Stream type, but with a lazy version of the Step constructor,
I tie my knot, I make very sure that the strict field is evaluated, and then I unsafeCoerce
the whole thing in a thoroughly unsupported fashion to get back to the right type. Ideally,
It would be nice to get GHC to manufacture, and expose to users, bidirectional patterns
that offer more access to the raw representation of a type.

Basically, I want to get a bidirectional pattern for Step that:

1. Is lazy when used as a constructor (applying the "worker" constructor directly)
2. Is viewed as lazy on matching, so the strictness analysis comes out right.

Using such a feature will presumably always be dangerous (unless someone
does a ton of work to find an efficient way to make it safe), but I'd rather have
a reasonable dangerous way to do it than an unreasonable dangerous way,
if that can be accomplished.

Unfortunately, I haven't been able to think of a reasonable design for such a
language feature. Does anyone else have any ideas? Or some other thought about
how such things might be done?

David


More information about the ghc-devs mailing list