Wow, I knew the stuff from previous lectures from my countless attempts to penetrate into category theory. But this one moved my understanding and intuitions further. Bartosz, your explanations are priceless, I wish I could give this video series 10 likes. Thank you!
Is the identity preservation condition needed for the definition of functors? Because it seems like it is already included in the composition condition. Consider two objects a, b with a morphism f :: a -> b Category C dictates that f ° id (at a) = f So then, using Functor F from C to D, in category D, f will be mapped to Ff, id (at a) will be mapped to F(id at a) Due to composition, mapping f ° id (at a) will give us F(f ° id (at a)) = Ff ° F(id at a) But since f ° id (at a) = f F(f ° id (at a)) = Ff Therefore Ff ° F(id at a) = Ff Which implies that F(id at a) has to be an id at Fa Same argument works for left identity. Is that correct, or did I make an incorrect assumption anywhere?
@@BartoszMilewski now that I think about it you're correct. A counterexample is maybe C being a category of just one object a with identity and another morphism. A bad Functor can map them both to a morphism f in category D that is idempotent (i.e. a morphism f :: a -> a such that f ° f = f) and so composition laws are satisfied. But then the homset of Fa -> Fa could include other morphisms that didn't come from C (i.e. F is not Full). Then, one of those new morphisms g won't necessarily follow the equation g ° f = g or f ° g = g And so the identity rules are needed. Thank you for the reply, and for the interesting thought exercise!
From your example of the endofunctor "Maybe" in Haskell, it seems clear that when one goes into details, a functor F: C ->D is defined by two maps with distinct signatures : a first one F_obj acting on objects and a second one F_arr acting on arrows. But that is OK, in math, to just use "F" notation for both maps ; the same way, "o" denotes both the composition of arrows of C and D, even if their laws are different in general. Am I correct ? Regarding foundation aspect, with is not your goal with your course (and that is fine !), I am wondering if the two maps needed for defining a given functor F: C ->D can be formalized by just using the vocabulary of category. I mean a "map" is not an "arrow", generally speaking. So, is set theory or type theory is needed for defining the "map" concept, itself required for defining the concept of "functor" ? Unless of some implicit embedding of both C and D in a shared category, says E, as a strict union of C and D, so that a "map" between objects(C) onto objects(D) can be "encoded" with some arrows of E (that are neither the arrows of C and D, of course) ; also the hom-sets of objects of C and D, have to embeded somehow. Could you give me some hints ?
Tricky question! These mappings are well defined if objects and morphisms in a category form sets--then they are just functions between sets. If they don't form sets then we hit the size problem and there are several options: Use classes instead of sets, use universes, consider enriched categories, work in a 2-category of categories...
@@DrBartosz , I just want to say that the term "functor" contradicts the term "category". A category is a set of elements without a structure, and a functor is a morphism between elements with a given structure (categories). Perhaps the functor is just a morphism between morphisms? Thus the term "endofunctor" becomes less meaningless.
@@ne4to777 Yes, but you can look at Cat as if categories (its objects) had no structure and only functors (with their composition table) existed. It's the same with Set. The question is, where do you get your composition table from? You peek under the hood, either into individual categories, to see how functors compose; or individual sets, to see how functions compose.
@Bartosz Milewski , ok, if а functor is a morphism between objects and morphisms, why does "fmap:: (а -> b) -> (F a -> F b)" only accepts functions as arguments? where are the objects? I expect something like that "fmap:: а -> F a" too.
@@ne4to777 The mapping between objects is the type constructor. It takes type a and produces type F a. In general a is in a different category that F a, so there can't be a morphism between them. What may be confusing is that fmap looks like a _morphism_ between morphisms. It really isn't: it's a function. That's because morphisms in both source and target category form sets, and you can have functions between sets. So fmap is really (a -morphism-in-C-> b) -function-between-sets-> (F a -morphism-in-D-> F b). Each arrow means something different.
When you mention the case where a category "collapses" to a single object c, why are all morphisms collapsed in the identity morphism? Can't there be more than one morphism from c to c, different than id_c?
On the (fmap f Nothing = ?) business, am I correct in thinking that (fmap id Nothing = Nothing) regardless of the type (in this case we have a->a)? Otherwise it violates the preservation of identity, right?
51:51 I think it will be a functor indeed. F id_a ° F f = F f ° F id_a = F f always because all morphisms return nothing now, therefore F id_a = id_[F a] . Also (F g ° F f)° F h = F g °(F f ° F h) for the same reason, as well as F (g ° f) = F g ° F f. Then, It is basically a functor.
The last step, "therefore F id_a = id_[F a]", does not follow. All mapped morphisms return Nothing, but id_[F a] is not a mapped morphism. In particular, id (Just True) = Just True (where id :: Maybe Bool -> Maybe Bool), but fmap id (Just True) = Nothing (where id :: Bool -> Bool), so the fmap version that always returns Nothing does not map identity morphisms to identity morphisms.
If we didn't define functors to preserve id, but just composition, we actually can recover the preservation of identity when the functor is "surjective," and every object/arrow in D is in the image of functor F. Let a' be an object in D, where F a = a'. Let f' : a' -> b', g' : b' -> a be arbitrary arrows out of and in to a, where F b = b', F f = f' and F g = g'. Then we have f' . F id_a = F f . F id_a = F (f . id_a) = F f = f', and F id_a . g' = F id_a . F g = F (id_a . g) = F g = g' so F id_a is a left and right identity for morphisms into and out of a. Question: What if F doesn't actually "hit" everything in D -- is there any way to recover the identity to identity aspect of F? I mean if you're only looking at objects and arrows in the image of F, then F id always *looks* like the identity map, but I think one could construct a "functoid" (it's what I'm calling Functors without the identity to identity property) that is *not* a functor, right?
16:43 So a category with no arrows other than identities can be thought of as representing a set of certain size, because due to the total lack of arrows, there is no structure, and that's what we take as the essence of "set". Such a category is called discrete. Ok, now I was wondering how to turn that around: what about a category with, say, exactly 1 arrow from every object to any other (different) object, plus of course identities. That should be possible, right? At 17:41 you said that any non-discrete category, by definition, has structure. But look, the category I just described is also lacking structure in a sense, since how (ie: why) would you pick any object wrt the others? Every object is, eg both initial and terminal (correct?). Likewise for any pair of objects, what would possibly make it different from any other pair, and so on. What would such a category represent? Again said set? Since you did not mention it, I am quite unsure whether I missed something here... However, this idea of putting arrows where there haven't been ones, and taking away all that have been there (except for identities), feels so much like the "reversing the arrows" move ("dualizing" it's called I think), doesn't it...?
p.s.: I am aware of compositions. But I can't see a problem coming from that wrt to the construction of the category I described; it's just that a lot of paths are identified. However, then I wondered how many different morphisms there would actually be then... Could this be related to the rerpresentation of a power set?
Neither one is actually "lacking" structure, both just have very trivial structures, corresponding to two extremes, at one end where everything in the structure is disconnected from everything else, and at the other extreme where everything in the structure is connected to everything else, so it's "more similar" (in the sense of topology) to a single object than it is to the discrete category of the same number of objects (in the very precise sense that if you have a functor from one of these "arrow-complement" categories to the discrete category, then it must map every object in the arrow-complement category to a single object in the discrete category in order to preserve connectivity). With respect to the "duality" thing, there might be infinite spectrums of possibilities for ways to add arrows to the empty hom-sets, so I'm not sure it can really be called a "dual", unless you have a way to do it that is somehow "the best" out of all other candidates (in the same sense that initial & terminal objects are "the best" out of all other candidates), like for example if you define some larger category that contains the first category plus additional arrows, and then you can take the complement, though you have to work out some coherence issues, like for example no arrows in the complement can compose to arrows in the original category, etc...
I agree with @Bob Davis the structure of such a category would be in some sense trivial. As an example, consider a set (the elements are the objects of the category) with an equivalence relation (there's an arrow between a and b if a is in relation with b). Every equivalence class will look like the category you described, so if this set has only one equivalence class (maybe the relation is "a and b are in the same set") you will get exactly your category. But I wouldn't say that it has no structure, I would say that it has too much structure, at the point that basically everything can be identified. Hope this is interesting, even if four years are passed.
For me a Functor is like a box. A box around Elements and Functions between them. Just like when you order a tennis bat or a book over the internet it comes wrapped in a box and looks like something else but when you look inside the box the articles are in there. EDIT: could you write a Functor even in Typescript like this: type Func = (a: T) => T const compose = (f: Func) => (g: Func) => (x: T) => f(g(x)) type MaybeFunctor = (f: (y: T) => T) => (y: T | undefined) => T | undefined const fmapMaybe: MaybeFunctor = (f) => (y) => y === undefined ? y : f(y) type NumberFunc = Func const addOne: NumberFunc = x => x + 1 const idNumber: NumberFunc = x => x const multiplyByTwo: NumberFunc = x => x * 2 const mappedId = fmapMaybe(idNumber) const mappedAddOne = fmapMaybe(addOne) const mappedMultiplyByTwo = fmapMaybe(multiplyByTwo) const mappedComposition = fmapMaybe(compose(addOne)(multiplyByTwo)) const composedMappedFuncs = compose(mappedAddOne)(mappedMultiplyByTwo) console.assert(mappedId(1) === 1) console.assert(mappedId(undefined) === undefined) console.assert(mappedAddOne(1) === 2) console.assert(mappedAddOne(undefined) === undefined) console.assert(mappedComposition(1) === composedMappedFuncs(1)) console.assert(mappedComposition(undefined) === composedMappedFuncs(undefined))
Quick question, if I have a category with 2 objects and 2 morphisms (just the ID morphisms), so as simple as a 2-object category can be, and I had another singleton category (1 object, 1 morphism), if I had a Functor map both of the objects from the 2-category to the single in the 1-category, then this is a valid Functor because it keeps structure, but it is not faithful. If I reverse it and have a Functor map the the single object from the 1-category to one of the objects in the 2-category, this is a valid Functor again because it keeps structure but it is not full. Anyone can confirm that this is correct?
But in my 2-category I had 2 hom-sets, a->a (identity) and b->b (another identity), and I mapped both of these to my 1-category, so both of these hom-sets became the same hom-set in the 1 category right? Now they are both c->c (identity) in the one category. Isn't that non-injective. I wouldn't be able to go the other way because how do I know if c->c in my 1-category represents a->a or b->b in my 2-category. Just when I think Im understanding things... Thanks Bartosz, you really are the best :D
You have to consider every hom-set separately. Remember, a functor is a mapping of objects plus a bunch of functions on hom-sets. It's those functions that you are concerned with. Is each of them injective? Surjective? In your case, each of them maps a singleton set to a singleton set and is, in fact, an isomorphism.
So I guess I have to think about it from a "programmer" perspective to try and make sense of this. A functor is a type-constructor (like `maybe` for instance), it maps types->types. So continuing thinking about the 2-category and the 1-category (my category here is the usual programming one, objects:types, morphisms:functions) which only have identities, that means we have 2 types (in the 2-category) and each type has only a single function on it, the identity. Then I can "lift" them into this 3rd type (from 2-category to 1-category), I can do EVERYTHING (every function) that I could with them in the 2-category, and so I haven't lost any structure! The mapping from my 2-category to my 1-category essentially acts as a valid "container" (yes I watched your next lecture). I think this makes sense :) Here is the natural next question though, and probably the last question in this line of questioning (and then the interrogation is over), continuing in this "programmer-thinking" way, let's pretend that the types in my 2-category were "int" and "float", and because we only have identities, all I can do is 5->5 or 3.2 -> 3.2, and let's say my type in my 1-category is a boolean, where I follow the same identities, true->true and false->false. Let's focus on the functor from "int" -> "bool", let's say all I do is whatever "int" you give me, I just make it "true". The structure will be preserved. If you had the "int" 5, and called identity twice, you end up with the same thing, the "int" 5. If you put it in this container, and call the identity twice, you also end up with the same thing, so I do see that we preserve the structure. BUT that being said, I can't take the "int" from my container!! I don't know which integer you gave me, so while this functor is both faithful and full, it doesn't mean that given a container I can tell you what value is inside the container! It begins to sounds a bit weird to use the word container in this case! QUESTION: So is it true that even if a functor is both faithful and full, it isn't mandatory that given a "container" I can tell you what value is inside the container? I CAN keep working with this container the SAME way you work with the original type, I support all the same operations of the same structure, but it isn't guaranteed that when you're done the 10 operations you wanted on the container you can say: "well tell me the value now please"! LAST NOTE: I reckon in programming, there are few use-cases like this, if we look at `maybe` for instance, if you give me `Just 10` I know it maps to 10, but this IS NOT because it is faithful and full, this is an additional restriction saying we want to be able to open the container and see what's inside (because this is useful, often when we are done working with the context, we want to see what we actually got). I hope you read this Bartosz :) I'm hoping I'm finally on the right track, and again a HUGE thank you for being so responsive and helpful, I really appreciate it, who would've known my favourite professor wouldn't even be at my university :D
A functor is a category (or a data type in computer languages) mappable from another category, on condition 1) that the identity element in the home category (or in the source type) maps into the identity element in the target category (or type), 2) that any two elements that compose together into a third in the source category (or type), map into into two elements that compose together into a third in the target category (or type) such as that the aforementioned third element in the source category always maps into it. The Haskell language (or any programming language by the way that implements the concept) should use in priority the less arcane name "mappable" (like equatable, comparable and numerable) not to lose behind too many potential users. A list of integers is a mappable type from integers, as well as an optional integer, as well as any user-defined supertype over the integers such as the fractions. The name "functor" could be used as an alias. Haskell shouldn't need a guru to be taught (actually it is an easier language than most others especially for people who don't like programming that much), though once easily learned it could then be useful to a guru and to disciples discussing general philosophy. In the same way monads should be called flowable as they are are meant to follow each other as in a flow subject to extra-functional accidents. The operation bind should be called flow into. A >= A should be called flow f into A.
Would it also make sense to model a set as a category where every object had a unique morphism to every other object? Since every element of a set is related to every other element by their being included in the same set. Would this make any difference, or is it just a convention to say that a set is best modelled as a set with only identity morphisms?
What you're describing is a thin category (a poset) in which all object are isomorphic. That's very different than a discrete category. You want a model for a set to be the simplest category. One way to think about it is that, in any category, morphisms between any two objects form a set -- a hom-set. You can look at this hom-set as a discrete category, and that doesn't add anything to the picture. But if you model a hom-set as a poset with isomorphisms, than you have a non-trivial enriched category. In that category all morphisms between two objects would be equal up to isomorphism. So you'd get an interesting generalization of a thin category.
Although it's understandable, but the mathematical and the Haskell notion of functor looks quite different: in the mathematical definition a functor is an operation defined on arrows and objects, and it looked like arrows and objects are different (can an arrow be an object in the same category?). Later there was a separate Maybe oparator that worked on objects, and fmap that worked on arrows, but if the same arrow (function) is used on the Maybe operator, in that case it's used as an object. To put it shorter it looks like Maybe f is not the same as fmap f, and f is both an arrow and an object at the same time. Anyways, I love the lectures, thanks very much for doing them! After watching more of the videos, it seems like fmap is not the functor itself, but it takes the function object and executes the functor on the arrow that belongs to that function object. Of course fmap is not a function either, just a function object as well, so it makes things a little bit tricky to explain it well why a different fmap is needed when you already have the Maybe functor.
In the lecture on function objects I explain how arrows can also be objects. It's a very important property in any language that supports functional programming.
in Haskell, there exists by default a global category defined in the language called Hask. all functors are, as it was mentioend by Bartosz, endofunctors. so all instances of Functor map from Hask to Hask. in this case, Just defines an operator which transform any object of type a in Hask into an object of type `Maybe a` in Hask, and Functor Maybe turns any morphisms in Hask into `Maybe a -> Maybe b`. in this sense, you can indeed view Functor in haskell like a methematical functor.
I don't think the example about using Just 0 for fmap is correct. If I have f :: a -> Int and g :: Int -> b; fmap (g . f) doesn't equal to (fmap g) . (fmap f) anymore as with the former you can get Nothing but with later not (as it's filtered away in fmap f). This breaks the composition rule required of Functor.
If for all, f :: a -> Int you have fmap defined as: (fmap f) :: F(a) -> F(Int) (fmap f) Nothing = Just(0) (fmap f) Just(x) = Just(f x) then for all g :: Int -> b, define fmap as: (fmap g) :: F(Int) -> F(b) (fmap g) Nothing = Nothing (fmap g) Just(0) = Nothing (fmap g) Just (S x) = g(S x) then it should work out.
The composition rule states that functor need to map from Maybe a to Maybe b. And I think that is satisfied even if the value 'Nothing' is filtered away.
A simpler way of "breaking" it, is to notice that fmap (id :: a->a) is not equal to id :: (Maybe a -> Maybe a) In the case where type a is Int, fmap (id :: Int -> Int) Nothing == Just 0 which is different to (id :: Maybe Int -> Maybe Int) Nothing == Nothing
Hey, I just Uploaded a time lapse of Making of a Program in Python which gives me covid-19 stats of any country! I hope you will love it!.. It's my first !
