Now explain what a "type constructor" is, otherwise these words are worthless.
For example, in C, if you have any type Foo, the pointer operator * will give you a new type Foo*.
Another example: in Haskell, Maybe is a type constructor, since it takes a type parameter a (Maybe a). So 'Maybe' is a type constructor, but 'Maybe Int' is a type.
So a type constructor is like a function, but it operates on types, not on values.
"You can think of a type constructor like a generic type, particularly the way those work in languages like TypeScript"
Edit: The C example was added after my initial comment, and is better than nothing, though I'd tend to say the pointer example is a bit of a weird one to go with. Of course intuitiveness is relative and I'm not saying an example has to mention TypeScript or whatever to be valid. But I do think, like, C++ templates would be a somewhat clearer comparison to make for that audience.
Do you mean declarator?, As in:
Foo * f; // f is a pointer to a Foo
List<Integer> is a type.
List<T> is a type constructor.
In order to get a real type from a type constructor, you need to "pass it type parameters". In the example above, you need to say that T is Integer.
Values are things. Concrete. Since we are manipulating computers, a value is really just some abstract symbols--1s and 0s occupying a slot in memory. The meaning of the symbols exists on a higher level, what we usually call semantics.
Types are a well-studied method to attach semantics to blocks of otherwise meaningless (but concrete!) symbols. By declaring a variable (which is just a pointer to a memory block containing arbitrary symbols) is of type Int, we are establishing that in the context of the program, the symbols occupying that memory block are to be interpreted as the encoding of an integer.
Functions are transformations of values. They manipulate concrete things to produce other concrete things. By specifying the input and output types, we ensure that the transformations applied by our functions are only used on the right kinds of things, and we also know what kind of thing we will get out of the function. Mind you, these things are still all just arbitrary symbols in blocks of memory, but now we know how to semantically interpret them based on the function's specification.
Type constructors are also transformations, but of types. That is, we use type constructors to modify or enhance the semantics of a basic type. Functors are essentially type constructors that extend function semantics as well: if F<-> is a functor, then you can "lift" any function from type A to type B into a function from type F<A> to type F<B>. (Note that I'm using the commonly recognized "generic type" angle bracket notation to deliberately avoid the confusion of Haskell's pedantically minimalist syntax.)
I think this description provides a much more intuitive path to the understanding of, say, a list as a functor. A "list" is a generic structure that can be applied to any semantics, evident in the phrase "list of X". The preposition "of" makes it clear that this is a semantic extension of whatever kind of thing that X is. Furthermore, there is an obvious way to lift functions: just apply the function to each element of the list, and collect the results in a list. Bam! There's a functor. This is starting to feel like blog post territory, but I'll forge ahead...
An important point here is that the "semantic structure" that type constructors add to a basic type has to come from some extra data that is used when defining the type constructor. In the case of functors, we have to actually describe an algorithm that implements the lifted function in terms of its basic version (as we just did for lists).
So a monoid is also a type constructor, and it must come along with a description of the monoidal product: For type M<A>, we need to describe a function (the monoidal product) which takes two A's and returns another A. We must also identify a specific value within type A that serves as the identity element. Now, to actually be a monoid, the monoidal product and identity element must satisfy some laws, but in general proving the laws are satisfied by a given constructor is outside of the capabilities of our type syntax. This is a step up from the functor type constructor, which needs only a valid implementation of the lifting function (called `fmap` in Haskell) in order to establish that we have actually created a functor.
In any case, to arrive at monads we don't actually combine the functor and monoid type constructors; instead we gently introduce monoid semantics on top of a functor. We do so by making the functor type constructor itself act like a monoidal product, so that repeated applications of the type constructor don't create "nested" versions of the semantics, they just stop at the first level instead. Lists are again a very straightforward example of this: List<A> is a list of things of type A, and List<List<A>> is a list of lists of As, and there is an obvious way to bring the list of lists back down to just a list: flatten it.
...okay maybe I'll stop there, at least for now.
I really appreciate this. I know the Haskell syntax kindasorta, but my brain just doesn't grok it well. Vs anything along the lines of Generic[Type] or Generic<Type> is just far more familiar for most audiences, myself included.
The people whom Haskell type syntax makes sense for are largely not the ones trying to learn this stuff.
> So a monoid is also a type constructor
Is it? You claimed correctly a couple paragraphs back that a functor is a type constructor F bundled with the ability to "lift" functions into the context of F. So `List` is a functor in the usual way, and so on. But a monoid cannot be a type constructor, or else `String` could not be a monoid. A monoid is a concrete type M bundled with multiplication and unit on that type.
I would say "sigh", but you have to say what you mean.
A functor is a PAIR, please notice the emphasis, of a type constructor F and a map function with the following signature: a -> b -> f a -> f b.
Its not a type constructor, it's a pair of two things, the type constructor AND its map function.
Now that we said what it is we provide the usual simple example of Array, Record or Option, show the type constructors and show how we map them.
Is it really so hard to grasp starting from definitions rather than examples and contrived blogs?
I wish people understood that fp is much easier to understand by reading definitions.
The real landscape of its adoption begs to differ. For the great majority of people, examples and analogies are fantastically more efficient for communicating ideas than building up from first principles. You get to re-use existing mental machinery, intuition, etc, until enough experience has been gained to refine it.
which covers basically all the fundamentals to be proficient in functional programming that has definitions that are opaque and unapproachable. And all of those have very simple examples, both in real life and especially programming. But definition has to come first, or you have this great mass of people that do not understand what they talking about even when they blog about it.
If you can take your time to understand that a type constructor (and take the time to see what it is) and a map function form a pair called functor, you are equipped to learn about monads.
It's not rocket science, but yes, it requires a bit of studying and learning, which is what people don't want to hear, and instead choose the long road of contrived example-driven, inaccurate and confusing blog posts.
(a -> b) -> F a -> F b; the parentheses are critical. I don't fully disagree with your point, but if you're going to emphasize rigor and definitions, it would be wise to make sure you're not setting people on the fence up for mistakes akin to those in the original post.
(You also called it `F` and then used it as `f`.)
The equivalent signature in Java (if we could abstract over type functions) would be:
interface Functor<F<_>> {
<A, B> Function<F<A>, F<B>> map(Function<A, B> f);
}
I wish more FP writers understood that not everyone has the same neurotype, and "easier to understand by reading definitions" is far from a universal statement.
So why can't we just call the damn things 'Type constructors'?
So basically it is just a parametric type such as List<T> which has a type constructor so you can get a concrete type (eg List<String>), a map function which takes a function f: A => B and and turns it into a function List<A> => List<B>, and a "flatten" function with will turn a List<List<A>> into a List<A>.
The last part is what allows "flatMap" which takes a function f: A => List<B> and turns it into a function List<A> => List<B> and is really just a shorthand for doing map and then flatten.
Unfortunately, due to abuse of notation, the type constructor isn't given much focus. But it's true that "type constructor" is the first conceptual hurdle.
The List functor is a combination of the type function sending `T` to `List<T>` and the ... what do you want me to call it, a function function? implemented in Java as:
static <T, S> Function<List<T>, List<S>> map(Function<T, S> f) {
return (ts) -> {
var ss = new ArrayList<S>();
for (final var t : ts) ss.add(f.apply(t));
return ss;
};
}
But it's not the `map` method that's the important part, so much as the idea that we can (or want to; can't in Java) pass `List` to any function that needs a Functor, which can then use whatever `map` implementation that functor has, without knowing what actual type function it was given.
Really, I suspect it's neither the type constructor nor the map function that's the conceptual hurdle. It's abstracting over the type constructor; taking a type constructor as a parameter. You may have never used a language that supports that, or seen a need for it, and this may all seem like needless sophistry until you do.
- 5 is a value. Its type is int
- int is a type
- T is a type parameter. Like the x in "f(x)", we have to pass one in to evaluate it
- List<T> is a type constructor. It takes a type, T, and spits out a new, "compound" type. It will "contain" T's.
- [3,5,7] is a list. Its type is List<int>. We fed the type "int" to List<T> to construct a new type
- List<T> is a functor because it "contains" T's. List<int> "contains" ints.
- F<T> -> () (a function which takes a T and returns nothing) is a type constructor. It's not really a functor. There's ways in which it technically can be (e.g. decorators in python) but for the sake of pedagogy and giving a counterexample, I'm going to say it's not, because you usually aren't going to map over something like that.
- because functors "contain" other values, you can apply a function to the contents, without changing the container context. This is called map. It may change types, eg mapping sqrt over a list of ints could give floats. But it always gives the same "container type"
The tricky bits:
- To be a true blue functor, there has to exist an identity function that is a no-op and gives you the same types and values back. You needn't define it, it just has to be possible to define.
- functors need not actually "contain" anything, nor the contained value be primitive data. But they always have this wrapper-like feel to them, with an outer type, an inner type, some context/data/value/computation, and the ability to map over that inner value. E.g. Optional<T> could contain nothing, but you can still map over it.
- it's not necessary to be able to dereference or "dispense" the contained value. Sometimes, like the IO monad pattern, the inner value gets "stuck". it never leaves the IO, it's only ever (flat)mapped over.
- the inner value can be: nothing, a single datum, a collection of data, a function, a computation, another functor, another type constructor...almost anything you could assign to a variable.
- well-known functors include: List<T>, Dict<K,V>, Optional<T>, Result<T,E>, Future<T>, Generator<T>, IO<T>, Tree<T>. T* (pointer to a T). Virtually all container types.
Hope that helps
- List<T> is a functor because it "contains" T's. List<int> "contains" ints.
Is really correct. I believe a `Container<T>` becomes a functor only if it also 'has' (can have?) a function that can take a function and apply it to all values in the 'container'. So, a 'map' of some sort.
I mean, I see your explanation of 'map' later on. It's also probably true that in real world software engineering contexts any 'container type' of that kind would also be one that either has or can naturally have a `map'. It's just that if someone willing to understand this read your comment and went: "Aha! Some container thing is a functor because it contains things!" I think they'd gain incorrect understanding.
Not that I'm an FP guru, so..
If you have two sources and you want to combine them into a single source, you need an Applicative Functor, also known as a monoidal functor.
If you have a source that itself produces sources, and you want to flatten the nesting and treat it as a single-level source, you need a Monad.
> F<T> -> () (a function which takes a T and returns nothing) is a type constructor. It's not really a functor.
I'm having a little trouble matching the prose against the type signature. A function which takes a T and returns nothing would have type `T -> ()`; no F in sight. I'm guessing you meant that F<T> is defined to give `T -> ()`, in which case F is indeed not a functor; it's a contrafunctor, a place to which Ts can be sent (not retrieved).
Class<List<String>> thisistypeconstructor(Class<String> strClass)
And if I generify the types above, maybe something like
<OutputType> thisistypeconstructor(<InputType>)
So, to make this absolutely clear, a monad is a type constructor in functional programming. This is why I personally prefer the more “creative” explanations of monads, because they attempt to explain what the monad is doing to the original type: adding context, or the possibility of a null value, or multiple values, or a probability distribution over values, etc.