Post-condition for map functions
f#, functional-programming, functor
Solution
Many points of view, here is mine:
We can think of all `map` functions/methods as specific cases of Haskell's `fmap` of Functors. From that definition we can assume that the structure will be preserved (plus some other interesting properties).
But in .NET there are no Typeclasses so we can define `map` over 'restricted Functors', the consequence is some Functor properties will not be preserved, but since there is no generic code that will be affected the impact is limited.
So nothing stops us to define `map` over:
- Sets (restriction: the function must be 'a->'b when 'a and 'b: comparison and should be injective)
- Strings (restriction: the function should be char->char)
- Nullables (restriction: the function should be 'a->'b where 'b is not a reference type)
Notice that in some cases there are restrictions at both type and value level, for example for sets the restriction at type level is both types 'a and 'b should have comparison while the restriction over the function value is that the function should be injective.
If the language is able to express the type level constraints the compiler will throw an error when these requirements are not met.
For function values there are no compile-time restrictions though we can create unit tests if we want to ensure they are correct. But what would happen if we don't care about constraining those functions?
Well, as long as we understand that some Functor properties will not be obeyed there's nothing wrong in using a map over a restricted Functor.
So we can define a `map` over structures like sorted lists, of course we can't assume that `map a >> map b` will be always equivalent to `map (a >> b) `in these cases. The restriction here is that the function should be monotonically increasing.
NOTE: For Haskell there is a package with a restricted functor and an instance for Sets
Problem
Do the map functions (Seq.map, List.map etc) have an implicit post-condition that the output has the same number of items as the input? Going further, if we had some kind of Tree.map function, is there an assumption that the "shape" of the input and output trees are the same? The reason that I ask is that I had always made such an assumption (and I suspect that a lot of code that maps over sequences does too), but then I discovered that Set.map can return a smaller set if the mapping function produces duplicates. So either my assumption is invalid, or Set should not be treated as a sequence for mapping purposes. Which is it?