3 ms·

>Functors are type constructors So why can't we just call the damn things 'Type constructors'?

by 6nf 5y ago

catgary 5y ago
Not every type constructor is a functor.
- 6nf 5y ago
 What makes a type constructor a functor, what's the difference
 - Twisol 5y ago
 In particular, a functor is a type constructor F together with a higher-order function deriving transformations `F T -> F S` given a transformation `T -> S`, subject to some semantic requirements. This is the `map` or `fmap` people refer to as defining the functor. 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.
 - 6nf 5y ago
 See this is exactly the point where FP fans lose the rest of us.
 - catgary 5y ago
 It’s a type constructor that extends to functions. It’s a functor.
 - Twisol 5y ago
 You asked. I'm happy to dissect it to your level, but I don't know what you may be familiar with, and if you're not comfortable with type functions, I'm going to have a hard time motivating the extra bits a functor has. 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; }; } We call it as map(f).apply(ts). If we want to pass them both at once, we can rewrite the function so that it's not static, but it doesn't much change that it's a mapping operation. 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.
 - catgary 5y ago
 Type constructor that lifts to functions is even a pretty intuitive (ahistorical) intuition for “functor”.
 - lupire 5y ago
 in OO langauage: Collection is a class, but not every class is Collection.
 - lmm 5y ago
 A functor is a type constructor with a map operation (that obeys composition and identity), similar to how a group is a set with an operation. (And similarly, we casually talk about the type as though it were the functor, just as we talk about the set as though it were the group; if someone says "the Option functor" that's a slight abuse of notation in the same way as "the group of integers").
 - kortex 5y ago
 I might get flack from the FP purist crowd, but I like to think of functors as containers + context. - 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
 - Twisol 5y ago
 I have pretty much the same intuition, except I think of functors not just as containers, but as sources of T. If you have a source of Ts, you can adapt it with a function from T to S to get a source of Ss. If you want to apply a pipeline of type-changing operations to some source of initially Ts, a functor is the right metaphor. (And if you have a sink instead of a source, that's a contrafunctor.) 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).
- deleted 5y ago
 [deleted]
thinkharderdev 5y ago
A functor has three things: 1. A type constructor 2. A "map" function 3. A "flatten" function 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, 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 and turns it into a function List<A> => List and is really just a shorthand for doing map and then flatten.

>Functors are type constructors So why can't we just call the damn things 'Type constructors'?

by 6nf 5y ago

>Functors are type constructors So why can't we just call the damn things 'Type constructors'?

catgary 5y ago

Not every type constructor is a functor.

6nf 5y ago
What makes a type constructor a functor, what's the difference
- Twisol 5y ago
 In particular, a functor is a type constructor F together with a higher-order function deriving transformations `F T -> F S` given a transformation `T -> S`, subject to some semantic requirements. This is the `map` or `fmap` people refer to as defining the functor. 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.
 - 6nf 5y ago
 See this is exactly the point where FP fans lose the rest of us.
 - catgary 5y ago
 It’s a type constructor that extends to functions. It’s a functor.
 - Twisol 5y ago
 You asked. I'm happy to dissect it to your level, but I don't know what you may be familiar with, and if you're not comfortable with type functions, I'm going to have a hard time motivating the extra bits a functor has. 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; }; } We call it as map(f).apply(ts). If we want to pass them both at once, we can rewrite the function so that it's not static, but it doesn't much change that it's a mapping operation. 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.
 - catgary 5y ago
 Type constructor that lifts to functions is even a pretty intuitive (ahistorical) intuition for “functor”.
- lupire 5y ago
 in OO langauage: Collection is a class, but not every class is Collection.
- lmm 5y ago
 A functor is a type constructor with a map operation (that obeys composition and identity), similar to how a group is a set with an operation. (And similarly, we casually talk about the type as though it were the functor, just as we talk about the set as though it were the group; if someone says "the Option functor" that's a slight abuse of notation in the same way as "the group of integers").
- kortex 5y ago
 I might get flack from the FP purist crowd, but I like to think of functors as containers + context. - 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
 - Twisol 5y ago
 I have pretty much the same intuition, except I think of functors not just as containers, but as sources of T. If you have a source of Ts, you can adapt it with a function from T to S to get a source of Ss. If you want to apply a pipeline of type-changing operations to some source of initially Ts, a functor is the right metaphor. (And if you have a sink instead of a source, that's a contrafunctor.) 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).
deleted 5y ago
[deleted]

thinkharderdev 5y ago

A functor has three things: 1. A type constructor 2. A "map" function 3. A "flatten" function 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, 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 and turns it into a function List<A> => List and is really just a shorthand for doing map and then flatten.