4 ms·

Of course C#, because of subtyping, also has contravariant type parameters (unlike Haskell). The variance phenomena shows up in many places.

evincarofautumn 8y ago
A kind of subtyping does show up in Haskell with higher-rank polymorphism: the System F “generic instance” subtyping rule. Namely, for types A and B, A is a subtype of B iff A is a “generic instance” of B, meaning A is at least as polymorphic as B. “Higher-rank polymorphism” sounds scarier than it is, too, by the way. It’s basically just a way to pass polymorphic functions as arguments. It’s what you really want any time you think you’re craving a “virtual template” in C++; the typical OOP solution in a language like C# is more convoluted, usually consisting of wrapping the function in a class with a generic method and invoking it through an interface. The intuition is that you can pass a more polymorphic function (like the identity function of type “∀a. a → a”) as an argument to a function expecting a less polymorphic one (like “Int → Int”) and it’ll just be specialised—but you clearly can’t do the reverse because “Int → Int” doesn’t accept all the types that “∀a. a → a” does (like “String → String”, “Char → Char”, “Bool → Bool”, &c.). However, the subtyping gets flipped every time you go to the left of a function arrow, because it’s contravariant. And you only notice this with higher-rank polymorphism because that’s the only place Haskell has a subtyping rule like this. My usual example, stolen from an SPJ paper, is: f ∷ ((∀a. [a] → [a]) → Int) → Int f x = x (drop 1) g ∷ ([Int] → [Int]) → Int g y = sum (y [1, 2, 3]) h ∷ (∀a. a → a) → Int h z = z 5 Or, in pseudo-imperative notation for those not familiar with Haskell: func f(x: (<T> (List<T> => List<T>)) => int): int { return x(list => list.drop(1)); } func g(y: List<int> => List<int>): int { return y([1, 2, 3]).sum(); } func h(z: <T> (T => T)): int { return z(5); } “f g” works because “([Int] → [Int]) → Int” (the type of g) is more polymorphic than “(∀a. [a] → [a]) → Int” (the type of x, the parameter of f), because “[Int] → [Int]” (the type of y, the parameter of g) is less polymorphic than “∀a. [a] → [a]” (the type of the parameter of x). f g f (\ y -> sum (y [1, 2, 3])) (\ y -> sum (y [1, 2, 3])) (drop 1) sum (drop 1 [1, 2, 3]) sum [2, 3] 5 But “f h” is a type error, because “(∀a. a → a) → Int” (the type of h) is less polymorphic than “(∀a. [a] → [a]) → Int” (the type of x), because “∀a. a → a” is more polymorphic than “∀a. [a] → [a]” (the type of the parameter of x). And indeed it’s easy to come up with a type-incorrect implementation as I’ve done here—if you could run it, you’d end up trying to call “drop” on a number instead of a list: f h f (\ z -> z 5) (\ z -> z 5) (drop 1) drop 1 5
- coldtea 8y ago
  >“Higher-rank polymorphism” sounds scarier than it is, too, by the way Well, there's some irony of writing that after 6 paragraphs filled with obscured Haskellise. (Even though it's just some basic functional stuff in the end, like map, drop, sum etc, they will definitely look alien to anyone uninitiated).
  - evincarofautumn 8y ago
    Good point, haha, I did see the irony while writing that. I’ve moved that paragraph up toward the top in the hope it helps somewhat. :P The thing about a lot of these big scary concepts in Haskell is that they’re really simple, the kind of thing where, once it clicks, you go “Oh! That’s all?”, but that doesn’t mean they’re easy—you’ve got to get familiar with the notation and jargon, and spend time building intuition from examples and just trying things out. Nowadays I think of my process of learning new things as “try to realise how simple it is”, i.e. “what do experts understand (or just have memorised) that makes this easy for them?” It’s been a lot more motivating and pleasant than my old tactic of “try to cram this into my head without ‘chewing’ and hope my brain can digest it”.
  - willtim 8y ago
    Haskell does make a great semi-formal language with which to communicate functional programming ideas, even if you have no plans to ever use an implementation of it. Mainstream languages are beginning to borrow more and more ideas from it (albeit often with significantly more verbose syntax). Much of the research literature in functional programming also uses Haskell syntax, so IMHO it is worth any developer learning.
  - MaxBarraclough 8y ago
    They say you need a PhD to use Haskell. It's not true. I've seen PhD students use it!
    - deleted 8y ago
      [deleted]
    - 8y ago

evincarofautumn 8y ago

A kind of subtyping does show up in Haskell with higher-rank polymorphism: the System F “generic instance” subtyping rule. Namely, for types A and B, A is a subtype of B iff A is a “generic instance” of B, meaning A is at least as polymorphic as B. “Higher-rank polymorphism” sounds scarier than it is, too, by the way. It’s basically just a way to pass polymorphic functions as arguments. It’s what you really want any time you think you’re craving a “virtual template” in C++; the typical OOP solution in a language like C# is more convoluted, usually consisting of wrapping the function in a class with a generic method and invoking it through an interface. The intuition is that you can pass a more polymorphic function (like the identity function of type “∀a. a → a”) as an argument to a function expecting a less polymorphic one (like “Int → Int”) and it’ll just be specialised—but you clearly can’t do the reverse because “Int → Int” doesn’t accept all the types that “∀a. a → a” does (like “String → String”, “Char → Char”, “Bool → Bool”, &c.). However, the subtyping gets flipped every time you go to the left of a function arrow, because it’s contravariant. And you only notice this with higher-rank polymorphism because that’s the only place Haskell has a subtyping rule like this. My usual example, stolen from an SPJ paper, is: f ∷ ((∀a. [a] → [a]) → Int) → Int f x = x (drop 1) g ∷ ([Int] → [Int]) → Int g y = sum (y [1, 2, 3]) h ∷ (∀a. a → a) → Int h z = z 5 Or, in pseudo-imperative notation for those not familiar with Haskell: func f(x: (<T> (List<T> => List<T>)) => int): int { return x(list => list.drop(1)); } func g(y: List<int> => List<int>): int { return y([1, 2, 3]).sum(); } func h(z: <T> (T => T)): int { return z(5); } “f g” works because “([Int] → [Int]) → Int” (the type of g) is more polymorphic than “(∀a. [a] → [a]) → Int” (the type of x, the parameter of f), because “[Int] → [Int]” (the type of y, the parameter of g) is less polymorphic than “∀a. [a] → [a]” (the type of the parameter of x). f g f (\ y -> sum (y [1, 2, 3])) (\ y -> sum (y [1, 2, 3])) (drop 1) sum (drop 1 [1, 2, 3]) sum [2, 3] 5 But “f h” is a type error, because “(∀a. a → a) → Int” (the type of h) is less polymorphic than “(∀a. [a] → [a]) → Int” (the type of x), because “∀a. a → a” is more polymorphic than “∀a. [a] → [a]” (the type of the parameter of x). And indeed it’s easy to come up with a type-incorrect implementation as I’ve done here—if you could run it, you’d end up trying to call “drop” on a number instead of a list: f h f (\ z -> z 5) (\ z -> z 5) (drop 1) drop 1 5

coldtea 8y ago
>“Higher-rank polymorphism” sounds scarier than it is, too, by the way Well, there's some irony of writing that after 6 paragraphs filled with obscured Haskellise. (Even though it's just some basic functional stuff in the end, like map, drop, sum etc, they will definitely look alien to anyone uninitiated).
- evincarofautumn 8y ago
  Good point, haha, I did see the irony while writing that. I’ve moved that paragraph up toward the top in the hope it helps somewhat. :P The thing about a lot of these big scary concepts in Haskell is that they’re really simple, the kind of thing where, once it clicks, you go “Oh! That’s all?”, but that doesn’t mean they’re easy—you’ve got to get familiar with the notation and jargon, and spend time building intuition from examples and just trying things out. Nowadays I think of my process of learning new things as “try to realise how simple it is”, i.e. “what do experts understand (or just have memorised) that makes this easy for them?” It’s been a lot more motivating and pleasant than my old tactic of “try to cram this into my head without ‘chewing’ and hope my brain can digest it”.
- willtim 8y ago
  Haskell does make a great semi-formal language with which to communicate functional programming ideas, even if you have no plans to ever use an implementation of it. Mainstream languages are beginning to borrow more and more ideas from it (albeit often with significantly more verbose syntax). Much of the research literature in functional programming also uses Haskell syntax, so IMHO it is worth any developer learning.
- MaxBarraclough 8y ago
  They say you need a PhD to use Haskell. It's not true. I've seen PhD students use it!
  - deleted 8y ago
    [deleted]
  - 8y ago