10 ms·

I don't understand what a functor is or why an array is a functor. Can anyone please explain? I did the wikipedia article for category theory and I read some st

I don't understand what a functor is or why an array is a functor. Can anyone please explain? I did the wikipedia article for category theory and I read some stack overflow questions and I'm not sure I understand why an array is a functor. It seems some languages have their own meaning for what a "functor" is, confusing the issue. My initial guess is that a functor is just sort of like a function that casts or does something like return an interface type from a type that implements the interface or a base class. Is that right? I still don't understand why an array is a functor though, I'd imagine it would at least have to be a function? Edit: Actually I think he's talking about Haskell's version of an iterable, and it would then make sense to call an array a functor. https://en.wikibooks.org/wiki/Haskell/The_Functor_class https://en.wikibooks.org/wiki/Haskell/The_Functor_class Why is that called a functor instead of an iterable or enumerable though?

JoshTriplett 12y ago
The name "Functor" can be confusing; it's a thing you apply a function to, not a function itself. A Functor is a type t parameterized by some other type a, such that if you have a function from type a to type b, you can apply that function to a t of a and get a t of b. Most commonly, a functor will be a container of values of type a, and the mapping consists of applying the function to each value, resulting in a container of values of type b. Other common functors include a computation that returns type a (use composition to apply the function to the result to get a computation that returns type b), or a possibly null pointer to type a (map null to null, map pointer to a to pointer to b).
- twic 12y ago
  In an alternate universe where functional programming was invented by programmers rather than mathematicians, map would probably be called something like convertWith and a functor would probably be called something like a convertible. If you think of a function as being a way of converting from one kind of thing to another, then a functor is an object which has a number of things which you can convert to some other kind (a number which may be one or zero), using a method of your choice, and map is the name of the method you use to do that.
  - blahber 12y ago
    /wow More please ! Also guys, please check this new submission. https://news.ycombinator.com/item?id=7895901 https://news.ycombinator.com/item?id=7895901 Alice and Bob play a cryptographic tetris game. Some french phd bloke has written it.
    - dang 12y ago
      Would you please stop putting "/word" at the top of your comments? Gimmicks like that don't work here.
      - blahber 12y ago
        /love It is a pattern, yes. Let me show you a pattern that I have observed in Hacker News and forums since the demise of USENET. USENET had an elegant way of ignoring without hellbanning, which the negative karma has done to me now. Would you please study the history of Stalinism ? Let me summarise it for you. Ideology -- pg. Yeah, Marx is a good guy too. It is made of dictators and the inner ring -- Admins and Karma users like you. These people have special "powers" of punishment. Admins have far greater powers of purging and renaming things. Then the party cadre -- people who submit and actually keep the things in motion. They are usually not aware of the "inner ring", users like you. They want to help the lay people. In fact no one even knows who is in the inner ring. The inner ring is clueless of the Admins. Then there are lay users like me, who lurk around and want to help but are generally punished. If you think I am shitting you consider the rate of new users becoming high karma users in HN over the years. You can use d3 and it will go the top of HN. Your pedantry is just arbitrary. There is nothing really substantial in it. Rather than judging on the basis of content, you are judging me on the "words" I use. Gimmick: An ingenious or novel device, scheme, or stratagem, especially one designed to attract attention or increase appeal. Why thank you, it is novel :) Please understand the democratic roots of the word "forum" and take it seriously.
  - skybrian 12y ago
    In Java we would call it "Mappable". A Mappable interface would have one method: map(). It hasn't been all that useful until recently due to lack of closures, but perhaps it would make sense in Java 8? "Functor" is a terrible name that only a mathematician could like.
afthonos 12y ago
Let's begin with the array. Imagine I have an array of characters: var a = ['a', 'b', 'c'] I'd like instead to have the index of their position in the alphabet. That's another array of the same length that would look like this: var i = [0, 1, 2] To each element in a, there corresponds an element i, at the same index. And the operation we use is the same for each element: f('a') = 0 f('b') = 1 f('c') = 2 But we could also want an array that gives us the next letter in the alphabet, like so: var n = ['b', 'c', 'd'] Here the function is: g('a') = 'b' g('b') = 'c' g('c') = 'd' But we're very much doing the same thing. We call it mapping. So Arrays in Swift have a map function defined that works like this: var i2 = a.map(f) We're passing the function to apply to each member, and we get an array back, of the same length, with the result of doing so. A functor is a generalization of that concept. It takes a type parametrized by another type, say Box<V> and a function from the parametrized type to another type, say f:V -> W. Then, according to rules that are specific to Box, if you map f over Box<V>, you'll get a Box<W> out. The key is that exactly how a Box<V> becomes a Box<W> is up to Box.
orbifold 12y ago
More precisely it is an endofunctor in the category whose objects are Swift types and morphisms are functions between Swift types. All this really means is that given a Swift type, say Int or String, there are Arrays of Int or String, and given a function like showInt(a : Int) : String, a functor gives you a function from an Array of Int to an Array of String (in this case it would just apply showInt to each element of the Array and the result would be the Array of String) in such a way that if you have two functions (to keep with the example, say toUppercase(s : String) : String, the function you get by applying the functor to the composition (toUppercase . showInt) is the same as the composition of functions gotten from the application of the functor to the individual functions. In addition it is required that the identity function is mapped to the identity function.
- muaddirac 12y ago
  Thank you for this. I find explanations that eschew category theory bizarre, this really cleared things up for me (having spent a lot of time with functors mathematically, and almost no time with them in a programming context).
  - leorocky 12y ago
    I appreciate orbifold taking the time to reply but I couldn't understand his answer at all, even after perfectly understanding what others have said. There are 3 sentences in that paragraph the second of which is very large and difficult to parse and missing an end parenthesis somewhere. Why do you get a composition of functions by applying a functor to individual functions? It seems like a functor is just something you can map over. When a functor is mapped over the end result is another functor. Not a function nor a composition of functions.
    - Dewie 12y ago
      > Why do you get a composition of functions by applying a functor to individual functions? It seems like a functor is just something you can map over. When a functor is mapped over the end result is another functor. Not a function nor a composition of functions. A function is a Functor. ;) If you have a function f and a function g, fmap f g = h, and h is a function. A more common way to write this is function composition of f and g, which can be written: f . g. The dot (.) is function composition. Which means that fmap f g = f . g, which means that fmap = (.). > When a functor is mapped over the end result is another functor. Not a function nor a composition of functions. But they was describing the case when the Functor in question is a function.
tel 12y ago
If something is Iterable, it's a Functor, but not the other way around. Iterable implies there's an order to the elements, for instance. It also implies that you could get ahold of the elements if you chose. Types which are Functors may have orders and may provide access to the elements, but the Functor interface does not provide those means. This allows you to instantitate more restrictive types. For instance (in Haskell notation) data Pretend a = Pretend is a data type with only one element (`Pretend`) that pretends to be a container. Consider the two types Array Int Pretend Int You can still consider Pretend to be a Functor (the mapping function is just a no-op) but it certainly isn't iterable. In Haskell, Iterable is called Foldable and effectively is the following interface instance Foldable c where toList :: c a -> [a] but `Foldable` is used because typically instead of converting it to a list you want to fold over the elements fold :: Foldable c => (a -> b -> b) -> b -> c a -> b
Dewie 12y ago
> Why is that called a functor instead of an iterable or enumerable though? Probably because 1) it is inspired by category theory rather than some interface/signature from another programming language 2) "Iterable"/"Enumerable" might be misleading. 2): It might make sense for things like arrays, where you can think of the function (fmap) as enumerating/iterating over the array and then, for each value in the array, uses the supplied function on it. But Functors aren't just things that you can iterate over; functions themselves are functors, and function composition is fmap. But how does the iteration-intuition make sense in this case? Other functors are more a kind of "box" than a collection that can be iterated over (for example: the Option/Maybe type). Sure, you can say that you can implement fmap on Maybe by iterating over the data that it holds, namely the single data that it holds, but that doesn't really say much.
wting 12y ago
A functor is a thing that can be mapped over. For example: map abs [-1, 2, 3] => [1, 2, 3] Arrays are the simplest example, but it looks like an iterable. However functors retain shape whereas iterables don't. For example if we had a tree (represented visually): oak = -1 / \ 2 3 If we used oak as an iterable, we would lose the structure of the tree: map abs iter(oak) => [1, 2, 3] However if tree belongs to the functor typeclass (i.e. implements functor interface), then: map abs oak => 1 / \ 2 3 The alternatives to functors are: 1. mutate the existing data structure 2. copy a new one and then mutate (two passes) 3. create a new one while mutating (one pass, increased complexity / bugs)
- leorocky 12y ago
  I get it now, thank you for this great explanation, and all the other explanations as well. I think it warrants its own wikipedia page.
- dscrd 12y ago
  >However functors retain shape whereas iterables don't. Wow. Such a simple sentence yet this is the first time I have read it, and it makes the concept much more clear than hundreds of articles before did. Thank you! I wish all FP features would be explained so simply.
  - acomar 12y ago
    You can build a bit of mathematical intuition for the concept now that you get the basic idea. Try and work out from the functor laws why functors preserve shape. The laws are very straightforward: map id c = id c (Mapping the identity function is the same as simply applying the identity function -- or with a little more category theory, the functor maps the identity function in the base category to the identity function in the functor's category) map f (map g c) = map (f . g) c The second law is also simple -- mapping one function over the container then mapping another function is exactly the same as mapping the composition of the functions over the container. This one is the basis of stream fusion, a very important optimization, that allows you take two traversals of a container and turn them automatically into just one traversal. The preservation of structure follows from just these two laws and parametricity (The element type of the containers is generic and therefore unknown, this greatly restricts what operations are available on the elements of the container. You can't, for example, conjure up a new value of the element type to insert.). I strongly recommend trying to figure out how.
ScottBurson 12y ago
The term "functor" is badly overloaded in general -- almost every language that uses the term has its own definition. In C++, it's an object that can be called as a function (by virtue of defining 'operator()') [0]. In Prolog, it's the head and arity of a term [1]. In ML, it's a function from structures to structures [2]. [0] http://www.stanford.edu/class/cs106l/course-reader/Ch13_Functors.pdf http://www.stanford.edu/class/cs106l/course-reader/Ch13_Func... [1] http://www.swi-prolog.org/pldoc/man?predicate=functor/3 http://www.swi-prolog.org/pldoc/man?predicate=functor/3 [2] http://en.wikipedia.org/wiki/Standard_ML#Module_system http://en.wikipedia.org/wiki/Standard_ML#Module_system

JoshTriplett 12y ago

The name "Functor" can be confusing; it's a thing you apply a function to, not a function itself. A Functor is a type t parameterized by some other type a, such that if you have a function from type a to type b, you can apply that function to a t of a and get a t of b. Most commonly, a functor will be a container of values of type a, and the mapping consists of applying the function to each value, resulting in a container of values of type b. Other common functors include a computation that returns type a (use composition to apply the function to the result to get a computation that returns type b), or a possibly null pointer to type a (map null to null, map pointer to a to pointer to b).

twic 12y ago
In an alternate universe where functional programming was invented by programmers rather than mathematicians, map would probably be called something like convertWith and a functor would probably be called something like a convertible. If you think of a function as being a way of converting from one kind of thing to another, then a functor is an object which has a number of things which you can convert to some other kind (a number which may be one or zero), using a method of your choice, and map is the name of the method you use to do that.
- blahber 12y ago
  /wow More please ! Also guys, please check this new submission. https://news.ycombinator.com/item?id=7895901 https://news.ycombinator.com/item?id=7895901 Alice and Bob play a cryptographic tetris game. Some french phd bloke has written it.
  - dang 12y ago
    Would you please stop putting "/word" at the top of your comments? Gimmicks like that don't work here.
    - blahber 12y ago
      /love It is a pattern, yes. Let me show you a pattern that I have observed in Hacker News and forums since the demise of USENET. USENET had an elegant way of ignoring without hellbanning, which the negative karma has done to me now. Would you please study the history of Stalinism ? Let me summarise it for you. Ideology -- pg. Yeah, Marx is a good guy too. It is made of dictators and the inner ring -- Admins and Karma users like you. These people have special "powers" of punishment. Admins have far greater powers of purging and renaming things. Then the party cadre -- people who submit and actually keep the things in motion. They are usually not aware of the "inner ring", users like you. They want to help the lay people. In fact no one even knows who is in the inner ring. The inner ring is clueless of the Admins. Then there are lay users like me, who lurk around and want to help but are generally punished. If you think I am shitting you consider the rate of new users becoming high karma users in HN over the years. You can use d3 and it will go the top of HN. Your pedantry is just arbitrary. There is nothing really substantial in it. Rather than judging on the basis of content, you are judging me on the "words" I use. Gimmick: An ingenious or novel device, scheme, or stratagem, especially one designed to attract attention or increase appeal. Why thank you, it is novel :) Please understand the democratic roots of the word "forum" and take it seriously.
- skybrian 12y ago
  In Java we would call it "Mappable". A Mappable interface would have one method: map(). It hasn't been all that useful until recently due to lack of closures, but perhaps it would make sense in Java 8? "Functor" is a terrible name that only a mathematician could like.

afthonos 12y ago

Let's begin with the array. Imagine I have an array of characters: var a = ['a', 'b', 'c'] I'd like instead to have the index of their position in the alphabet. That's another array of the same length that would look like this: var i = [0, 1, 2] To each element in a, there corresponds an element i, at the same index. And the operation we use is the same for each element: f('a') = 0 f('b') = 1 f('c') = 2 But we could also want an array that gives us the next letter in the alphabet, like so: var n = ['b', 'c', 'd'] Here the function is: g('a') = 'b' g('b') = 'c' g('c') = 'd' But we're very much doing the same thing. We call it mapping. So Arrays in Swift have a map function defined that works like this: var i2 = a.map(f) We're passing the function to apply to each member, and we get an array back, of the same length, with the result of doing so. A functor is a generalization of that concept. It takes a type parametrized by another type, say Box<V> and a function from the parametrized type to another type, say f:V -> W. Then, according to rules that are specific to Box, if you map f over Box<V>, you'll get a Box<W> out. The key is that exactly how a Box<V> becomes a Box<W> is up to Box.

orbifold 12y ago

More precisely it is an endofunctor in the category whose objects are Swift types and morphisms are functions between Swift types. All this really means is that given a Swift type, say Int or String, there are Arrays of Int or String, and given a function like showInt(a : Int) : String, a functor gives you a function from an Array of Int to an Array of String (in this case it would just apply showInt to each element of the Array and the result would be the Array of String) in such a way that if you have two functions (to keep with the example, say toUppercase(s : String) : String, the function you get by applying the functor to the composition (toUppercase . showInt) is the same as the composition of functions gotten from the application of the functor to the individual functions. In addition it is required that the identity function is mapped to the identity function.

muaddirac 12y ago
Thank you for this. I find explanations that eschew category theory bizarre, this really cleared things up for me (having spent a lot of time with functors mathematically, and almost no time with them in a programming context).
- leorocky 12y ago
  I appreciate orbifold taking the time to reply but I couldn't understand his answer at all, even after perfectly understanding what others have said. There are 3 sentences in that paragraph the second of which is very large and difficult to parse and missing an end parenthesis somewhere. Why do you get a composition of functions by applying a functor to individual functions? It seems like a functor is just something you can map over. When a functor is mapped over the end result is another functor. Not a function nor a composition of functions.
  - Dewie 12y ago
    > Why do you get a composition of functions by applying a functor to individual functions? It seems like a functor is just something you can map over. When a functor is mapped over the end result is another functor. Not a function nor a composition of functions. A function is a Functor. ;) If you have a function f and a function g, fmap f g = h, and h is a function. A more common way to write this is function composition of f and g, which can be written: f . g. The dot (.) is function composition. Which means that fmap f g = f . g, which means that fmap = (.). > When a functor is mapped over the end result is another functor. Not a function nor a composition of functions. But they was describing the case when the Functor in question is a function.

tel 12y ago

If something is Iterable, it's a Functor, but not the other way around. Iterable implies there's an order to the elements, for instance. It also implies that you could get ahold of the elements if you chose. Types which are Functors may have orders and may provide access to the elements, but the Functor interface does not provide those means. This allows you to instantitate more restrictive types. For instance (in Haskell notation) data Pretend a = Pretend is a data type with only one element (`Pretend`) that pretends to be a container. Consider the two types Array Int Pretend Int You can still consider Pretend to be a Functor (the mapping function is just a no-op) but it certainly isn't iterable. In Haskell, Iterable is called Foldable and effectively is the following interface instance Foldable c where toList :: c a -> [a] but `Foldable` is used because typically instead of converting it to a list you want to fold over the elements fold :: Foldable c => (a -> b -> b) -> b -> c a -> b

Dewie 12y ago

> Why is that called a functor instead of an iterable or enumerable though? Probably because 1) it is inspired by category theory rather than some interface/signature from another programming language 2) "Iterable"/"Enumerable" might be misleading. 2): It might make sense for things like arrays, where you can think of the function (fmap) as enumerating/iterating over the array and then, for each value in the array, uses the supplied function on it. But Functors aren't just things that you can iterate over; functions themselves are functors, and function composition is fmap. But how does the iteration-intuition make sense in this case? Other functors are more a kind of "box" than a collection that can be iterated over (for example: the Option/Maybe type). Sure, you can say that you can implement fmap on Maybe by iterating over the data that it holds, namely the single data that it holds, but that doesn't really say much.

wting 12y ago

A functor is a thing that can be mapped over. For example: map abs [-1, 2, 3] => [1, 2, 3] Arrays are the simplest example, but it looks like an iterable. However functors retain shape whereas iterables don't. For example if we had a tree (represented visually): oak = -1 / \ 2 3 If we used oak as an iterable, we would lose the structure of the tree: map abs iter(oak) => [1, 2, 3] However if tree belongs to the functor typeclass (i.e. implements functor interface), then: map abs oak => 1 / \ 2 3 The alternatives to functors are: 1. mutate the existing data structure 2. copy a new one and then mutate (two passes) 3. create a new one while mutating (one pass, increased complexity / bugs)

leorocky 12y ago
I get it now, thank you for this great explanation, and all the other explanations as well. I think it warrants its own wikipedia page.
dscrd 12y ago
>However functors retain shape whereas iterables don't. Wow. Such a simple sentence yet this is the first time I have read it, and it makes the concept much more clear than hundreds of articles before did. Thank you! I wish all FP features would be explained so simply.
- acomar 12y ago
  You can build a bit of mathematical intuition for the concept now that you get the basic idea. Try and work out from the functor laws why functors preserve shape. The laws are very straightforward: map id c = id c (Mapping the identity function is the same as simply applying the identity function -- or with a little more category theory, the functor maps the identity function in the base category to the identity function in the functor's category) map f (map g c) = map (f . g) c The second law is also simple -- mapping one function over the container then mapping another function is exactly the same as mapping the composition of the functions over the container. This one is the basis of stream fusion, a very important optimization, that allows you take two traversals of a container and turn them automatically into just one traversal. The preservation of structure follows from just these two laws and parametricity (The element type of the containers is generic and therefore unknown, this greatly restricts what operations are available on the elements of the container. You can't, for example, conjure up a new value of the element type to insert.). I strongly recommend trying to figure out how.

ScottBurson 12y ago

The term "functor" is badly overloaded in general -- almost every language that uses the term has its own definition. In C++, it's an object that can be called as a function (by virtue of defining 'operator()') [0]. In Prolog, it's the head and arity of a term [1]. In ML, it's a function from structures to structures [2]. [0] http://www.stanford.edu/class/cs106l/course-reader/Ch13_Functors.pdf http://www.stanford.edu/class/cs106l/course-reader/Ch13_Func... [1] http://www.swi-prolog.org/pldoc/man?predicate=functor/3 http://www.swi-prolog.org/pldoc/man?predicate=functor/3 [2] http://en.wikipedia.org/wiki/Standard_ML#Module_system http://en.wikipedia.org/wiki/Standard_ML#Module_system