Hacker News new | comments | show | ask | jobs | submit login
Haskell Typeclasses vs. C++ Classes (michaelburge.us)
155 points by MichaelBurge 8 months ago | hide | past | web | favorite | 79 comments



Very detailed and informative!

For onlookers, I'd note that Haskell typeclasses are something of a trap for beginners who think they are the way to accomplish object-like coding in Haskell.

Actually, records with functions (closures) inside is usually a better choice: simpler, more flexible, more straightforward.

Of course the resemblance between a vtable and a record of functions is very obvious!


Yup, generally in terms of program structure, when I would make a class in C++/C#/Java, I make a module in Haskell. There’s usually a primary type and some helper types exported, along with functions that form the public interface.

If you need polymorphism you can mostly just reach for parametric polymorphism (generics) and closures. Existential types, in the form of closures, explicit existentially quantified types, or rank-2 universally quantified functions, give you basically the same expressive power as virtual functions—they’re all encodings of the same concept.

Typeclasses are more about the principle of “code to the interface, not the implementation”. For example, using a container through its Functor/Applicative/Monad/Monoid/Traversable/Foldable instances lets you be agnostic to its representation, swap it out for testing/performance, &c.


> when I would make a class in C++/C#/Java, I make a module in Haskell.

This. Group you code logically, expose only what's needed. This also gives the FPer a large part of the "encapsulation" and "group by responsibility" advantages that are often mentioned as pros of OO. Without going down the "implicit state sharing" path.


Encapsulation works even better with modules than with objects:

(0) Modules may expose n-ary operations on abstract types for n > 1.

(1) Modules may have multiple interrelated abstract type components, i.e., what Stepanov calls “multisorted algebras”.

Furthermore, if you are willing to use an impure language (like ML or Scala), modules can be just as stateful as objects if you deem it necessary.


Records with adhoc v-tables was how we did it in C. It was incredibly useful given an existing object schema to model.


> they are the way to accomplish object-like coding in Haskell. > Actually, records with functions (closures) inside is usually a better choice:

The better choice would be to use Haskell as it was intended to be used.


And that doesn't include first class functions inside of data structures? :)


I was just responding to "object-like coding," which i took to mean "using the OO paradigm in haskell." sorry if that's not what you meant.


I assume “object-like coding” just means “a data structure and a set of functions for interacting with it. Are you implying that the “right way” of using Haskell doesn’t do anything like that?


The closest thing to Typeclasses in C++ are concepts, i.e. the set of semantic and syntactic requirements on template parameters.

As of C++17, concepts are not yet an actual language construct but are enforced by convention and normally only checked at template instantiation time (as opposed to definition time), although there are techniques that can be used to simulate more formal checking (archetypes, enableif, etc.).


They've been voted into C++20! The wait may finally be over (in a few more years) :-)


That's excellent, I missed the news.

Unfortunately concepts lite are not capable of type checking declarations, but it is still an improvement.


It may even be fair to say that Haskell's typeclasses make it more like an object-oriented programming language. They have things like properties and multiple inheritance. Even Wadler has a section leading with "Object-oriented programming." in his paper on parametric polymorphism:

https://people.csail.mit.edu/dnj/teaching/6898/papers/wadler... (page 3)


Polymorphism — If you understand by OOP the single-dispatching made at runtime, then type classes are different because type classes are solved at compile time, the "vtable" (the dictionary of functions) being passed around isn't virtual and is provided per type, not per instance.

Encapsulation — If you understand by OOP the encapsulation of data, then no, type classes have no such thing.

Inheritance — type classes don't have inheritance. What they have are constraints (e.g. you can implement typeclass X for type T if a typeclass implementation Y also exists for T). So you can say for example that MonadError can be implemented only for types already implementing Monad. That's not inheritance, but composition.

Most importantly perhaps and something that doesn't clearly follow from the above is that OOP as implemented in popular languages, including C++, gives you subtyping, whereas type classes do not.

This has important ramifications. For example downcasting isn't possible. And you no longer have the "liskov substitution principle". And subtyping is actually incompatible with Hindley-Milner type inference.

Also in actual usage the differences can be quite big — for example, if you view type classes as "restrictions" on what a type can do (like OOP interfaces are), you no longer need to add these restrictions on the types themselves, but on the operations, where you actually need them, while the data structure definition can remain free of such restrictions.

This is called "constrained parametric polymorphism" btw. Which can't be achieved in most OOP languages that I know of, except for Scala and that's because Scala has "implicit parameters" which are equivalent to Haskell's type classes.

At the end of the day, what a type class gives you is a way to transform a type name into a meaningful value. Imagine having a function like ...

     f: T => A
But the T param is a type name. That's what type classes give you, whereas OOP does not.


> Which can't be achieved in most OOP languages that I know of, except for Scala and that's because Scala has "implicit parameters" which are equivalent to Haskell's type classes.

C++ can do that with template specialization.


I didn't know that, but it doesn't surprise me, seems to me like C++ templates are like their own language grown within C++ and can do lots of crazy things.


It is fairly straightforward, created a pastebin showing how it can be done, you can also make it check that it is implemented at compile time but the logic around that is a bit iffy:

https://pastebin.com/DiFh4GuM


> type classes are different because type classes are solved at compile time

    data Nested a = Nest a (Nested [a]) | Done deriving Show

    build :: Int -> a -> Nested a
    build 0 a = Done
    build i a = Nest a $ build (i- 1) [a]

    main = do
        i <- readLn
        print (build i i)



if you build a value of Nested at runtime then it is impossible to do static dispatch and the dictionary has to be constructed at runtime as well.

Sorry that I mistyped the example at first. If you run this version:

    > main
    23
    Nest 23 (Nest [23] (Nest [[23]] (Nest [[[23]]] (Nest [[[[23]]]] (Nest [[[[[23]]]]] (Nest [[[[[[23]]]]]] (Nest [[[[[[[23]]]]]]] (Nest [[[[[[[[23]]]]]]]] (Nest [[[[[[[[[23]]]]]]]]] (Nest [[[[[[[[[[23]]]]]]]]]] (Nest [[[[[[[[[[[23]]]]]]]]]]] (Nest [[[[[[[[[[[[23]]]]]]]]]]]] (Nest [[[[[[[[[[[[[23]]]]]]]]]]]]] (Nest [[[[[[[[[[[[[[23]]]]]]]]]]]]]] (Nest [[[[[[[[[[[[[[[23]]]]]]]]]]]]]]] (Nest [[[[[[[[[[[[[[[[23]]]]]]]]]]]]]]]] (Nest [[[[[[[[[[[[[[[[[23]]]]]]]]]]]]]]]]] (Nest [[[[[[[[[[[[[[[[[[23]]]]]]]]]]]]]]]]]] (Nest [[[[[[[[[[[[[[[[[[[23]]]]]]]]]]]]]]]]]]] (Nest [[[[[[[[[[[[[[[[[[[[23]]]]]]]]]]]]]]]]]]]] (Nest [[[[[[[[[[[[[[[[[[[[[23]]]]]]]]]]]]]]]]]]]]] (Nest [[[[[[[[[[[[[[[[[[[[[[23]]]]]]]]]]]]]]]]]]]]]] Done))))))))))))))))))))))

The innermost Nested has type `Nest [[[[[[[[[[[[[[[[[[[[[[Int]]]]]]]]]]]]]]]]]]]]]]` which wasn't known at compile time so the show instance has to be constructed at runtime. This is called polymorphic recursion.


Technically, one might argue that i doesn't store a vtable, but only a reference to a type, which stores a vtable determined at runtime.

I'd say the difference is minor to non-existent.


"i" does not store a reference to a type. Values in Haskell aren't tagged with their type like in OOP.

There is no "isInstanceOf" check in Haskell.


This is a single Show instance that pattern matches to decide on whether to recurse, same as how lists are shown.


Yeah, sorry, forgot the type variable at first.


All you need is a GADT which carries around the type class constraint.

    data Object cls a where
      Object :: cls a => a -> Object cls a
Now, the class `cls a` is carried around with the value `a`. You can even go one step further and reify the vtable by itself.

    data Dict c where
      Dict :: c => Dict
which you can't really do in standard C++.


> This is called "constrained parametric polymorphism"

The more common terminology is ad-hoc polymorphism AFAIK.


ad-hoc polymorphism is more general. Constrained/Bounded parametric polymorphism is a controlled subset of violations of parametric polymorphism.


eh, that might be a bit of a stretch. I like my peanut-butter and jelly separate, thank you.


>the "vtable" (the dictionary of functions) being passed around isn't virtual and is provided per type, not per instance.

This might be nitpicking but vtables in C++ are created per type with instances having a pointer to it.


it is not nitpicking, you are correct to point it out. The only difference is where the vtable is attached to: pointers in Haskell, objects instances in c++.

Although the language does not offer a builtin syntax for it, in C++ is also common to attach the 'vtable' to the 'handle' (a smart pointer or deep copying envelope), in the case of type erased wrappers (std::function, std::any, etc).


> It may even be fair to say that Haskell's typeclasses make it more like an object-oriented programming language.

The trick here is defining "object-oriented". In modern object-oriented languages, I usually assume that involves encapsulation of state inside of boxes called objects. In that sense, type classes are quite different.

Methods on objects generally mutate or provide views into the contents of the box, while methods in type classes are just regular functions. Critically, there is no inner mutation or privileged view into data via type classes.

> They have things like properties and multiple inheritance

How do they have properties? Also, they don't have multiple inheritance - a type can only ever have one instance of any given typeclass.

> Even Wadler has a section leading with "Object-oriented programming."

I read Wadler's paragraph on object-oriented programming (bottom of page 3) more as a highlight of the fundamental _difference_ between type classes and object-oriented classes. The only similarity between typeclasses and classes are that they are the mechanisms by which runtime dispatch is achieved.


Rust's traits are basically typeclasses, and so people coming from an OOP background have often struggled to model stuff in a Rust-y way. The 17th chapter of The Rust Programming Language [1] tries to get into the differences, and explain this kind of stuff. It's really hard though, since what OOP means depends on who you ask.

I enjoyed this post since it's kind of a mirror of this chapter, which was one of the hardest for us to figure out what to put in it.

1: https://doc.rust-lang.org/book/second-edition/ch17-00-oop.ht...


OOP has nothing to do with classes, inheritance, especially multiple inheritance. It's about programming objects that communicate with each other. In fact Javascript and it's prototype system are much more OOP than say C++ classes, or worse, Java classes.

We should call programming with classes and inheritance. COP, as in Class Oriented Programming. COP is especially appropriate because if you don't follow the type rules, you go to compiler jail.


> OOP has nothing to do with classes, inheritance, especially multiple inheritance. It's about programming objects that communicate with each other.

That is the Alan Kay definition. I'm not sure I'd claim that is the colloquial, universal understanding of OOP apart from the HN crowd, though. (ask a LOB programmer what OOP is and observe what they say).

I rather like the Alan Kay definition myself, but that is rather like having a Many Worlds understanding of quantum mechanics; Entirely consistent and arguably "correct", but not universally shared among practitioners.

We should refine our language (e.g. COP), but it would be revisionist to ignore what the 90's and 00's understanding of the definition would be.

I think it would be even more of a stretch to say that prototypal languages (javascript) are more OOP than non-prototypal languages, unless of course one is being a bit reductionist.


> In fact Javascript and it's prototype system are much more OOP than say C++ classes, or worse, Java classes.

I'm not sure what your ordering relation is here, but if it has something to do with how "purely object-oriented" a language is, then, sure, JavaScript is more OOP than C++ and Java since classes are not first-class in the latter.

But Smalltalk, which is class-based, is even more OOP than JavaScript since in Smalltalk, constructor calls are simply regular method calls (unlike JS which has a special "new" keyword) and there are no primitive objects (unlike JS, which distinguishes between primitive types and their boxed forms, though it tries to obscure that fact).

> COP is especially appropriate because if you don't follow the type rules, you go to compiler jail.

Smalltalk, Ruby, and Python are all class-based OOP languages but do not have static type systems with lots of compiler errors.


> It's about programming objects that communicate with each other.

This becomes even more apparent when using an actor-model language like Erlang. The types of "design patterns" you use focus much more around the communication and coordination you might find in real, physical systems. Consequently I find it easier to model "real" systems using actors than standard objects in a language like Java.

I also appreciate how the Pony language decomposes the notion of "objects" into actors that have their own process and capabilities (standard objects). It shows that their is a distinct role for both types of objects, and it helps when decomposing entities in a system.


That entirely depends on who you ask.

If classes and inheritance aren't a form of OOP, then what are they?

Also, Smalltalk had classes and inheritance, whatever Alan Kay had to say on the matter.


Object is a sufficiently generic term, so that it can mean very different things to different people. Lumping state with some functions that implicitly have R/W access to that state is not possible in Haskell, not even with the powerful type-classes. Thankfully.

Type-classes do allow interesting polymorphism tricks, that —as Wadler mentioned— allows Haskellers to use some of good parts of OO.


You're right; I still struggle to come up with a good catch-all definition for "object." On an unrelated note, I'm also still trying to figure out what DevOps is, aside from YAML and tears.


DevOps provisioning by software (hence the "dev") instead of by hand (manual-Ops).

It is with cloud-native that it gets interesting. Cloud-native infrastructure (like k8s) usually replaces the traditional devops tools (like Puppet, Ansible and Salt). Also it brings the notion of "scrappable instances", "blue green deployments" and "stateless compute nodes". This is were it got really interesting, this is were the FP intuitions start carry over. :)


Interesting last point! It does seem to be the trend, notably with large data sets:

https://wycd.net/posts/2017-04-09-rpcs-for-moving-computatio...


Lumping state with some functions that implicitly have R/W access to that state is not possible in Haskell

s/not possible/possible, but highly discouraged/


I kinda wish the Haskell designers hadn't gone with the term "typeclass", as it's incredibly misleading.

Typeclasses have a lot more cognitive similarity to Go-style interfaces or Smalltalk protocols than they do to OOP-style classes, and that fact can be enormously confusing to newcomers (which, at times, seems to be the Haskell raison d'etre).


Well this stuff happened in '88: http://homepages.inf.ed.ac.uk/wadler/papers/class-letter/cla... --- they possibly didn't expect OOP and "classes" (Stroustrup '79) to become quite so very ubiquitous as they did in the 90s.


You... don't really think Stroustrup invented the term "class", do you? :)


Of course not but that sort of meaning for the term class was GP's point here


And my point is that that usage of the term predates Stroustrup by 10 solid years.

By the time Haskell was first released, OOP was either already available in popular languages (Smalltalk, Object Pascal) or being introduced into existing languages (Objective C, C++, Lisp).

In hindsight it would appear there was no reason not to see that OOP was gaining in popularity, that the term "class" was already in use, and that overloading it would be confusing.

That said, in the end, all my original post was lamenting is that it's a shame that Haskell terminology went the way it did... it's just yet another aspect of the language that creates confusion among newcomers, and it already has enough of that already! :)


I don't think the creators of Haskell were concerned even slightly with trying to fit in with trends in imperative languages. They were doing their own thing (or at least, trying to make a research-friendly version of David Turner's commercial language Miranda).


Your explanation does not justify the choice. They were tasked with communicating with other academics who were already using the term "class" in the field of programming language research.


To be blunt, it doesn't need to be justified. Should I call cars horseless carriages simply because that was the original term? Have you seen how bad the situation is in mathematics where the exact same concept has multiple names? This isn't a unique thing to have happen. Nor one to fret this much over.

The haskell committee were concerned with conveying knowledge amongst functional programming researchers. The use of class in similar but unrelated fields doesn't mean everyone need use it.


If you call a fish a "car" don't be surprised when people get confused and think that choice of name was ill-advised. Car is already in use, don't use car to describe a fish, it's not difficult. When a word has an accepted meaning, using that word to convey an entirely different meaning where you could easily choose something else is ridiculous. It is right to criticise anyone who does something so silly.

Or you can think I'm just flying the mountain with ice cream windows if you like.


It depends whether you care about catering to a general audience.

Lisp got away with an entirely different meaning for “car” for a pretty long time!


But classes in the traditional OOP sense are types of values, while Haskell typeclasses are types of types. There is no opportunity for confusion.


Well, Smalltalk had been around for 16 years, Simula for over 20.

The whole world of GUI programming was based on OO.


The whole world of GUI programming consisted of a bunch of top of line labs and some research centers studying GUIs.


Huh?

The Xerox Star was introduced in 1981 https://en.wikipedia.org/wiki/Xerox_Star

Apple's Lisa was introduced in 1983. https://en.wikipedia.org/wiki/Apple_Lisa

With it, Lisa Toolkit and Clascal (Pascal with Classes) http://www.mirrorservice.org/sites/www.bitsavers.org/pdf/app...

The Mac in 1984 https://en.wikipedia.org/wiki/Macintosh_128K

MacApp in 1985 https://en.wikipedia.org/wiki/MacApp

The Tektronix 4404 running Smalltalk, also 1984 http://www.wirfs-brock.com/allen/files/tek/4404-Flyer.pdf

The Amiga and Atari ST in 1985.

Windows was at 2.0 in 1987.

Heck, the NeXT cube had been introduced by fall of '88.

https://en.wikipedia.org/wiki/NeXT_Computer


I think the logic behind the name is e.g. “‘Eq t’ is the class of types ‘t’ that support equality”, with “class” having the sense of “subset”.


That's exactly how I think of it: Typeclass = a class of types, which makes my C++ brain think of templates not inheritance.


Oh, I don't dispute the name is logical.

I'm saying in the broader context of programming languages, it's confusing. And that that confusion could have been easily foreseen and avoided... after all, Smalltalk had been using the term "class" for almost 20 years before Haskell appeared and introduced their terminology.


Haskell uses the words "type", "class", and "kind", and maybe some others too, which are all just simple English words that denote some form of abstract grouping ("form" and "group" I suppose are two other candidates).

At least they're called "typeclasses" and not just "classes". But we're always going to have some overloading of these powerful short ancient words.

I did recently see a suggestion to rename the "typeclass" keyword to "algebra" which would be pretty cool!


Quite. Typeclasses are Haskell's way of doing ad hoc polymorphism. C++ has ad hoc polymorphism too, but it's via templates not classes.


Typeclasses also do virtual dispatch, though. That comparison isn't much closer.


Not an Haskell expert (or even a beginner really, just generally interested in language design), but as far as I understand in 99% of the cases virtual dispatch in Haskell is purely an implementation detail: i.e. type classes can be implemented via monomorphization exactly like C++ templates (and in fact the compiler will do exactly that when optimising or when explicitly directed to do so); it isn't done by default mostly to preserve separate compilation and code explosion.

There are cases where that can't be done at all (polymorphic recursion, when the recursion can't be proven to terminate at compile time, I'm sure there are other) and runtime dispatching is required, but that's more of an exception. In C++ that's implemented with explicit, semi manually implemented, type erasure wrappers.

edit: as I said, I'm not an Haskell programmer; maybe in idiomatic Haskell the cases where runtime dispatch is required are much more common.


Imagine you have a problem for which you need virtual dispatch. In C++, you typically reach for inheritance. In Haskell, you typically reach for typeclasses.

Comparatively, imagine you have a problem for which you need ad-hoc, but statically resolvable, overloads. In C++, you typically reach for templates. In Haskell, you instead typically reach again for typeclasses.

This is what I mean when I say neither comparison is really closer than the other. Haskell couldn't replace typeclasses with templates, just as it couldn't replace them with objects.


You should realize that the term "class" has also meaning in mathematics, which is a different meaning than in programming. So from mathematics perspective, the name is apt.

I am not sure what other name you would suggest, anyway.


I think `interface` is probably the software engineering terminology that comes closest. Leading to:

    interface Eq a where
       (==), (/=) :: a -> a -> Bool
       x /= y     =  not (x == y)

    implement (Eq a) => Eq (Tree a) where
       Leaf a         == Leaf b          =  a == b
       (Branch l1 r1) == (Branch l2 r2)  =  (l1==l2) && (r1==r2)
       _              == _               =  False
Not bad. But not a total game changer either. Probably makes more immediate sense for most new comers though.


It is close but typeclasses are not interfaces either.

They could have used a fashionable and somewhat overloaded term like "interface" or "protocol" or "trait" or "flavor", or they could have used an exact, albeit somewhat bland, name coming from mathematics. They did the latter.

In fact, they have faced a similar choice for many aspects of the language, and in most cases, mathematical purity got precedence over practicality. Had they chosen differently, the result wouldn't be Haskell.


> It is close but typeclasses are not interfaces either.

Why not? They seem to be exactly interfaces to me.

> They could have used a fashionable and somewhat overloaded term like "interface" or "protocol" or "trait" or "flavor", or they could have used an exact, albeit somewhat bland, name coming from mathematics. They did the latter.

The terminology "class" in Haskell certainly has nothing to do with its mathematical meaning of "collection of sets defined by a predicate".


> They seem to be exactly interfaces to me.

If we are talking about interface like in Java, for instance, then the important difference is that in Java, class specifies what interfaces it has, while in Haskell, any code can specify how a type is a member of a type class (actually there can be multiple different ways how the same type can be member of same type class). Another difference was, until recently, that the type classes can define "default" implementations of functions. And there are other differences related to "deriving" statement.

> The terminology "class" in Haskell certainly has nothing to do with its mathematical meaning of "collection of sets defined by a predicate"

I don't want to get into philosophy of math, I am not strong in it, but "class" in mathematics is certainly not limited to collections of sets. For example, there is a class of all classes, but not set of all sets.

The predicate that defines the type class in Haskell is defined by the collection of all the relevant "instance" statements.

Actually, now that I think about it, as I note above, there are multiple ways that one type can be made a member of one type class, so it's certainly not a membership in the set-theoretic sense.


In popular OOP languages (C#, Java, etc), interfaces give you a way to state that some existentially quantified type implements some set of common methods. Here's what I mean by "existentially quantified":

Let's say you have some function called GetStringableThing() that returns returns, as its name suggests, some object that implements the Stringable interface -- where Stringable is just an interface that consists of a ToString() method. As the caller of GetStringableThing(), you have no say in precisely which type of Stringable thing you'll get -- that's up to the callee. So there exists some type that implements Stringable, which GetStringableThing() would be more than happy to give you. This is in contrast with universal quantification; if the return type of GetStringableThing() was universally quantified, that would mean that you as the caller get to dictate the return type (so long as it implements Stringable), and its the callee's responsibility to be able to return any type the caller demands.

Typeclasses (as in Haskell) have the benefit of allowing you, as the caller of a function, to dictate the return type of that function -- in fact, universal quantification is the default, and you have to go out of your way (e.g. with GADTs) to represent existential types.

This now leads us to a common pitfall for people coming to Haskell from OOP languages, where their intuition that "typeclass == interface" fails them:

    -- The intent here is the same as earlier with "Stringable",
    -- though in Haskell that would be "Show".
    --
    -- A beginner's intuition:
    -- "Surely this reads 'somethingShowable is some type implementing the Show interface', right?"
    somethingShowable :: (Show a) => a
    somethingShowable = (42 :: Int)
A beginner will often think that the above should compile ("42 is an Int, and Int has a Show instance, so this should work, right? I just need to provide something that has a Show instance, right?"). Unfortunately, it doesn't compile. The above code is making the promise that it can provide a value of any type that the caller demands (so long as it implements Show), but here we're only providing an integer specifically.

This bit of OOP pseudo-code captures what they we're going for:

    func getStringableThing() Stringable {
      return 42
    }
A natural implication of this universal vs existential quantification distinction is this:

Typeclass instances are resolved at compile time (except where you've gone out of your way to existentially type something), and can be specialized and inlined accordingly. Interfaces (a la OOP) are implemented via some sort of vtable mechanism, where dispatch is deferred until runtime (though a JIT can potentially do some inlining).

Interfaces (a la OOP) and typeclasses are implemented (and behave) quite differently, so I would argue that if Haskell were to replace its use of "class" (and "typeclass") with "interface" it would only confuse things further (as evidenced by the constant stream of beginners asking for help where they've made this exact conflation; for the record, I was one of these beginners 3 years ago).

The "they shouldn't call these (type)classes!" complaint is quite tiring: no one ever has a reasonable alternative to offer. At least (type)class makes some sense when you realize that "class" is meant in the mathematical sense of the word "class".


Yes, I get that.

It's still confusing. And programming languages exist to first and foremost aid programmers, not to adhere to some abstract expression of mathematical perfection.

At the time Haskell hit the scene, the term Interface was free and could've been taken. But that's just one thought, I'm not a language designer...


I agree. But it might be fair to say that the Haskell people often think that they're doing mathematics, not programming. (Or at least they act like they think that.)


To me, type-classes are used like a less flexible form of duck typing. I would really like to see a more flexible strongly typed duck-typing than type-classes. I think that a sufficiently advanced IDE could auto-generate, from an expression, a "duck-type" for each untyped object used. For example, if you have the expression:

    (given) g :: Int -> String
    function a =
     let
      l = (f a)
     in
      g l
Would it be possible to generate the duct-type

"function :: (a which has a method f :: a -> Int) -> String"

Now you're not saying that a has to belong to a typeclass, you are saying that a has a duck-type of any value with a method f :: a -> Int.


I think OCaml does what you are looking for. See the example on https://en.wikipedia.org/wiki/Structural_type_system, which features OCaml.


Thanks, looks interesting. One of the things I've always wondered about with this approach is, how do you then show the "duck type"s in a succinct and human readable way.

This is pretty succinct, but I'd have to say that it is not obvious what the syntax means:

     val y : < get_x : int; set_x : int -> unit > = <obj>
Perhaps the example was poorly chosen, what is "unit"?


Unit is a type that has exactly one value, (). It's often used like `void` is used in C-like languages.

So this:

    val y : < get_x : int; set_x : int -> unit >
means an object that has a get_x method that returns an int, and a set_x method that takes an int and returns unit (void).


It's () in haskell. Here's a good write-up: https://stackoverflow.com/a/16893900


Fine. Now propose a concrete type-checking algorithm. And make it scalable.


I think row types are probably what OP is looking for. And they can be fully inferred.


I don't think row polymorphism is what the OP asked for. They might be what the OP wants, but that's a-whole-nother matter.

If I understood correctly, the OP asked for a “duck type of all values on which a function `f` can be applied”. Alas, OCaml-like object types are glorified function types, not duck types:

(0) The type of an object is the type of its methods.

(1) The type of an object is not the type of its internal state.

Say you have a particular data type like `float list`, and you want to “bless it with a method `f`”, so that you can pass a `float list` to any context that expects an object with a method `f`. This is everyday stuff in duck-typed languages.

Turns out, you can't. The best thing you can do is explicitly construct an object with a method `f`, and whose state happens to be a `float list`. Alas, because the state isn't a part of the object's type, there is no way a user of the object can recover the original `float list`. In fact, no user of the object has any way to tell whether the object's internal state is a `float list` or something else altogether.


> I don't think row polymorphism is what the OP asked for. They might be what the OP wants, but that's a-whole-nother matter.

I think that's the other way around. It appears to be what they asked for, even if it may not be what they want.

They pretty clearly said they wanted to be able to write a type that says "Object that has method f :: a -> Int".

What you're talking about doesn't seem to be duck typing (though it might work nicely along side duck typing), it's being able to add methods to objects at run time (unless I'm misunderstanding).




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: