4 ms·

I'm curious what programs people are writing where parametric polymorphism is so crucial. I've written hundreds of thousands of lines of Go code (servers, web a

I'm curious what programs people are writing where parametric polymorphism is so crucial. I've written hundreds of thousands of lines of Go code (servers, web apps, data processing, etc.), and there's probably been maybe O(hundreds) of lines of code that were annoying or tedious because of a lack of parametric polymorphism. My suspicion is that what's more likely is that lots of people don't want to consider writing their programs a little differently, and see that writing code with parametric polymorphism is the only acceptable solution to their problem. But maybe there's a whole class of problem (actual problem, not a sub-problem like "I want to implement a container") that I don't come in contact with.

cgag 13y ago
"But maybe there's a whole class of problem (actual problem, not a sub-problem like "I want to implement a container") that I don't come in contact with." i want to apply a transformation to every element in a collection i want to select the elements from a collection for which some predicate holds true
- redbad 13y ago
  Those are both sub-problems.
  - cgag 13y ago
    of every software problem in history
- mseepgood 13y ago
  Use a for loop. Stop thinking in LISP/Haskell/LINQ, start thinking in Go. Go is an imperative programming language. When in Rome do as the Romans do. Look at the code of the standard library to see how it's done.
  - pcwalton 13y ago
    It's not because it's unfamiliar that people are objecting; it's because it's suboptimal. Loops are harder to get right (try writing the loop to count down from 100 to 0 inclusive on unsigned ints), and they involve more boilerplate, obscuring the meaning of the code. I don't think generics are an imperative/functional thing so much as an important feature of any statically typed system.
colin_mccabe 13y ago
I think a big part of the issue is that in Java and C++, you really need generics a lot more than in Go. Without templates, you would not have any easy way of doing maps and lists in C++. There are no builtin types for those like in Go. The way the type system works in those languages also makes things very difficult if you don't have generics. Think about the sorting example I wrote earlier: https://news.ycombinator.com/item?id=7080562 https://news.ycombinator.com/item?id=7080562 If you were writing it in Java, is sort.Sort an interface or an abstract base class? Well, you can only "extend" one class (single inheritance only), so you would probably want Sort to be a Java interface. That means that you would always have to implement all three functions, not just one as I did, since Java interfaces cannot have default implementations. The comments indicate that most posters didn't even consider the idea that you could reuse the StringSlice functions. That method of easy composition simply doesn't exist in Java. In general, generics get used a lot as a band-aid to avoid multiple inheritance in C++ and Java. You can't (or shouldn't, in C++) have your Foo inherit from both a (non-abstract) Bar and Baz. But you can certainly template on them. In C++, this kind of thing is called "traits" and Alexandrescu wrote a whole book about it. It's also why std::string is actually std::basic_string<char, std::char_traits<char>, std::allocator<char> >. In Go, you don't need all this... you just implement as many interfaces as you like and you're done. So the Java and C++ programmers need time and an open mind to get up to speed. There's also another contingent of programmers that really just wants Go to be like their favorite strongly-typed functional programming language (Haskell, Scheme, SML, etc.) I like to think that these people will eventually give up. After all, nobody comes into every Lisp thread demanding that Lisp grow a type-checker. People have sort of accepted that that is not what Lisp is about and that there are other languages that will give you that if you want. Hopefully much the same will happen for Golang.
- pjmlp 13y ago
  Java 8 will have interfaces with default implementations. There are a few of optional type checkers for Lisp to choose from.
- scott_s 13y ago
  It is common in both C++ and Java for a class to implement several interfaces. So, one can accomplish the same kind of genericity in C++ and Java as one can in Go. Both languages still eventually saw enough of a need for a kind of generics to develop one. There is a difference in Go, and that is you don't need to explicitly implement the interface. That is, you don't need to declare that you do. But I am unconvinced that is so different from implementing interfaces in C++ and Java that C++ and Java programmers "need time and an open mind" to understand Go idioms. Don't get me wrong: I think Go is a neat language and culture. I like many aspects of it. And I know the stance the designers of Go have on generics: they would like to do them, but they can't think of a design that they like. And they don't consider it that important, so they've bunted on it. They may do them in the future. But I find it strange when people who are not the designers of the language argue against having them, in any form.
tel 13y ago
I think the biggest advantage of parametric polymorphism comes from program analysis, not just increased capability. The notion of parametricity depends crucially on parametric polymorphism and is super useful. Parametricity is the property that says greater polymorphism means lesser variation in implementation. Highly parametric functions can be almost completely described by their types along meaning it provides incredibly high value as documentation. The most common simple example is reasoning about the following pair of functions f :: a -> a g :: Int -> Int While (f > g) obviously, we can completely characterize the behavior of `f` while we know almost nothing at all about `g`. Up to non-termination, `f` must be `id` while `g` can be any recursive function on integers. g a = 3 f a = a g a = a * 2 g a = if (a == 0) then 1 else a * g (a - 1) If you hold in advance the triviality of this example, then we can already notice how much better documentation `f`'s type provides than `g`'s. We also can produce a list of properties and laws about `f`'s behavior that we cannot easily do with `g`. This means that I'm able to reason about `f` better and more confidently. --- So we can take it up a notch. Consider Functors in Haskell. In order to avoid the full generality, let's just say Functor is the container interface and types like [], Set, and Map instantiate it. This gives them the function fmap :: (a -> b) -> f a -> f b where `f` is specialized to the particular container of interest fmap :: (a -> b) -> [a] -> [b] fmap :: (a -> b) -> Set a -> Set b fmap :: (a -> b) -> Map k a -> Map k b -- for some key type k Now what can we reason about `fmap`s knowing only their type? Well, since the type `a` contained inside each container is unknown (or, to be more clear, any implementation of fmap must work for any type `a` and thus it's "unknown" in that we can't take advantage of information about it) then the only thing `fmap` is capable of doing is applying the first function to those types. Furthermore, since every mention of `a` vanishes in the result of the function we know that each value in the input container must either be transformed by the input function or dropped. -- a specific example, not a general function fmap f [a, b, c] = [f a, f b, f b] In this way, parametricity has pruned down the possibilities of functions that can implement `fmap` a great deal. If `a` or `b` were specialized to specific types then this would not be the case as we'd have a large variety of specific functions that could apply to each one of them. notFmap :: (Int -> Char) -> [Int] -> [Char] notFmap f [n1, n2, n3] = [f (n1 + 2), head (show n2), chr n3] ++ "hello world!" Indeed, in order to ensure that type-checking `fmap`s behave correctly we say they must follow a few laws. First, they respect function composition and second they respect identity fmap g (fmap f x) == fmap (g . f) x fmap id x == id x And we only ever need to check the first one because the second one is already guaranteed by a more sophisticated parametricity argument. fmap f [] = [] fmap f (x:xs) = f x : fmap f xs --- The take away is that while you can definitely write something that "maps over containers" without using parametric polymorphism, you have a harder time taking advantage of parametricity to have the types provide guarantees about the safe behavior of functions. Types (and in particular type inference) can sometimes make things more expressive, but their primary power lies in making things easier to understand and reason about.
lukaseder 13y ago
Parametric polymorphism is crucial in an API like jOOQ's: http://www.jooq.org http://www.jooq.org In fact, it is one of the fundamental cornerstones of internal DSLs
sdboyer 13y ago
heh, interesting. as somebody mucking about with containers in Go, i also recognize it to be a sub-problem, and not one really worth having a language-level debate over. perhaps odd, because i come from a crappily-typed PHP background. but if PHP teaches you anything, it's that you can accomplish just about anything with arrays (maps/slices).

cgag 13y ago

"But maybe there's a whole class of problem (actual problem, not a sub-problem like "I want to implement a container") that I don't come in contact with." i want to apply a transformation to every element in a collection i want to select the elements from a collection for which some predicate holds true

redbad 13y ago
Those are both sub-problems.
- cgag 13y ago
  of every software problem in history
mseepgood 13y ago
Use a for loop. Stop thinking in LISP/Haskell/LINQ, start thinking in Go. Go is an imperative programming language. When in Rome do as the Romans do. Look at the code of the standard library to see how it's done.
- pcwalton 13y ago
  It's not because it's unfamiliar that people are objecting; it's because it's suboptimal. Loops are harder to get right (try writing the loop to count down from 100 to 0 inclusive on unsigned ints), and they involve more boilerplate, obscuring the meaning of the code. I don't think generics are an imperative/functional thing so much as an important feature of any statically typed system.

colin_mccabe 13y ago

I think a big part of the issue is that in Java and C++, you really need generics a lot more than in Go. Without templates, you would not have any easy way of doing maps and lists in C++. There are no builtin types for those like in Go. The way the type system works in those languages also makes things very difficult if you don't have generics. Think about the sorting example I wrote earlier: https://news.ycombinator.com/item?id=7080562 https://news.ycombinator.com/item?id=7080562 If you were writing it in Java, is sort.Sort an interface or an abstract base class? Well, you can only "extend" one class (single inheritance only), so you would probably want Sort to be a Java interface. That means that you would always have to implement all three functions, not just one as I did, since Java interfaces cannot have default implementations. The comments indicate that most posters didn't even consider the idea that you could reuse the StringSlice functions. That method of easy composition simply doesn't exist in Java. In general, generics get used a lot as a band-aid to avoid multiple inheritance in C++ and Java. You can't (or shouldn't, in C++) have your Foo inherit from both a (non-abstract) Bar and Baz. But you can certainly template on them. In C++, this kind of thing is called "traits" and Alexandrescu wrote a whole book about it. It's also why std::string is actually std::basic_string<char, std::char_traits<char>, std::allocator<char> >. In Go, you don't need all this... you just implement as many interfaces as you like and you're done. So the Java and C++ programmers need time and an open mind to get up to speed. There's also another contingent of programmers that really just wants Go to be like their favorite strongly-typed functional programming language (Haskell, Scheme, SML, etc.) I like to think that these people will eventually give up. After all, nobody comes into every Lisp thread demanding that Lisp grow a type-checker. People have sort of accepted that that is not what Lisp is about and that there are other languages that will give you that if you want. Hopefully much the same will happen for Golang.

pjmlp 13y ago
Java 8 will have interfaces with default implementations. There are a few of optional type checkers for Lisp to choose from.
scott_s 13y ago
It is common in both C++ and Java for a class to implement several interfaces. So, one can accomplish the same kind of genericity in C++ and Java as one can in Go. Both languages still eventually saw enough of a need for a kind of generics to develop one. There is a difference in Go, and that is you don't need to explicitly implement the interface. That is, you don't need to declare that you do. But I am unconvinced that is so different from implementing interfaces in C++ and Java that C++ and Java programmers "need time and an open mind" to understand Go idioms. Don't get me wrong: I think Go is a neat language and culture. I like many aspects of it. And I know the stance the designers of Go have on generics: they would like to do them, but they can't think of a design that they like. And they don't consider it that important, so they've bunted on it. They may do them in the future. But I find it strange when people who are not the designers of the language argue against having them, in any form.

tel 13y ago

I think the biggest advantage of parametric polymorphism comes from program analysis, not just increased capability. The notion of parametricity depends crucially on parametric polymorphism and is super useful. Parametricity is the property that says greater polymorphism means lesser variation in implementation. Highly parametric functions can be almost completely described by their types along meaning it provides incredibly high value as documentation. The most common simple example is reasoning about the following pair of functions f :: a -> a g :: Int -> Int While (f > g) obviously, we can completely characterize the behavior of `f` while we know almost nothing at all about `g`. Up to non-termination, `f` must be `id` while `g` can be any recursive function on integers. g a = 3 f a = a g a = a * 2 g a = if (a == 0) then 1 else a * g (a - 1) If you hold in advance the triviality of this example, then we can already notice how much better documentation `f`'s type provides than `g`'s. We also can produce a list of properties and laws about `f`'s behavior that we cannot easily do with `g`. This means that I'm able to reason about `f` better and more confidently. --- So we can take it up a notch. Consider Functors in Haskell. In order to avoid the full generality, let's just say Functor is the container interface and types like [], Set, and Map instantiate it. This gives them the function fmap :: (a -> b) -> f a -> f b where `f` is specialized to the particular container of interest fmap :: (a -> b) -> [a] -> [b] fmap :: (a -> b) -> Set a -> Set b fmap :: (a -> b) -> Map k a -> Map k b -- for some key type k Now what can we reason about `fmap`s knowing only their type? Well, since the type `a` contained inside each container is unknown (or, to be more clear, any implementation of fmap must work for any type `a` and thus it's "unknown" in that we can't take advantage of information about it) then the only thing `fmap` is capable of doing is applying the first function to those types. Furthermore, since every mention of `a` vanishes in the result of the function we know that each value in the input container must either be transformed by the input function or dropped. -- a specific example, not a general function fmap f [a, b, c] = [f a, f b, f b] In this way, parametricity has pruned down the possibilities of functions that can implement `fmap` a great deal. If `a` or `b` were specialized to specific types then this would not be the case as we'd have a large variety of specific functions that could apply to each one of them. notFmap :: (Int -> Char) -> [Int] -> [Char] notFmap f [n1, n2, n3] = [f (n1 + 2), head (show n2), chr n3] ++ "hello world!" Indeed, in order to ensure that type-checking `fmap`s behave correctly we say they must follow a few laws. First, they respect function composition and second they respect identity fmap g (fmap f x) == fmap (g . f) x fmap id x == id x And we only ever need to check the first one because the second one is already guaranteed by a more sophisticated parametricity argument. fmap f [] = [] fmap f (x:xs) = f x : fmap f xs --- The take away is that while you can definitely write something that "maps over containers" without using parametric polymorphism, you have a harder time taking advantage of parametricity to have the types provide guarantees about the safe behavior of functions. Types (and in particular type inference) can sometimes make things more expressive, but their primary power lies in making things easier to understand and reason about.

lukaseder 13y ago

Parametric polymorphism is crucial in an API like jOOQ's: http://www.jooq.org http://www.jooq.org In fact, it is one of the fundamental cornerstones of internal DSLs

sdboyer 13y ago

heh, interesting. as somebody mucking about with containers in Go, i also recognize it to be a sub-problem, and not one really worth having a language-level debate over. perhaps odd, because i come from a crappily-typed PHP background. but if PHP teaches you anything, it's that you can accomplish just about anything with arrays (maps/slices).