4 ms·

> a monad is a type constructor Now explain what a "type constructor" is, otherwise these words are worthless.

hikarudo 5y ago
A type constructor is something that takes a type and gives you a new type. 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.
- brundolf 5y ago
  So this is a perfect example of how things could be better-explained to the average developer via analogy: "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.
  - hikarudo 5y ago
    Good point. A generic type is a great example of a type constructor.
- zabzonk 5y ago
  > the pointer operator * Do you mean declarator?, As in: Foo * f; // f is a pointer to a Foo The operator dereferences something - it certainly does not create a new type. And neither does the above - the concept of pointers to addressable types is innate to the C and C++ type systems - if you create a type Foo, you get pointers to Foo for free.
  - hikarudo 5y ago
    You are correct, my mistake.
  - jkhdigital 5y ago
    The fact that pointers to Foo are "free" doesn't invalidate the notion that the * is, in some sense, a semantic extension of whatever Foo is and thus a generic type. I know that this is not literally true in the "theory" of the C programming language and type system, but conceptually it matches up pretty well.
jkhdigital 5y ago
Here's how I like to think about things: 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.
hota_mazi 5y ago
Integer is a type. 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.
thinkharderdev 5y ago
A function that take one type and gives you another type. So (in Java for example) you have a generic type such as List<T>. But that is not a really a type because you can't have a value of the generic type. It is actually a type constructor, you can give it another type (say String) and it will give you a type List<String> which can actually be instantiated to a value. So in the context of programming languages it is just a fancy word for a generic or parametric type.

A type constructor is something that takes a type and gives you a new type. 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.

brundolf 5y ago
So this is a perfect example of how things could be better-explained to the average developer via analogy: "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.
- hikarudo 5y ago
  Good point. A generic type is a great example of a type constructor.
zabzonk 5y ago
> the pointer operator * Do you mean declarator?, As in: Foo * f; // f is a pointer to a Foo The operator dereferences something - it certainly does not create a new type. And neither does the above - the concept of pointers to addressable types is innate to the C and C++ type systems - if you create a type Foo, you get pointers to Foo for free.
- hikarudo 5y ago
  You are correct, my mistake.
- jkhdigital 5y ago
  The fact that pointers to Foo are "free" doesn't invalidate the notion that the * is, in some sense, a semantic extension of whatever Foo is and thus a generic type. I know that this is not literally true in the "theory" of the C programming language and type system, but conceptually it matches up pretty well.

jkhdigital 5y ago

Here's how I like to think about things: 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.

hota_mazi 5y ago

Integer is a type. 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.

thinkharderdev 5y ago

A function that take one type and gives you another type. So (in Java for example) you have a generic type such as List<T>. But that is not a really a type because you can't have a value of the generic type. It is actually a type constructor, you can give it another type (say String) and it will give you a type List<String> which can actually be instantiated to a value. So in the context of programming languages it is just a fancy word for a generic or parametric type.