Unpacking multi-type constructors

Simon Peyton-Jones simonpj at microsoft.com
Tue Jul 21 04:11:27 EDT 2009

Nice idea, but I'm not yet convinced that it would work well in practice.

First, there's an exponential explosion in the number of constructors required.  Anything with an exponential is worrying.

Second, you presumably do not want massive code duplication.  So I assume that if you start with

case x of { Node i n2 n2) -> e

then you'll desugar to something like this:

                let fj i n1 n2 = e
                case x of
                                Node1 I -> fj i Nothing Nothing
                                Node2 I n1 -> fj I (Just n1) Nothing
                                ... etc for other cases...

This doesn't look like a win, because you end up allocating the (Just n1) things anyway!

So maybe you want to *duplicate* e, so you generate
                case x of
                                Node1 I -> e[Nothing/n1, Nothing/n2]
                                Node2 I n1 -> e[Just n1/n1, Nothing/n2]
                                ... etc for other cases...

But now you not only have an exponential number of branches: in each of those branches you duplicate an arbitrarily large expression e. That doesn't look attractive to me.


From: glasgow-haskell-users-bounces at haskell.org [mailto:glasgow-haskell-users-bounces at haskell.org] On Behalf Of Louis Wasserman
Sent: 21 July 2009 00:20
To: glasgow-haskell-users at haskell.org
Subject: Unpacking multi-type constructors

I think this is a feasible idea.  Whether this is in fact a good idea is an entirely separate question, however, and I want feedback.

Currently, I believe that an UNPACK pragma used on a multi-constructor type has no effect.  For example,

data Node = Node Int {-# UNPACK #-} !(Maybe Node) {-# UNPACK #-} !(Maybe Node)

is the same as

data Node = Node Int !(Maybe Node) !(Maybe Node)

What I'd like is for this to translate into four constructors, one for each combination of constructors for the UNPACK'd fields:

data Node = Node0 Int -- Nothing, Nothing
| Node1 Int Node -- Just, Nothing
| Node2 Int Node -- Nothing, Just
| Node3 Int Node Node -- Just, Just
The primary counterargument I can think of is that this can result in a single-constructor type being turned into a multi-constructor type, which runs the risk of interfering with GHC's sexcellent handling of single-constructor types.

The countercounterargument is, of course, that the {-# UNPACK #-} pragma already behaves differently depending on the single-constructorness of the underlying type, and that the obligation is already on the programmer to check such things.

For reference, could somebody point me to the place in GHC that currently takes care of {-# UNPACK #-} pragmas, so I could -- for instance -- figure out whether or not there's another reason that this idea isn't in place already?

Louis Wasserman
wasserman.louis at gmail.com<mailto:wasserman.louis at gmail.com>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/glasgow-haskell-users/attachments/20090721/a982b68e/attachment-0001.html

More information about the Glasgow-haskell-users mailing list