3 ms·

What is a good example (not contrived) of a mappable non-functor?

opnitro 5y ago
To be honest with you, you're right in that you usually get that one without trying. Most of the things we think of as mappable obey the identity rules.
- tantalor 5y ago
  I think the confusion is calling anything that doesn't "obey the rules" a map function just because it is named "map". For example, ruby's hash "map" returns an array instead of hash. That's not really a map, is it? Making this useless distinction between "things with map function" and "functors" serves no purpose. It should be "things with real/fake map functions". The name of the function does not matter!
  - opnitro 5y ago
    Sure, the name doesn't matter. The type does though. `Functor f => a -> b -> f a -> f b` And it most type systems the law can't easily be captured in the type system.
dwohnitmok 5y ago
Great question! There's a minority of them, but the ones I've run into the wild all usually boil down to having some internal book-keeping that is either triggered by function calls or can affect a function call. For example, caches whose eviction calculation is triggered by function invocation aren't functors, even if you can map over the elements in the cache (since just calling any function on the cache can cause certain elements to be evicted). That's a bit of a weird one because caches also usually have some time-dependent behavior (which in general makes notions of things like equality a bit hard to pin down and so moots a lot of laws), but you can also have caches with eviction policies that are not based on time strictly, but rather deterministic heuristics that use the number of function calls as an input to the heuristic. Another example is certain tree-based data structures that use function calls to rebalance themselves in a way where the rebalancing causes publicly observable changes. Again there just calling map by itself can trigger a rebalancing, regardless of whether identity is passed or not. Another example is stuff like variants of `Iterator` where just iterating over something creates changes or function calls are logged. FWIW all these cases of a mappable non-functor can be changed into a mappable functor, simply by "suspending" calling the function until you actually ask for a value (so the `map` call does nothing other than just squirrel the function away somewhere). So often the idea of a mappable non-functor isn't useful so much for truly distinguishing a functor from a non-functor, as it is for pointing out how you should implement `map` in a way that "makes sense."

To be honest with you, you're right in that you usually get that one without trying. Most of the things we think of as mappable obey the identity rules.

tantalor 5y ago
I think the confusion is calling anything that doesn't "obey the rules" a map function just because it is named "map". For example, ruby's hash "map" returns an array instead of hash. That's not really a map, is it? Making this useless distinction between "things with map function" and "functors" serves no purpose. It should be "things with real/fake map functions". The name of the function does not matter!
- opnitro 5y ago
  Sure, the name doesn't matter. The type does though. `Functor f => a -> b -> f a -> f b` And it most type systems the law can't easily be captured in the type system.

dwohnitmok 5y ago

Great question! There's a minority of them, but the ones I've run into the wild all usually boil down to having some internal book-keeping that is either triggered by function calls or can affect a function call. For example, caches whose eviction calculation is triggered by function invocation aren't functors, even if you can map over the elements in the cache (since just calling any function on the cache can cause certain elements to be evicted). That's a bit of a weird one because caches also usually have some time-dependent behavior (which in general makes notions of things like equality a bit hard to pin down and so moots a lot of laws), but you can also have caches with eviction policies that are not based on time strictly, but rather deterministic heuristics that use the number of function calls as an input to the heuristic. Another example is certain tree-based data structures that use function calls to rebalance themselves in a way where the rebalancing causes publicly observable changes. Again there just calling map by itself can trigger a rebalancing, regardless of whether identity is passed or not. Another example is stuff like variants of `Iterator` where just iterating over something creates changes or function calls are logged. FWIW all these cases of a mappable non-functor can be changed into a mappable functor, simply by "suspending" calling the function until you actually ask for a value (so the `map` call does nothing other than just squirrel the function away somewhere). So often the idea of a mappable non-functor isn't useful so much for truly distinguishing a functor from a non-functor, as it is for pointing out how you should implement `map` in a way that "makes sense."