Proposal: Strict types

[Edward Z. Yang]

Hello all,

This proposal would like to make it easier to build data types
for strict data structures.  Everything described here can be
done by making a new data declaration; we'd like to support
some more ad-hoc mechanisms.

This is not intended to be complete, rather it's intended to
jump start discussion about the selection and use of strict
and lazy data structures in Haskell.

1. Move strict Maybe and Either into base

We create a new module Data.Maybe.Strict and Data.Either.Strict
which implement the following semantics:

    Just _|_ = _|_
    Left _|_ = _|_
    Right _|_ = _|_

We do not expose a left-strict or right-strict version of Either.

2. Move strict Tuple into base

We create a new module Data.Tuple.Strict that defines a new data
type Pair with:

    Pair _|_ a = _|_
    Pair a _|_ = _|_

3. Syntax extension for strict pairs

We extend syntax to allow a way of specifying strict pairs (maybe
(! 1, 2, 3 !), with operator (!,) (!,,) etc).  These are distinct from
normal pairs and have their own set of functions.

4. Move strict IO into base

Unpredicatable resource usage behavior with hGetContents (which is lazy) and
similar functions frequently affects newbies.  Offer a module
System.IO.Strict.

We note that proposals 1, 2 and 4 are implemented by the strict package,
as is a form of 3 without nice syntax.

5. Move strict-concurrency into base

The package strict-concurrency offers strict versions of MVars and Chans,
which are frequent culprits for unpredicatable behavior in which thread
a thunk is evaluated on.

As an alternative to moving 1-5 into base, we can place them in the Haskell
Platform.

6. Syntax extension for anonymous strict types

If I have a type (a, b), and I would like to make it strict in
the first argument, I have to create a new data type.  This syntax
extension would permit me to create such data type simply by writing (!a, b).

This is probably going to be difficult, so here are some possible
implementation strategies:

    * Such syntax is simply sugar for creating an anonymous data type
      with those properties.  Coercions would need to be specified
      manually.  Type inference errors might become harder to diagnose.

    * We modify all types to have a strictness bit and modify the
      inference algorithm to propagate these bits.  It sounds like
      a fascinating research problem with a paper at the end, if it
      actually works.

If this is implemented, it supersedes all of the previous points
(and in fact, probably many of the .Strict modules that currently exist,
if application of strictness is strictly (ahem) mechanical.)

Discussion time: 1 month