3 ms·

Non-recursive higher-kinded types can be implemented in terms of functors. For example, the free monad type constructor is very easy to implement in Standard ML

Non-recursive higher-kinded types can be implemented in terms of functors. For example, the free monad type constructor is very easy to implement in Standard ML (OCaml is similar): signature FUNCTOR = sig type 'a t val map : ('a -> 'b) -> 'a t -> 'b t end functor FreeMonad (F : FUNCTOR) = struct datatype 'a t = Pure of 'a | Free of 'a t F.t (* operations go here *) end Modules can do everything type classes can do, and more. There is no weakness. The real reason why you need to define this as a higher-kinded type constructor in Haskell (`data Free f a = ...`) is to overcome the limitation of not having parameterized modules. The way it's done in Haskell also has the defect that the type system will happily allow you to construct a value of type `Free Foo a`, where `Foo` is not a functor, whereas the ML version prohibits this by construction.

Ericson2314 11y ago
That's not the same however, because the modules language is a lot more constrained than the term language. See the first paragraph the second page of https://www.mpi-sws.org/~rossberg/1ml/1ml-extended.pdf https://www.mpi-sws.org/~rossberg/1ml/1ml-extended.pdf.
- catnaroek 11y ago
  > That's not the same however, because the modules language is a lot more constrained than the term language. You don't need to tell me. That's obvious to anyone who has programmed in ML. But Haskell's type class language is similarly a lot more constrained than its term language. It's basically a pure (in particular, cut-free) compile-time Prolog, with some restrictions to guarantee that no query will return more than one result. > See the first paragraph the second page of https://www.mpi-sws.org/~rossberg/1ml/1ml-extended.pdf https://www.mpi-sws.org/~rossberg/1ml/1ml-extended.pdf. Rest assured, I've read the paper - not today, but several months ago. I'm quite familiar with the ML module literature. Check my post history: https://news.ycombinator.com/item?id=10856201 https://news.ycombinator.com/item?id=10856201 https://news.ycombinator.com/item?id=11131265 https://news.ycombinator.com/item?id=11131265 But, since you're arguing that the combination of type classes and higher-kinded types can do something that ML modules can't, I'm providing evidence for the opposite: everything that can be done with type classes and higher-kinded types can be done with modules. (0) You can't compute new modules at runtime, but you also can't define new type class instances at runtime. (1) An ML module can have both transparent and abstract type components, controlled by the programmer. A type class always has abstract type components at definition time, and transparent type components at instantiation time. Modules are more expressive than type classes. (2) The signature of an ML module is structural, and you can, after the fact, selectively forget part of a module's contents. Type classes don't let you do this. Try making `Monoid` a subclass of `Semigroup` without recompiling any existing code. Again, modules are more expressive than type classes. As for higher kinds, at least with OCaml's higher-order applicative functors, you can encode arbitrary higher-kinded type constructors. And most of the higher-kinded constructors that actually arise in practice can be encoded even with Standard ML's first-order functors.
  - Ericson2314 11y ago
    > Rest assured, I've read the paper Don't worry, I quote the paper not because I doubt your ML experience, but to make sure that I don't mess up the peculiars of the situation. I've spent more time thinking about the design of SML/OCaml than using them, and wouldn't want to undermine my argument with a mis-remembered surface syntax. My point with this arguments is not that "polymorphic instances" are as powerful as functors (they aren't!). Rather in this (and similar examples) it's higher-kinded types vs modules, no type classes involved. The Haskell equivalent is just a plane function, not a polymorphic instance, and there is things that can be done in the term language but not the module language. SML/OCaml with higher-kinded types would annihilate this argument, no type classes or implicits needed, but don't yet exist.
    - catnaroek 11y ago
      > My point with this arguments is not that "polymorphic instances" are as powerful as functors (they aren't!). Rather in this (and similar examples) it's higher-kinded types vs modules, no type classes involved. This paper disagrees: http://www.cse.unsw.edu.au/~chak/papers/modules-classes.pdf http://www.cse.unsw.edu.au/~chak/papers/modules-classes.pdf . See below. > The Haskell equivalent is just a plane[sic] function, not a polymorphic instance, and there is things that can be done in the term language but not the module language. A plain function can't return fresh new types. A functor can. > SML/OCaml with higher-kinded types would annihilate this argument As I said above, OCaml's higher-order modules let you encode arbitrarily higher-kinded types. Even if OCaml didn't have parametric polymorphism in the core language, you can express it in the module language with applicative functors (although the result would be a lot more verbose). If you don't believe me, give me an arbitrary higher-kinded type, and I'll tell you how to encode it in OCaml.
      - Ericson2314 11y ago
        I don't have time to read the paper for a few days, but I meant while functors can do things functions cannot do, functions can do things functors cannot do too.

Ericson2314 11y ago

That's not the same however, because the modules language is a lot more constrained than the term language. See the first paragraph the second page of https://www.mpi-sws.org/~rossberg/1ml/1ml-extended.pdf https://www.mpi-sws.org/~rossberg/1ml/1ml-extended.pdf.

catnaroek 11y ago
> That's not the same however, because the modules language is a lot more constrained than the term language. You don't need to tell me. That's obvious to anyone who has programmed in ML. But Haskell's type class language is similarly a lot more constrained than its term language. It's basically a pure (in particular, cut-free) compile-time Prolog, with some restrictions to guarantee that no query will return more than one result. > See the first paragraph the second page of https://www.mpi-sws.org/~rossberg/1ml/1ml-extended.pdf https://www.mpi-sws.org/~rossberg/1ml/1ml-extended.pdf. Rest assured, I've read the paper - not today, but several months ago. I'm quite familiar with the ML module literature. Check my post history: https://news.ycombinator.com/item?id=10856201 https://news.ycombinator.com/item?id=10856201 https://news.ycombinator.com/item?id=11131265 https://news.ycombinator.com/item?id=11131265 But, since you're arguing that the combination of type classes and higher-kinded types can do something that ML modules can't, I'm providing evidence for the opposite: everything that can be done with type classes and higher-kinded types can be done with modules. (0) You can't compute new modules at runtime, but you also can't define new type class instances at runtime. (1) An ML module can have both transparent and abstract type components, controlled by the programmer. A type class always has abstract type components at definition time, and transparent type components at instantiation time. Modules are more expressive than type classes. (2) The signature of an ML module is structural, and you can, after the fact, selectively forget part of a module's contents. Type classes don't let you do this. Try making `Monoid` a subclass of `Semigroup` without recompiling any existing code. Again, modules are more expressive than type classes. As for higher kinds, at least with OCaml's higher-order applicative functors, you can encode arbitrary higher-kinded type constructors. And most of the higher-kinded constructors that actually arise in practice can be encoded even with Standard ML's first-order functors.
- Ericson2314 11y ago
  > Rest assured, I've read the paper Don't worry, I quote the paper not because I doubt your ML experience, but to make sure that I don't mess up the peculiars of the situation. I've spent more time thinking about the design of SML/OCaml than using them, and wouldn't want to undermine my argument with a mis-remembered surface syntax. My point with this arguments is not that "polymorphic instances" are as powerful as functors (they aren't!). Rather in this (and similar examples) it's higher-kinded types vs modules, no type classes involved. The Haskell equivalent is just a plane function, not a polymorphic instance, and there is things that can be done in the term language but not the module language. SML/OCaml with higher-kinded types would annihilate this argument, no type classes or implicits needed, but don't yet exist.
  - catnaroek 11y ago
    > My point with this arguments is not that "polymorphic instances" are as powerful as functors (they aren't!). Rather in this (and similar examples) it's higher-kinded types vs modules, no type classes involved. This paper disagrees: http://www.cse.unsw.edu.au/~chak/papers/modules-classes.pdf http://www.cse.unsw.edu.au/~chak/papers/modules-classes.pdf . See below. > The Haskell equivalent is just a plane[sic] function, not a polymorphic instance, and there is things that can be done in the term language but not the module language. A plain function can't return fresh new types. A functor can. > SML/OCaml with higher-kinded types would annihilate this argument As I said above, OCaml's higher-order modules let you encode arbitrarily higher-kinded types. Even if OCaml didn't have parametric polymorphism in the core language, you can express it in the module language with applicative functors (although the result would be a lot more verbose). If you don't believe me, give me an arbitrary higher-kinded type, and I'll tell you how to encode it in OCaml.
    - Ericson2314 11y ago
      I don't have time to read the paper for a few days, but I meant while functors can do things functions cannot do, functions can do things functors cannot do too.