3 ms·
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.
by 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 agoI 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 agoYou 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.
- freyrs3 12y agoThough if you take this intuition too far it tends to break down, for instance IO and ST both define functor instances but it doesn't really make sense to talk about a functor over IO preserving shape.