One more post before the end of the year:

Haskell users tend to be mathematically inclined, so it's no surprise that they should notice a mathematical application of typeclasses: they can represent abstract algebraic structures. You only get one model of the ~~algebra~~ structure per type (potentially annoying for common ~~algebras~~ structures like groups), but where applicable this makes a great (for some values of "great") way to show off your mathematical prowess. Indeed, some of the standard typeclasses are intended as ~~abstract algebras~~ algebraic structures: `Monad`

and `MonadPlus`

, at least.

There are probably quite a few Haskellers who have not only noticed this, but wished it were taken further. For instance, why isn't `/`

defined like this?

`(/) :: (Field a) => a -> a -> a`

(Really mathematical Haskellers may also wish the return type was `Maybe a`

.)

Isn't `Num`

actually `Ring`

, and `Fractional`

`Field`

?

Not quite. `Integer`

is indeed a ring, but `Int`

isn't because of overflow. `Ratio`

is a field, but `Float`

isn't, because of rounding. ~~Abstract algebras~~ Algebraic structures are useful only because it's possible to reason from their axioms and apply the conclusions to the models, and that doesn't work when the models don't actually satisfy those axioms. The reason `Monad`

works is that its standard instances *do* correctly model it. The others are stuck with names less proudly abstract but less misleading (not to mention less opaque to non-mathematicians).

Of course, none of these models are really correct, because they all have the limitation of finite memory. But that's a less intrusive limitation than fixed-precision numbers. "Less intrusive" is a disappointingly vague description; I suspect the real difference is that finite memory afflicts virtually every operation in the language, while overflow and rounding are specific to certain types. So while assuming the monad laws work on lists, for example, will cause problems in some circumstances, it won't cause any *more* problems, because your programs would fail anyway in those cases. In contrast, it's pretty easy to write code that will work for any ring, but not for `Int`

.

The difference is that there could, theoretically, be an implementation of the language with infinite memory.

ReplyDeleteInt is a ring, even with overflow. Google “quotient ring”.

ReplyDelete