[Haskell-cafe] Small question

[Josef Svenningsson]

On 8/10/07, John Meacham <john at repetae.net> wrote:
> On Thu, Aug 09, 2007 at 06:37:32PM +0100, Andrew Coppin wrote:
> > Which of these is likely to go faster?
> >  type Quad = (Bool,Bool)
> ...
> >  data Quad = BL | BR | TL | TR
> ...
> > I'm hoping that the latter one will more more strict / use less space.
> > But I don't truely know...
>
> The second one will be signifigantly better for a couple reasons. A
> simple counting of values that they can take on will show not only this
> but that they are not isomorphic even,
>
> (Bool,Bool) can be one of
>
> _|_
> (True,True)
> (True,False)
> (False,True)
> (False,False)
> (_|_,True)
> (_|_,False)
> (_|_,_|_)
> (True,_|_)
> (False,_|_)
>
> that is a total of 10 different cases, each time a bottom might appear,
> a thunk evaluation (or indirection) is involved.
>
>
> now, take the second case
>
> data Quad = BL | BR | TL | TR
>
> the possible values are
>
> _|_
> BL
> BR
> TL
> TR
>
> a whole half of the other representation.
>
>
Well, there are ways to improve the situation. If you want to remove
all the bottoms in your type you can define Quad as:

type Quad = Data.Strict.Tuple.Pair Bool Bool

I'm not sure how much speed this will gain in practice and whether it
will beat the four constructor data type though. If anyone does some
measurements it'd be interesting to know.

Cheers,

Josef

PS. Data.Strict.Tuple lives in the strict package which can be found here:
http://www.cse.unsw.edu.au/~rl/code/strict.html