Expressing multi-parameter typeclasses in terms of single-parameter ones

Question

For a certain reason (weird Hugs installation on target computer) I want Haskell98 compliant code, which means no common language extensions. One annoyance in particular is the absence of multi-parameter typeclasses, for example in my case:

class Semiring d where
  zero :: d
  one :: d
  plus :: d -> d -> d
  times :: d -> d -> d

class Monoid e where
  mzero :: e
  mplus :: e -> e -> e

class (Semiring d, Monoid e) => Module d e where
  mtimes :: d -> e -> e

I get a feeling that this issue in particular can be stepped around somehow, maybe by defining a few helper typeclasses and "packaging" the information about the types somehow, but I cannot figure it out.

Is my intuition justified at all? I am reading that multiparam typeclasses were widely used even at the time of Haskell98 standard's writing, were there ways of working around this limitation back then?

Answer 1

Oleg Kiselyov wrote a demonstration of this in 2007, Haskell with only one typeclass:

[I]f we remove the type class declaration and the standard type classes, leaving the language with a single, fixed, pre-defined type class with a single method, no expressivity is lost. We can still write all Haskell98 type-class programming idioms including constructor classes, as well as multi-parameter type classes and even some functional dependencies.

Briefly, he introduces a two-parameter class C with a functional dependency and a single method:

class C l t | l -> t where ac :: l -> t

This relates a “label” l with its type t, for example:

data Add a

instance C (Add Int) (Int -> Int -> Int) where
  ac _ x y = x + y

(+) :: forall a. (C (Add a) (a -> a -> a)) => a -> a -> a
(+) = ac (undefined :: Add a)

This isn’t strictly H98 because it uses a scoped type variable, but I believe those were implemented in Hugs fairly early on.

Now, as a multi-parameter class is effectively a set of tuples of types, we can rephrase it as a single-parameter class whose elements are tuples, at the loss of the functional dependency.

class Overload a where overload :: a -> a

data Add a

instance Overload (Add Int, Int -> Int -> Int) where
  overload (label, _) = (label, \x y -> x + y)

apply :: (Overload (label, signature)) => label -> signature
apply label = f
  where
    (_, f) = overload (label, f)

(+) :: forall a. (Overload (Add a, a -> a -> a)) => a -> a -> a
(+) = apply (undefined :: Add a)

In modern Haskell, you may wish to use a proxy, but I’ve kept the use of undefined/bottom, both in the spirit of old-timey Haskell, and for the sake of similarity with the previous example.

Of course, the lack of a fundep now means that the compiler won’t be able to infer an unambiguous type in many cases, because it can’t determine that each label such as Add Int has only one corresponding signature Int -> Int -> Int. So this may require a type annotation. On the other hand, it grants you some flexibility, in that you can technically give multiple types to the same term if you want to construct things like subtypes or overlapping instances. And if all you want to avoid is multi-parameter classes, then you can avoid a lot of the ambiguity by not restricting yourself to just one class.

You can also encode functional dependencies manually using equality constraints, if they’re available:

-- |
-- Compare:
--
-- > class Widen a b | a -> b where widen :: a -> b
-- > instance Widen Bool Int where widen = fromEnum

instance (b ~ Int) => Overload (Widen Bool b, Bool -> Int) where
    overload (label, _) = (label, fromEnum)

Many more details and examples are in the article and accompanying code.

Answer 2

I'm not sure it can be done purely in H98. But here's a hack that gets partway there with a very easily-supported extension, FlexibleInstances, that may be available in Hugs (though perhaps not under that name).

{-# Language FlexibleInstances #-}
data ModuleDict d e = ModuleDict { mtimes :: d -> e -> e }
class Default a where def :: a
instance Default (ModuleDict Int Int) where def = ModuleDict (+)

example :: Int
example = mtimes (def :: ModuleDict Int Int) 3 4

-- more generalizably:
-- example :: Default (ModuleDict Int Int) => Int
-- this additionally requires FlexibleContexts, but that should be supported
-- everywhere that FlexibleInstances is, as they're kinda useless without
-- each other

Although it doesn't let you call mtimes directly, it's actually not that different from how the multi-parameter typeclass you proposed would have to be used. Namely, in many situations, the MPTC would require a type annotation on mtimes to fix which instance to use; think of the type annotation on def as essentially similar. Of course, one downside is that if the context does indeed fix the types, then with MPTC's you can drop the type annotation, but with this solution you need to keep the def around.

This also doesn't really let you express your constraints that only Semirings and Monoids can be related, so you'll be replicating those constraints in a lot of type signatures. You can avoid this somewhat by extending the dictionary:

data SemiringDict d = SemiringDict { zero, one :: d, plus, times :: d -> d -> d }
data ModuleDict d e = ModuleDict { semiringDict :: SemiringDict d, mtimes :: d -> e -> e }

Your type signatures could then be shorter, but usage of the "class methods" would be significantly more verbose.

Answer 3

(weird Hugs installation on target computer) I want Haskell98 compliant code,

Hugs has HugsMode: menu File -> Options -> Allow Hugs/Ghc extensions [radio button]

Or as it says here, -98 option at the command line. (Confusingly, +98 means H98 mode; so -98 means not H98 mode -- that is Hugs mode.) And from that doco page, follow the link to Section 7 for the full run-down.

I can think of no reason your installation is so weird you can't run Hugs mode.

I did once get a version of Hugs for a very old model of iPad. It forgot to switch on HugsMode for its build. (The iPad has since died; that Hugs ap has also died.)

And to everybody else here who's being rude to Hugs: Hugs(Mode) is a long way in advance of H2010 (except not supporting pattern guards). And has a half-decent records system -- unlike GHC. So I use Hugs more than GHC for serious work. With a little bit of tweaking, you can even persuade Hugs to a records algebra.