5 ms·

Are there some good examples of problems for which these sorts of programming tools are particularly helpful, or yield a particularly elegant solution, or is th

Are there some good examples of problems for which these sorts of programming tools are particularly helpful, or yield a particularly elegant solution, or is their role more academic?

jayd16 8y ago
I've used covariance and contravariance in C# before. I can't say its particularly elegant because it has the code spell of being too exotic but the alternatives if we did not use the features would have been a lot worse. Simple C# doc page explaining the language feature in less academic and more brass tacks terms: https://docs.microsoft.com/en-us/dotnet/csharp/programming-guide/concepts/covariance-contravariance/ https://docs.microsoft.com/en-us/dotnet/csharp/programming-g...
- willtim 8y ago
  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
- keithnz 8y ago
  I find in C# you use it without thinking about it because it usually makes sense when you have specific things you are trying to do, you often don't think too much about the types. public interface ITalker { string Talk(); } public class Robot : ITalker { public string Talk() => "Beep Boop"; } class Program { static void Main(string[] args) { var robots = new List<Robot>() {new Robot()}; MakeEmTalk(robots); DoStuffWithRobots(MakeEmTalk, robots); } private static void DoStuffWithRobots(Action<List<Robot>> robotoStuff, List<Robot> robots) { robotoStuff(robots); } private static void MakeEmTalk(IEnumerable<ITalker> talkers) { foreach (var talker in talkers) { Console.WriteLine(talker.Talk()); } } } so intuitively, with MakeEmTalk, a list of robots should be able to be used where a enumerable list of talkers is required. conversely ( contraversely? ) with DoStuffWithRobots, an action on a list of robots should be able to use a more generic action that works on an enumerable of Italkers, while we are only dealing with a list of robots there shouldn't be anything that stops us using something designed to work on a broader set of things.
willtim 8y ago
Standardised principled abstractions make for better program composition and better API design. In the Haskell world, APIs are much less adhoc, more consistent and easily understood because of such mathematical abstractions (and the laws they imply, relating operations). Principled abstractions enable many other possibilities too, such as automatic program derivation. In Haskell I do not need to write any code to aggregate nested maps or parse a sudoku board, the compiler knows how to assemble such code automatically from the types.
clhodapp 8y ago
Contravariance, as shown here, is extremely helpful for a working programmer and (like much of strongly typed functional programming) becomes more so as you begin to let go of that type of concern and just learn the stuff. Say you have a JSON encoder that knows how to turn Strings into JSON. You can make an encoder for UUIDs with that encoder and a simple contramap operation. In Scala: // First, summon a String encoder val stringEncoder: Encoder[String] = Encoder[String] // Now contramap val uuidEncoder: Encoder[UUID] = stringEncoder.contramap[UUID](_.toString) Of course, you're free to do this inline so there's not usually so much val-binding involved.
- evincarofautumn 8y ago
  Profunctors are another great example of variance in functional programming. A profunctor is a type constructor that takes two arguments, one contravariant, one covariant. The simplest example of this is the function type constructor (->): you can lmap (contramap) the first type parameter by composing a function before the input, or rmap (fmap) the second type parameter by composing a function after the result: pipe :: A -> B lmap (modifyInput :: A' -> A ) pipe :: A' -> B rmap (modifyOutput :: B -> B') pipe :: A -> B' Profunctors are the class of types that behave like functions or “pipes”—anything that takes input of some type and produces output of another type, which you want to be able to stitch together in a pipeline. In fact I think the only way to have a contravariant type parameter in Haskell is to use it on the left of a function arrow, or not use it at all; all Profunctor instances are wrappers for something function-like.
merijnv 8y ago
Well, one example I like when people ask me "what's contravariant good for?" is the following intuition. Suppose we're doing stream processing. We might have a datatype 'Source a' which is a source that produces a stream of a's. 'Source' is an example of a Functor. We can use 'fmap :: Functor f => (a -> b) -> f a -> f b' as '(a -> b) -> Source a -> Source b'. So, if we a function 'a -> b' we can turn a source of a's into a source of b's. Nice. In such a library we would obviously also want a 'Sink a', this is a datatype that consumes a stream of a's. For example, it might write these a's to disk. Now, clearly it doesn't make sense for 'Sink' to be a functor. Think about it, if we have a sink that writes a's to disk, how would a function 'a -> b' affect it? Sure, we could turn all a's into b's, but then what? We don't know how to do anything with b's. However, 'Sink' is a Contravariant (Functor). So, let's have a look at that. 'contramap :: Contravariant f => (a -> b) -> f b -> f a', so '(a -> b) -> Sink b -> Sink a'. If we have a 'Sink' that writes 'b' to disk and a function that turns a's into b's we can obviously construct a 'Sink a' that consumes a stream of a's, converts them to b's and passes them to the original 'Sink'. And then there's a third abstraction not mentioned in the original post. The 'Profunctor', a Profunctor is a type that has two arguments and is contravariant in the first one, while the second is a regular Functor. In other words, if we have 'Pipe a b' this type can be made a Profunctor which comes with 'dimap :: Profunctor p => (a -> b) -> (c -> d) -> p b c -> p a d', which hopefully looks very similar to both Functor and Contravariant. In our stream processing example 'Pipe a b' would correspond with a pipe that consumes a stream of a's and turns it into a stream of b's which we can use to plumb 'Sink' and 'Source' together. We can both contramap it's first type argument to change what we can feed into it, as well as fmap the second type argument to alter what it produces. These are from the only cases where these classes show up, but I hope they give some relatively easy to follow example on how these classes can capture some common scenario.
- Myrmornis 8y ago
  Thanks for your reply, I'm going to try to read it and the others carefully. I wonder whether it's possible to bridge the gap more for people who are used to more conventional programming paradigms. For example, > 'Source' is an example of a Functor. We can use 'fmap :: Functor f => (a -> b) -> f a -> f b' as '(a -> b) -> Source a -> Source b'. So, if we a function 'a -> b' we can turn a source of a's into a source of b's. Nice. In python that's just itertools.imap(function_a_to_b, stream_of_as) and many other languages will have a similar construction. So I immediately hit a block as I'm struggling to understand why I need the notion of a Functor to understand what in the end looks like just lazy mapping of a function over a stream.
jerf 8y ago
There are some other good replies already, but I really want to highlight that contravariance and covariance are not Haskell concepts; they're programming language concepts. They come up in object-oriented programming languages all the time too, especially once generics get involved. (Understanding the issues around -variance and generics in OO is an important part of the path of understanding why those sets of features aren't a thing you "just" put in a language, and why you end up with some sort of tradeoff in every implementation.) As is often the case, you can muddle through without an explicit understanding of the issues, but you'll be a better programmer (better designs, faster understanding why certain error messages come up, etc... I mean a practically better programmer, not just academically better) if you understand these issues well. Though I will confess that I have a hard time keeping straight which is co- and which is contra- once I step away from the issues for a while. I understand the concepts and their application at a practically-useful level, but I've never loved the naming scheme.
ufo 8y ago
Variance inevitable rears its ugly face when you introduce a subtyping relation to your type system. Variance is most visible in languages that mix parametric polymorphism (generics) with subtyping (for example, OO subclassing) because when this happens you may need to write down explicit variance annotations to appease the type checker. However, variance still matters even without parametric types. For example, it describes what types you can use when overriding a methof in a subclass. The subclass is allowed to be "more general" than the superclass so if you want you can change the input parameters of the method to a more general supertype and you can change the return type to a more specific subtype. The output types are covariant: in the subclass where you create the method you can use a subclass of the return type. The input types are contravariant: in the subclass where you create the method you use a superclass of the input types.

Are there some good examples of problems for which these sorts of programming tools are particularly helpful, or yield a particularly elegant solution, or is their role more academic?

jayd16 8y ago

I've used covariance and contravariance in C# before. I can't say its particularly elegant because it has the code spell of being too exotic but the alternatives if we did not use the features would have been a lot worse. Simple C# doc page explaining the language feature in less academic and more brass tacks terms: https://docs.microsoft.com/en-us/dotnet/csharp/programming-guide/concepts/covariance-contravariance/ https://docs.microsoft.com/en-us/dotnet/csharp/programming-g...

willtim 8y ago
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
keithnz 8y ago
I find in C# you use it without thinking about it because it usually makes sense when you have specific things you are trying to do, you often don't think too much about the types. public interface ITalker { string Talk(); } public class Robot : ITalker { public string Talk() => "Beep Boop"; } class Program { static void Main(string[] args) { var robots = new List<Robot>() {new Robot()}; MakeEmTalk(robots); DoStuffWithRobots(MakeEmTalk, robots); } private static void DoStuffWithRobots(Action<List<Robot>> robotoStuff, List<Robot> robots) { robotoStuff(robots); } private static void MakeEmTalk(IEnumerable<ITalker> talkers) { foreach (var talker in talkers) { Console.WriteLine(talker.Talk()); } } } so intuitively, with MakeEmTalk, a list of robots should be able to be used where a enumerable list of talkers is required. conversely ( contraversely? ) with DoStuffWithRobots, an action on a list of robots should be able to use a more generic action that works on an enumerable of Italkers, while we are only dealing with a list of robots there shouldn't be anything that stops us using something designed to work on a broader set of things.

willtim 8y ago

Standardised principled abstractions make for better program composition and better API design. In the Haskell world, APIs are much less adhoc, more consistent and easily understood because of such mathematical abstractions (and the laws they imply, relating operations). Principled abstractions enable many other possibilities too, such as automatic program derivation. In Haskell I do not need to write any code to aggregate nested maps or parse a sudoku board, the compiler knows how to assemble such code automatically from the types.

clhodapp 8y ago

Contravariance, as shown here, is extremely helpful for a working programmer and (like much of strongly typed functional programming) becomes more so as you begin to let go of that type of concern and just learn the stuff. Say you have a JSON encoder that knows how to turn Strings into JSON. You can make an encoder for UUIDs with that encoder and a simple contramap operation. In Scala: // First, summon a String encoder val stringEncoder: Encoder[String] = Encoder[String] // Now contramap val uuidEncoder: Encoder[UUID] = stringEncoder.contramap[UUID](_.toString) Of course, you're free to do this inline so there's not usually so much val-binding involved.

evincarofautumn 8y ago
Profunctors are another great example of variance in functional programming. A profunctor is a type constructor that takes two arguments, one contravariant, one covariant. The simplest example of this is the function type constructor (->): you can lmap (contramap) the first type parameter by composing a function before the input, or rmap (fmap) the second type parameter by composing a function after the result: pipe :: A -> B lmap (modifyInput :: A' -> A ) pipe :: A' -> B rmap (modifyOutput :: B -> B') pipe :: A -> B' Profunctors are the class of types that behave like functions or “pipes”—anything that takes input of some type and produces output of another type, which you want to be able to stitch together in a pipeline. In fact I think the only way to have a contravariant type parameter in Haskell is to use it on the left of a function arrow, or not use it at all; all Profunctor instances are wrappers for something function-like.

merijnv 8y ago

Well, one example I like when people ask me "what's contravariant good for?" is the following intuition. Suppose we're doing stream processing. We might have a datatype 'Source a' which is a source that produces a stream of a's. 'Source' is an example of a Functor. We can use 'fmap :: Functor f => (a -> b) -> f a -> f b' as '(a -> b) -> Source a -> Source b'. So, if we a function 'a -> b' we can turn a source of a's into a source of b's. Nice. In such a library we would obviously also want a 'Sink a', this is a datatype that consumes a stream of a's. For example, it might write these a's to disk. Now, clearly it doesn't make sense for 'Sink' to be a functor. Think about it, if we have a sink that writes a's to disk, how would a function 'a -> b' affect it? Sure, we could turn all a's into b's, but then what? We don't know how to do anything with b's. However, 'Sink' is a Contravariant (Functor). So, let's have a look at that. 'contramap :: Contravariant f => (a -> b) -> f b -> f a', so '(a -> b) -> Sink b -> Sink a'. If we have a 'Sink' that writes 'b' to disk and a function that turns a's into b's we can obviously construct a 'Sink a' that consumes a stream of a's, converts them to b's and passes them to the original 'Sink'. And then there's a third abstraction not mentioned in the original post. The 'Profunctor', a Profunctor is a type that has two arguments and is contravariant in the first one, while the second is a regular Functor. In other words, if we have 'Pipe a b' this type can be made a Profunctor which comes with 'dimap :: Profunctor p => (a -> b) -> (c -> d) -> p b c -> p a d', which hopefully looks very similar to both Functor and Contravariant. In our stream processing example 'Pipe a b' would correspond with a pipe that consumes a stream of a's and turns it into a stream of b's which we can use to plumb 'Sink' and 'Source' together. We can both contramap it's first type argument to change what we can feed into it, as well as fmap the second type argument to alter what it produces. These are from the only cases where these classes show up, but I hope they give some relatively easy to follow example on how these classes can capture some common scenario.

Myrmornis 8y ago
Thanks for your reply, I'm going to try to read it and the others carefully. I wonder whether it's possible to bridge the gap more for people who are used to more conventional programming paradigms. For example, > 'Source' is an example of a Functor. We can use 'fmap :: Functor f => (a -> b) -> f a -> f b' as '(a -> b) -> Source a -> Source b'. So, if we a function 'a -> b' we can turn a source of a's into a source of b's. Nice. In python that's just itertools.imap(function_a_to_b, stream_of_as) and many other languages will have a similar construction. So I immediately hit a block as I'm struggling to understand why I need the notion of a Functor to understand what in the end looks like just lazy mapping of a function over a stream.

jerf 8y ago

There are some other good replies already, but I really want to highlight that contravariance and covariance are not Haskell concepts; they're programming language concepts. They come up in object-oriented programming languages all the time too, especially once generics get involved. (Understanding the issues around -variance and generics in OO is an important part of the path of understanding why those sets of features aren't a thing you "just" put in a language, and why you end up with some sort of tradeoff in every implementation.) As is often the case, you can muddle through without an explicit understanding of the issues, but you'll be a better programmer (better designs, faster understanding why certain error messages come up, etc... I mean a practically better programmer, not just academically better) if you understand these issues well. Though I will confess that I have a hard time keeping straight which is co- and which is contra- once I step away from the issues for a while. I understand the concepts and their application at a practically-useful level, but I've never loved the naming scheme.

ufo 8y ago

Variance inevitable rears its ugly face when you introduce a subtyping relation to your type system. Variance is most visible in languages that mix parametric polymorphism (generics) with subtyping (for example, OO subclassing) because when this happens you may need to write down explicit variance annotations to appease the type checker. However, variance still matters even without parametric types. For example, it describes what types you can use when overriding a methof in a subclass. The subclass is allowed to be "more general" than the superclass so if you want you can change the input parameters of the method to a more general supertype and you can change the return type to a more specific subtype. The output types are covariant: in the subclass where you create the method you can use a subclass of the return type. The input types are contravariant: in the subclass where you create the method you use a superclass of the input types.