4 ms·

A Mappable would be anything that has a `map` function. A `Functor` is a something that has a `map` function _AND_ obeys the rule that calling `map` with the i

A Mappable would be anything that has a `map` function. A `Functor` is a something that has a `map` function _AND_ obeys the rule that calling `map` with the identity function produces the same result. ie: say I have some value `f` that is a functor. If I call `map identity f` I should always get back `f`. The mere existence of a `map` function doesn't imply this law holds. The identity function always returns it's argument unmodified. (identity x = x) (Now, in Haskell the type system does not encode that law, but not following it would be breaking the interface.) If this explanation doesn't make sense or you need more examples I'm happy to expand EDIT: Both me and grandparent forgot another law for functors. They also need to preserve composition. fmap (f . g) == fmap f . fmap g In english, if I combine the functions f and g and map them, it should be the same as if I first map g and then map f

dwohnitmok 5y ago
> They also need to preserve composition. I didn't state this because this generally comes for free, assuming no shenanigans such as runtime type reflection/type-casing (but in that case all laws go out the window). In particular in Haskell (which is what I assume you're coming from given fmap and your ML-ish syntax) this is a superfluous law. If a type constructor's `fmap` obeys the identity law, it must obey the composition law.
- opnitro 5y ago
  Yes that seems right, sorry.
Shish2k 5y ago
> A Mappable would be anything that has a `map` function. A `Functor` is a something that has a `map` function _AND_ obeys the rule that calling `map` with the identity function produces the same result. This sentence just taught me more about functional programming terminology than 4 years of university and 20 years of casual blog-post reading :O
OJFord 5y ago
> They also need to preserve composition. > fmap (f . g) == fmap f . fmap g Can you give an example where that doesn't follow from `map identity f == f`? Assuming of course `f` .. is what I think is called 'pure'? i.e. is deterministic on its input arguments.
tantalor 5y ago
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."

dwohnitmok 5y ago

> They also need to preserve composition. I didn't state this because this generally comes for free, assuming no shenanigans such as runtime type reflection/type-casing (but in that case all laws go out the window). In particular in Haskell (which is what I assume you're coming from given fmap and your ML-ish syntax) this is a superfluous law. If a type constructor's `fmap` obeys the identity law, it must obey the composition law.

opnitro 5y ago
Yes that seems right, sorry.

Shish2k 5y ago

> A Mappable would be anything that has a `map` function. A `Functor` is a something that has a `map` function _AND_ obeys the rule that calling `map` with the identity function produces the same result. This sentence just taught me more about functional programming terminology than 4 years of university and 20 years of casual blog-post reading :O

OJFord 5y ago

> They also need to preserve composition. > fmap (f . g) == fmap f . fmap g Can you give an example where that doesn't follow from `map identity f == f`? Assuming of course `f` .. is what I think is called 'pure'? i.e. is deterministic on its input arguments.

tantalor 5y ago

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."