Define Haskell type constructor equality?

3
votes

I'm not meaning as a member of Eq. My code:

data Race = Terran | Zerg | Protoss deriving (Eq, Show, Read);

data MU = MU Race Race deriving (Eq, Show);

In this case I define for instance (MU Terran Zerg). I want to create a data constructor TvZ which is essentially identical in all aspects for intance so I can match a function pattern:

foo TvZ = ...

instead of having to do

foo (MU Terran Zerg) = ...

Which you can't do if you assign it to a variable as in tvZ = (MU Terran Zerg)

Another thing I want to do is making short forms as in making the type constructor T and Terran identical.

Last thing, medivac speed boost needs a minor nerf I feel.

3
haskellalgebraic-data-typespattern-synonyms
Do you want to differentiate between TvZ and ZvT? Also, what do you gain from matching TvZ over (MU Terran Zerg)? - user1131435
So what exactly is your question? - jwodder
What you're asking for has been proposed a few times under the name "pattern synonyms", see here and here, but I haven't heard of any plans to implement it (yet). - hammar
What I gain from the short form is that it's shorter and cleaner, less room for typing errors. The very reason we tend to do pi = 3.14159265359 oce and then get it over with, short is good, leaves less room for typing errors. - Zorf
SHE offers a prototype implementation of pattern synonyms: they're so simple a mere preprocessor can handle it. It's your basic definitional abstraction, but for the pattern language as well as the expression language. All the usual motivations for definitional abstraction apply. View patterns are often mentioned as a candidate alternative in this context, a position which is its own punishment. - pigworker

3 Answers

8
votes

What you're asking for is called a "pattern synonym", and has been proposed multiple times. It is currently not implemented. You can view the proposals here, here, and a bunch of other places (links courtesy of hammar).

However, as a solution, this works just as well:

foo (MU Terran Zerg) = ...
foo (MU Zerg Terran) = foo $ MU Terran Zerg

and will effectively achieve the same thing, even if it doesn't look as nice.

6
votes

First try, use the following pattern (I'm assuming that MU Terran Terran and other self-relations are allowed.):

foo (MU Terran Terran)   = ...
foo (MU Terran Zerg)     = ...
foo (MU Terran Protoss)  = ...
foo (MU Zerg Zerg)       = ...
foo (MU Zerg Protoss)    = ...
foo (MU Protoss Protoss) = ...
foo (MU x y) = foo (MU y x)

You have to be very careful with functions defined like that, because if you don't get the cases to be exhaustive it's an infinite loop.

Second try: I had a shot at generalizing the pattern, and the best I came up with is this, which is barely any better:

forceSymmetric :: (MU -> Maybe r) -> MU -> r
forceSymmetric f = \p -> case f p of
                          Nothing -> fromJust (f (swap p))
                          Just r -> r

foo (MU Terran Terran)   = Just ...
foo (MU Terran Zerg)     = Just ...
foo (MU Terran Protoss)  = Just ...
foo (MU Zerg Zerg)       = Just ...
foo (MU Zerg Protoss)    = Just ...
foo (MU Protoss Protoss) = Just ...
foo (MU x y)             = Nothing

This has the virtue that you'd gen an error instead of an infinite loop if you mess up.

Third, deeper try: the heart of the problem is that you want symmetry. Let's forget that MU is a constructor, and just treat it as a function. You want it to obey this symmetry law:

MU a b == MU b a

By == I don't necessarily mean the Eq type class here, but rather mutual substitutibility; substituting one expression for the other should not affect the meaning of any program.

Well, algebraic data types don't have that property, period. For an algebraic data type constructor like MU, MU a b == MU c d if and only if a == b and c == d. So if you want to make it impossible for any function to distinguish between MU Terran Zerg and MU Zerg Terran, you need to make the MU type abstract, so that its users cannot see its internal representation.

The formula for number of combinations of n items taken r at a time, with duplicates allowed, is factorial (n + r - 1) / (factorial r * factorial (n - 1)); for n = 3 and r = 2, this is 6 combinations. So what we want is to define a type MU that has only six possible values, a function toMU :: Race -> Race -> MU such that mu a b == mu b a, and a function fromMU :: MU -> (Race, Race) such that uncurry toMU . fromMU == id. The easiest way I can think of doing this is to use sorted tuples:

data Race = Terran | Zerg | Protoss deriving (Eq, Show, Read, Ord);

data SortedPair a = SP a a  -- The constructor here needs to be private

makeSortedPair :: Ord a => a -> a -> SortedPair a
makeSortedPair a b | a < b     = SP a b
                   | otherwise = SP b a

breakSortedPair :: SortedPair a a -> (a, a)
breakSortedPair (SP a b) = (a, b)

type MU = SortedPair Race

toMU :: Race -> Race -> MU
toMU = makeSortedPair

fromMU :: MU -> (Race, Race)
fromMU = breakSortedPair

Now you're guaranteed that fromMU can produce (Terran, Zerg) but not (Zerg, Terran), so you can leave out the final "catch-all" cases from the first two proposals above. (The compiler doesn't know anything about this, however, so it will still complain about non-exhaustive patterns.)

0
votes

Starting with GHC 7.8, you can use pattern synonyms, a new language extension aimed, among others, exactly for this use case:

{-# LANGUAGE PatternSynonyms #-}

pattern TvZ :: MU
pattern TvZ = MU Terran Zerg

This will allow you to use TvZ both in pattern context (i.e. matching) and expression context (i.e. construction of a new MU value).