CODEWITHSUNDEEP
haskellalgebraic-data-typespattern-synonyms
Zorf
Zorf

Reputation: 6464

Define Haskell type constructor equality?

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.

Upvotes: 3

Views: 443

Answers (3)

Cactus
Cactus

Reputation: 27626

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).

Upvotes: 0

Luis Casillas
Luis Casillas

Reputation: 30227

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.)

Upvotes: 6

user1131435
user1131435

Reputation:

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.

Upvotes: 8

Related Questions