What would be a good example of an endofunctor that is not the identity functor?

Question

In Professor Frisby Introduces Composable Functional JavaScript the identity functor was introduced:

const Box = x => 
   ({ 
       map:  f => Box(f(x)),
       fold: f => f(x)           // for testing
   })

I spent the better part of the day understanding functors and why the above JavaScript code is actually the identity functor. So I thought I would alter it to get a "real" functor that is not the identity functor. I came up with this:

const Endo = x =>
   ({ 
       map:  f => Endo(f(x).split('')),
       fold: f => f(x).split('') // for testing
   })

My reasoning is that with Box, Id_Box: Box -> Box and Id_Box f = f. Endo would also map to itself but Endo(f): Endo(x) -> Endo(y) (if f: x -> y).

Am I on the right track?

EDIT: Replaced string with the more generic x as it was in the original examples.

At this point I just would like to know if I understood the theory correctly and how it would translate to JavaScript. To be honest, I'm not even sure if `Endo` would have any practical use at all, because `split()` could be just put in the chain like `Box("cakeisalie").map(s => s.trim()).map(s => s.split(''))` — toraritte, Jul 17 '17 at 04:44
I don't think your `Endo` even is a valid functor, as it only works with functions `f` that create a string from an array. A Functor needs to work with functions of any type. — Bergi, Jul 17 '17 at 05:15
Have you encountered any other functors on your journey to understand what functors are? If not, I'd suggest you just move on with the lecture, it sounded like Prof. Frisby would introduce more functors in the next sessions. — Bergi, Jul 17 '17 at 05:30
In the context of programming the term endofunctor just describes a functor of type `(a -> b) -> (f a -> f b)`, which maps types to types using pure functions. So any functor with the given type is an endofunctor and `Identity` is just the simplest one. Endofunctors are interesting, because their computational strategy works for any type, that is to say they are polymorphic. So restricting your `Box` functor to `String`s is not particularly useful. — , Jul 17 '17 at 07:30
Maybe it helps if we put functors aside and take a closer look at functions of type `a -> a` - polymorphic "endo-functions" so to speak. How many meaningful implementations of this besides `id = x => x` do exist? Afaik, none. — , Jul 17 '17 at 07:49
@Bergi - you're right. I though I knew what functors are (based on their abstract math definition) but I clearly should have looked around more about what their purpose is. Plus as you just noted, I started obsessing on the first term that I couldn't wrap my head around — toraritte, Jul 17 '17 at 14:51
@ftor - based on your comments, i think I also had the wrong idea about what "functor is a type of mapping between categories" means. I found your line `any functor with the given type is an endofunctor` especially intruiging and I have to rethink where I took a wrong turn. — toraritte, Jul 17 '17 at 14:56
@ftor @Bergi - thank you for your comments, really appreciate them. You were both right that fixing the type to `string` was dumb. I edited the question but I will clarify it more once I got further. Thanks again! — toraritte, Jul 17 '17 at 14:59
Here's a hint: a JavaScript array is a functor (must be homogeneous). — Jared Smith, Jul 17 '17 at 15:09
@JaredSmith, thanks, it helped but here's what makes me perplexed: if array had `map` only, it would just be an endofunctor with any given f. (Or not?...) So how would it become a functor? Adding `join`? (I am obsessing on functor vs clean endofunctor topic because for some reason I think that if I understand that then I'll get the rest too. Maybe I'm wrong, will read more.) — toraritte, Jul 17 '17 at 16:03
@toraritte for the purposes of programming, [all functors are endofunctors](https://stackoverflow.com/a/3870310/3757232). So no, understanding that difference will not help you at all. A functor is a data structure that can be mapped over, respects the identity function, and composition. That's really it. Don't overcomplicate it. — Jared Smith, Jul 17 '17 at 16:10
@JaredSmith wow, thanks for the link, I have to read it a couple more times to let it sink in. `for the purposes of programming, all functors are endofunctors` - this helped a lot too. I though there is something wrong with my reasoning because even looking at Haskell examples, they looked like endofunctors. — toraritte, Jul 17 '17 at 16:40
Also for future reference: https://stackoverflow.com/questions/10342876/differences-between-functors-and-endofunctors — toraritte, Jul 18 '17 at 09:17

Jared Smith · Accepted Answer · 2017-07-23T19:31:11.627

As pointed out in this answer, for our purposes as programmers we can treat all functors as endofunctors so don't get too caught up on the differences.

As for what a functor is, in brief it is

a data structure (Box in your example)
that can support a mapping operation (think Array.prototype.map)
and that mapping operation respects identity: xs === xs.map(x => x)
...and composition: xs.map(f).map(g) === xs.map(f . g) where . is function composition.

That's it. No more, no less. Looking at your Box, it's a data structure that has a map function (check 1 & 2) and that map function looks like it should respect identity and composition (check 3 & 4). So it's a functor. But it doesn't do anything, which is why it's the identity functor. The fold function isn't strictly necessary, it just provides a way to 'unwrap' the box.

For a useful functor, let's look at JavaScript arrays. Arrays actually do something: namely they contain multiple values rather than just a single one. If an array could only have one element, it'd be your Box. For our purposes we'll pretend that they can only hold values of the same type to simply things. So an array is a data structure, that has a map function, that respects identity and composition.

let plus = x => y => x + y;
let mult = x => y => x * y;
let plus2 = plus(2);
let times3 = mult(3);
let id = x => x;
let compose = (...fs) => arg => fs.reverse().reduce((x, f) => { return f(x) }, arg);  

// Here we need to stringify the arrays as JS will compare on 
// ref rather than value. I'm omitting it after the first for
// brevity, but know that it's necessary.
[1,2,3].map(plus2).toString() === [3,4,5].toString(); // true
[1,2,3].map(id) === [1,2,3]; // true
[1,2,3].map(plus2).map(times3) === [1,2,3].map(compose(times3, plus2)); // true

So when we map a function over a functor (array) we get back another instance of the same functor (a new Array) with the function applied to whatever the functor (array) was holding.

So now lets look at another ubiquitous JavaScript data structure, the object. There's no built in map function for objects. Can we make them a functor? Assume again that the object is homogenous (only has keys to one type of value, in this example Number):

let mapOverObj = obj => f => {
  return Object.entries(obj).reduce((newObj, [key, value]) => {
    newObj[key] = f(value);
    return newObj;
  }, {});
};

let foo = { 'bar': 2 };
let fooPrime = mapOverObj(foo)(plus2); // { 'bar': 4 }

And you can continue on to test that the function accurately (as far as is possible in JavaScript) supports identity and composition to satisfy the functor laws.

Re-reading your answer, the linked question and a couple other sources (https://en.m.wikipedia.org/wiki/Type_theory#Relation_to_category_theory . https://wiki.haskell.org/Category_theory ) i realised that the main cause of my confusion was that I arbitrarily identified categories with types whereas categories are specific type theories (such as Haskell's, Purescript's etc) and that's also why functors in functional programming are almost always endofunctors. — toraritte, Jul 18 '17 at 12:36
@toraritte yup, you got it. It can be hard to separate out intuitions of what a concept is from what it really is sometimes. — Jared Smith, Jul 18 '17 at 12:58
Tried suggesting an edit for the following but it got rejected, hence this comment: (1) the `compose` function would need a `slice()` as in the current form it replaces the input array in place, flip-flopping the order on every iteration (`let compose = (...fs) => arg => fs.`**`slice()`**`.reverse().reduce((x, f) => { return f(x) }, arg);`) (2) `mapOverObj` is missing the function application for a new value: `newObj[key] = f(value)`. Thanks again @JaredSmith because I just learned some new ES6 tricks as well! — toraritte, Jul 23 '17 at 18:50
@toraritte while `reverse` does work in place it only happens when the composed function is called. It doesn't happen on every iteration. Because the array is created by the splat operator rather than passed as an argument rearranging it destructively isn't a big deal. Good catch on the map function application. — Jared Smith, Jul 23 '17 at 19:30
Your reasoning is valid but then I'm doing something wrong because when I call `[1,2,3,4,5,6,7].map(compose(times3, plus2)) //> [9, 8, 15, 14, 21, 20, 27]` but with the `slice`d version the result is correct: `[9, 12, 15, 18, 21, 24, 27]` and it always happens when the input is reversed. (Thanks for the edit) — toraritte, Jul 23 '17 at 20:10
@toraritte odd. Nevertheless, the code I wrote was mostly for illustration: for actual usage I recommend a battle-tested fp library like ramda or lodash-fp. It was actually one of Brian Lonsdorf's (aka Professor Frisby) talks that introduced me to ramda a couple of years ago. — Jared Smith, Jul 24 '17 at 00:37

What would be a good example of an endofunctor that is not the identity functor?

1 Answers1

Linked