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.
'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.
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.
What you're calling "lazy mapping a function over a stream" is an example of a functor. To be precise the functor goes from "type a" to "stream of type a" (note that this isn't quite the same as a function since it operates on the level of types).
You don't need to understand Functors to understand how mapping over a stream works, however if you understand mapping over a stream then you can understand any other functor as being similar to mapping over a stream. Now functors are somewhat basic so it's hard to come up with a really nontrivial example, but you could for instance consider:
generate_b = lambda: function_a_to_b(generate_a())
to be pretty much the same thing as mapping over a stream, even though those functions can't be iterated over and could just be generating random data, or sample some time series etc.Note that here we're transforming the output, when you start transforming the input you get something contravariant, like when you do something as follows:
class CoMapped:
# ... #
def __index__(self, a):
return self.object_with_b_index[self.function_a_to_b(a)]
it looks a bit weird to do this in Python though as there's no way to denote types.You don't, for this one example.
You don't, for any one example.
But if you keep looking, you'll find more and more of these examples of functors embedded in the code you are already writing. You need the notion of functor when you want to abstract over all of these examples, or generalize one of your examples to handle things that it couldn't before.
You don't need to understand Functor to understand "map over stream", no. But it turns out that Functor (and to slightly lesser extent Contravariant and Profunctor) keep showing up everywhere. It's not just stream processing, they show up in writing parsers, data structures, DSLs, software transactional memory...
For example, "computation that produces either an error or a result" and "transforming the result IFF the operation was successful" is also captured by Functor. And so is "perform IO and then transform the result of that IO". And "apply this function to all elements in a datastructure".
So, once you 1) realise that all these cases can be generalised to functors and 2) write down what the lawful behaviour if Functor is (i.e. "the spec"), we can suddenly start writing generic code that works for any Functor. So when I make 'Source' a Functor, my users get all the generic code written for any Functor for free.
Similarly Monoid, Applicative, Monad, and all these other abstractions occur all over the place. And you get this positive feedback cycle. We have generic code that works for any type that's an instance, so if we make new types instances of them, we get all this generic code for free. But the more types are instances, the more incentive there is to write even more generic code using these abstractions. Which in turns encourages ever more instances, etc.
So you never need to "understand" the abstractions for any specific instance/operation. It's just that if you have a lot of use-cases described by the same abstraction, recognising that this abstraction captures all these cases lets you get a lot of code reuse. And not only that, but also a powerful toolkit that you can use for working with basically any other library/code you encounter supporting them.
In Haskell Monoid, Functor, Applicative, Monad, and co provide you a toolbox that you end up able to reuse again and again for tons of different libraries all supporting them. These abstractions didn't gain wide-adoption for the sake of "theoretical elegance" (though they are elegant), they gained wide adoption due to the sheer pragmatic benefit they provide when programming.
As an example, Applicative itself was only invented in 2004, I started learning Haskell in 2007 and by that time about 80-90% of libraries in the ecosystem had started using it. You don't get that kinda adoption if you don't have anything to show for it :)
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.
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.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-g...
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.
“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 5Well, 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).
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”.
It's not true. I've seen PhD students use it!
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.