9
$\begingroup$

Haskell and some other functional languages have Monad and Monoid types (and Semigroup, Functor, Applicative, and many others), and lists, trees, Maybe, and other types subtype all or some of these. You can write other functions that work with any Monad or Monoid type:

f :: (Monad m) => m Int -> m String
f x = x >>= \y -> return (show y)

For example, f here could be given a list of ints, a tree of ints, or a Maybe of int, and would give back a list/tree/Maybe of strings. That's a trivial case, but it works for bigger/more complex processing functions as well. This is really convenient for defining very general transformations!

I've seen that in Java you can define a common Monoid supertype with the weird-looking incantation interface Monoid<T extends Monoid<T>> { T combine(T o); } and then define methods that work with any Monoid, but that it isn't possible to do the same for Monad or Functor. Why is that? Why can you do it for one of them, and not both or neither?

Is it something about the type system, something to do with object orientation generally, or another design choice of the language? What would a Java-like language need to have in it to let all of those types work?

$\endgroup$
3
  • $\begingroup$ Note that the same is true in Swift, despite that having "protocols" (traits) and structs rather than being OO. (You can do OO in Swift but only for Objective-C interop; it's not idiomatic.) $\endgroup$
    – Bbrk24
    Aug 22, 2023 at 23:58
  • $\begingroup$ This is a duplicate of stackoverflow.com/questions/35951818/… $\endgroup$ Sep 6, 2023 at 21:26
  • $\begingroup$ Very technically, we can't define a type(class) of monoids in Java or Haskell because there's no support for algebraic laws; we can define a type(class) of unital magmas, binary operations with units, but we can't restrict implementations to those which fulfill the monoid laws. $\endgroup$
    – Corbin
    Nov 21, 2023 at 16:24

1 Answer 1

13
$\begingroup$

You need higher-kinded types. A way to introduce a generic parameter, which is itself generic.

Translating your Haskell example to Java-ish syntax, it might look something like this:

public M<String> f<M extends Monad<M>>(M<int> x) {
  x.bind( (y) -> M.return(y.toString()) )
}

Note how the M parameter has its own type parameter, so that I can write M<int> and M<String>.

$\endgroup$
6
  • 1
    $\begingroup$ I am not sure you always need HKT itself. Rust has GAT instead (Generic Associated Type) and there are Rust implementations of Monads -- though not as nifty as Haskell's, possibly. $\endgroup$ Aug 23, 2023 at 12:08
  • 2
    $\begingroup$ The M extends Monad<M> trick is sometimes known as the curiously recurring template pattern, and as the Wikipedia article notes, it’s a form of $F$-bounded quantification. It might be nice to at least mention these things in your answer. $\endgroup$
    – Alexis King
    Aug 23, 2023 at 14:52
  • 1
    $\begingroup$ That's not what the question was about, why would I overcomplicate the answer by mentioning it? That would only make it more confusing and less accessible. $\endgroup$ Aug 23, 2023 at 16:42
  • $\begingroup$ I had to google F-bounded quanification there $\endgroup$ Aug 24, 2023 at 0:01
  • 2
    $\begingroup$ Rust's GATs are HKTs, in a limited, verbose form. Depending on which Rust designers are writing about them, GATs may be characterized as an incremental step on Rust's path towards full HKTs or as a compromise meant to prevent Rust from getting full HKTs and becoming one of those languages. $\endgroup$
    – user570286
    Aug 26, 2023 at 2:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .