Post Condition for Map Functions

Question

Do the map functions (Seq.map, List.map, etc.) have an implicit post-condition that the output has the same number of elements 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 is the same?

The reason I ask is because I always made that assumption (and I suspect there is a lot of code that displays sequences) too, but then I found that Set.map could return a smaller set if the mapping Function produces duplicates. Therefore, either my assumption is invalid or Set should not be considered a sequence for matching purposes. What is it?

Answer 1

Many points of view are mine:

We can consider all map functions / methods as specific cases of Haskell fmap functors . From this definition, it can be assumed that the structure will be preserved (plus some other interesting properties).

But in .NET there are no Typeclasses, so we can define a map over "restricted functors", the consequence of which is Functor properties will not be saved, but since there is no common code that will be affected, the impact will be limited.

Therefore, nothing prevents us from defining map over:

• Sets (restriction: the function must be "a →" b, when "a" and "b": comparison must be injective )
• Strings (restriction: the function must be char -> char)
• Nullables (restriction: the function must be "a →" b, where "b is not a reference type")

Please note that in some cases there are restrictions both at the type level and at the level of values, for example, for sets, the restriction at the level level is both types: "a" and "b" must have a comparison, while the restriction over The value of the function is that the function should be injective .

If the language is capable of expressing type level restrictions, the compiler will throw an error if these requirements are not met.

There are no compilation time limits for function values, although we can create unit tests if we want to make sure that they are correct. But what happens if we do not care about limiting these functions?

Well, if we understand that some Functor properties will not be respected, there is nothing wrong with using a map over a limited Functor .

Thus, we can define a map over structures such as sorted lists, of course, we cannot assume that map a >> map b will always be equivalent to map (a >> b) in these cases. The limitation here is that the function must increase monotonously .

NOTE. For Haskell, there is a package with a restricted functor and an instance for Sets

Answer 2

Yes, I would expect the map function to respect the input structure (although many implementations probably won't have an explicit test).

In the case of Set.map it can be argued that this (parametric) map implementation itself is correct, but the argument function must be injective so that the general display function preserves the structure. So, indeed, for sets, this is a combined property of two functions.

It would be easy to wrap Set.map some kind of check, checking if the argument function is injective as it is applied.

Answer 3

Sets are a little complicated because you can only create a set of things for which you can check if they are equal. In fact, F # sets are actually represented as trees, so you should be able to compare them.

It also means that the map function for sets is not the same as the map function for lists:

 List.map : ('a -> 'b) -> 'a list -> 'b list Set.map : ('a -> 'b) -> Set<'a> -> Set<'b>) when 'a : comparison and 'b : comparison 

The fact that you should be able to compare the 'b values ​​explains why the map function on sets can do more than the regular map function for lists and sequences. Therefore, this is not a normal card operation!

(Of course, there are other possible ways to split this into F # - the map function may return an empty list - but then the output type of the result will be 'c list , so that the map will also be different).

Answer 4

Yes, usually you expect map to keep shape (and therefore keep size). But for sets, this obviously cannot be done at all, since sets must obey some additional laws (for example, there are no duplicate elements), so Set.map (f : X -> bool) obviously will not preserve the size of the set if it applies to set with more than two elements in it).

Answer 5

The term map is based on math and simply refers to a function. On his own, he does not make statements about how the results are presented. I would suggest that the answer depends on the type of content display.

Thus, either my assumption is incorrect, or Set should not be considered as a sequence for matching purposes. What is it?

I would say that the assumption is not valid as a whole, but must be fair if it can be reasonably applied. For example, if a tree requires a structure that depends on the values ​​contained, and one such tree is mapped to another, it is not possible to create a valid result that supports the tree structure.

However, you can think of a set as a sequence for matching purposes, like anything that can be converted to IEnumerable<> . Just use Seq.map instead of Set.map .