6 ms·

Implementing and Understanding Type Classes (2014)

118 points by z1mm32m4n 8y ago

cjhanks 8y ago
It takes a true Haskell mind to take something so intuitively obvious and make it incomprehensible. Most language users simply take for granted that they can easily write them in C++, Python, Dlang, Java, C#, ...
- hexane360 8y ago
  Are you kidding? Let's take C++: Templates are a dark art, generics are confusing and ugly, and inheritance is so so easy to screw up. Python: You use inheritance or duck typing, neither of which provide you any guarantees.
  - cjhanks 8y ago
    If you're afraid of your programming languages, maybe change jobs?
    - monocasa 8y ago
      Come on, even Herb Sutter thinks that the way people contort the template metaprogramming system leaves something to be desired, hence the constexpr blocks and metaclasses proposals coming down the pipeline.
- green_on_black 8y ago
  What? Could you give me a Java example??
- ionforce 8y ago
  Comprehensibility is a function of both the author and the recipient. I find that a lot of functional enthusiasts (e.g. people who are very, very comfortable with type classes) truly lack the relate-ability to make the material accessible to people who lack the same background as them.
- Sharlin 8y ago
  Do you even know what type classes are? Not to mention that this article has nothing to do with using type classes.
  - cjhanks 8y ago
    I do. And fwiw, "It takes a true Haskell mind to take something so intuitively obvious and make it incomprehensible." is both a compliment and a gibe. I guess most people are pessimists.
- zenhack 8y ago
  Not one of those languages has a construct equivalent to Haskell's type classes.
- dang 8y ago
  Could you please not do programming language flamewars here? https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html
calebh 8y ago
I've looked at this page and some other documents since I wanted to implement type classes in Juniper (a FRP language for the Arduino). It turns out that the dictionary passing is only necessary if you want to support polymorphic recursion. In all other cases, the call to a function that is part of a type class can be monomorphized. Hindley-Milner has problems with inferring types in the presence of polymorphic recursion, and a user provided type annotation is usually necessary. Polymorphic recursion does allow some cool things such as arbitrarily nested lists. This is a feature that users from a dynamically typed language might miss.
- mbid 8y ago
  > arbitrarily nested lists "Cool" as it might be, please don't inflict it on others.
  - baddox 8y ago
    I’m not aware of the specific type features the commenter was mentioning, but that doesn’t sound too different than a tree or graph data structure.
    - joshlemer 8y ago
      I believe the commenter may have been talking about what I've seen called fix-point recursion, and it is exactly as you say, it is for representing arbitrarily nested tree structures in a statically typed way. For example in scala, maybe you have data about Users case class User(id: Long, name: String, friends: List[User]) However, this structures is kinda inflexible, you don't always want to deal with an entire tree of users at a time. Maybe, you just want to have the friend userids, so you can introduce a type parameter for the recursive data case class User[Friend](id: Long, name: String, friends: List[Friend]) and then you can have a User[Long] which contains the friend ids, or User[String] which contains the friend names. However, if you want to go back and have the list be of Users themselves, you would have to know statically how deep the tree you're returning is. For example, this type would include full user information down to the grandchild level, but then terminate with the ids: User[User[User[Long]]] This is actually very useful! Sometimes we may want exactly this deep of a structure. If we want to get an arbitrarily deep tree of users, we would need to have an infinitely nested type like User[User[User[User[User[User[...]]]]]] which is of course impossible. So instead, people have a work-around using higher-kinded types, called `Fix`: case class Fix[F[_]](unfix: F[Fix[F]]) This signature may look scary, but if you apply it to User you get Fix[User](unfix: User[Fix[User]]) and all this means is that now we can deal with Fix[User] which means the same thing as User[User[...]]. You can construct one such Fix[User] differing levels like so: Fix( User( id = 1L, name = "Josh", friends = List( Fix( User( id = 2L, name = "John", friends = List( Fix( User( id = 3L, name = "Stacey" friends = List.empty ) ) ) ), Fix( User( id = 4L name = "Mary" friends = List.empty ) ) ) )
brianberns 8y ago
As an F# developer (no type classes), I found this very informative. Thank you. I'm looking forward to the day when .NET languages (including C#) support type classes.

118 points by z1mm32m4n 8y ago

It takes a true Haskell mind to take something so intuitively obvious and make it incomprehensible. Most language users simply take for granted that they can easily write them in C++, Python, Dlang, Java, C#, ...

hexane360 8y ago
Are you kidding? Let's take C++: Templates are a dark art, generics are confusing and ugly, and inheritance is so so easy to screw up. Python: You use inheritance or duck typing, neither of which provide you any guarantees.
- cjhanks 8y ago
  If you're afraid of your programming languages, maybe change jobs?
  - monocasa 8y ago
    Come on, even Herb Sutter thinks that the way people contort the template metaprogramming system leaves something to be desired, hence the constexpr blocks and metaclasses proposals coming down the pipeline.
green_on_black 8y ago
What? Could you give me a Java example??
ionforce 8y ago
Comprehensibility is a function of both the author and the recipient. I find that a lot of functional enthusiasts (e.g. people who are very, very comfortable with type classes) truly lack the relate-ability to make the material accessible to people who lack the same background as them.
Sharlin 8y ago
Do you even know what type classes are? Not to mention that this article has nothing to do with using type classes.
- cjhanks 8y ago
  I do. And fwiw, "It takes a true Haskell mind to take something so intuitively obvious and make it incomprehensible." is both a compliment and a gibe. I guess most people are pessimists.
zenhack 8y ago
Not one of those languages has a construct equivalent to Haskell's type classes.
dang 8y ago
Could you please not do programming language flamewars here? https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html

calebh 8y ago

I've looked at this page and some other documents since I wanted to implement type classes in Juniper (a FRP language for the Arduino). It turns out that the dictionary passing is only necessary if you want to support polymorphic recursion. In all other cases, the call to a function that is part of a type class can be monomorphized. Hindley-Milner has problems with inferring types in the presence of polymorphic recursion, and a user provided type annotation is usually necessary. Polymorphic recursion does allow some cool things such as arbitrarily nested lists. This is a feature that users from a dynamically typed language might miss.

mbid 8y ago
> arbitrarily nested lists "Cool" as it might be, please don't inflict it on others.
- baddox 8y ago
  I’m not aware of the specific type features the commenter was mentioning, but that doesn’t sound too different than a tree or graph data structure.
  - joshlemer 8y ago
    I believe the commenter may have been talking about what I've seen called fix-point recursion, and it is exactly as you say, it is for representing arbitrarily nested tree structures in a statically typed way. For example in scala, maybe you have data about Users case class User(id: Long, name: String, friends: List[User]) However, this structures is kinda inflexible, you don't always want to deal with an entire tree of users at a time. Maybe, you just want to have the friend userids, so you can introduce a type parameter for the recursive data case class User[Friend](id: Long, name: String, friends: List[Friend]) and then you can have a User[Long] which contains the friend ids, or User[String] which contains the friend names. However, if you want to go back and have the list be of Users themselves, you would have to know statically how deep the tree you're returning is. For example, this type would include full user information down to the grandchild level, but then terminate with the ids: User[User[User[Long]]] This is actually very useful! Sometimes we may want exactly this deep of a structure. If we want to get an arbitrarily deep tree of users, we would need to have an infinitely nested type like User[User[User[User[User[User[...]]]]]] which is of course impossible. So instead, people have a work-around using higher-kinded types, called `Fix`: case class Fix[F[_]](unfix: F[Fix[F]]) This signature may look scary, but if you apply it to User you get Fix[User](unfix: User[Fix[User]]) and all this means is that now we can deal with Fix[User] which means the same thing as User[User[...]]. You can construct one such Fix[User] differing levels like so: Fix( User( id = 1L, name = "Josh", friends = List( Fix( User( id = 2L, name = "John", friends = List( Fix( User( id = 3L, name = "Stacey" friends = List.empty ) ) ) ), Fix( User( id = 4L name = "Mary" friends = List.empty ) ) ) )

brianberns 8y ago

As an F# developer (no type classes), I found this very informative. Thank you. I'm looking forward to the day when .NET languages (including C#) support type classes.