Possible undesired seq subsumption results in KeyValuePairs

[gusty]

This was a question posed here #288 (comment)

Regarding seq and subsumption: Seems it's also happening with tryFind (foldable) and empty (functor). When used for Map<,>, it's subsumed as seq<KeyValuePair<,>> in both cases.

[gusty]

@cmeeren Thanks for pointing out these 2 corner cases.

Let's take dive on them:

• In the latter case the subsumption is "stopped" by the type system. So for instance: let (x: Map<int,int>) = empty doesn't compile, it fails with:

  let (x: Map<int,int>) = empty ;;
  ------------------------^^^^^

stdin(124,25): error FS0001: This expression was expected to have type
    'Map<int,int>'    
but here has type
    'seq<KeyValuePair<int,int>>'    

of course, the error message is telling you that there was a subsumption and then type -check failed.

A better error message would be, "Map<_,_> is not an instance of Empty as if it would, there should be something available like an infinite or catch-all value to act as key which so far is not possible to represent.". Also it should be an applicative, which is not, for the same reason.

Maybe there's a way to improve the error message by adding an overload that catches this situation.

• In the former case, an interesting one btw, the subsumption is desired in principle. We have an overload that uses toSeq, and that's where this result is coming from. The intent is "we want to try find something on any foldable, a foldable can be represented as a seq, so if something supports toSeq we tryFind on the result of that conversion".

But as you point out, by doing for instance tryFind (konst true) (dict [1,4;2,5]) we get:

val it : KeyValuePair<int,int> option = Some [1, 4] {Key = 1; Value = 4;}

The ToSeq invokable has a simple overload that accepts subsumption on any seq<_> which kind of makes sense, because if something implements IEnumerable it can be converted to seq<_>.

The controversy comes from (as usual) the .NET framework which casts Map<int,int> as a seq<KeyValuePair<int,int>> so even without linking this library, if you do Map.ofSeq ([1,4;2,5]) :> seq<_> :> seq<_> you get val it : seq<KeyValuePair<int,int>> = map [(1, 4); (2, 5)].

Now, if you think about Map has 2 type parameters while seq<_> has only one. You could say "ok, if there are 2 type parameters we collapse them into a tuple" which kind of make sense but if you think about, it's also a bit arbitrary, we could claim to be a ValueTuple instead.

Going back to our tryFind, the generic signature is (predicate: 'T->bool) (source: 'Foldable<T>) : 'T option now how do we unify Foldable<'T> with Map<'K,'V> ?

Keep in mind it's really Map<'K,'V>, not Map<'K * 'V>.

Short answer: there's no standard way to represent two type parameters into one, so we stick to what .NET already does.

There's an open question here, forget all the above, the question could be: how a Map should fold Map<'K,'V>?

Maybe it should fold only the values? If so, we can add overloads to fight back the automatic conversion (this would be a breaking change, so it would be for v2).

There is a Map.fold in FSharp.Core but it has an incompatible signature as it uses an extra parameter for the key. But see? it folds with the key, so having a generic fold that takes both arguments inside a union (in this case a KeyValuePair) doesn't seem to be that wrong.

More thoughts welcome.

[cmeeren]

A better error message would be, "Map<_,_> is not an instance of Empty as if it would, there should be something available like an infinite or catch-all value to act as key which so far is not possible to represent.".

I don't get it. What is Map.empty, then? Isn't it the "same kind of thing" as List.empty, Seq.empty, None, etc.?

There is a Map.fold in FSharp.Core but it has an incompatible signature as it uses an extra parameter for the key.

Thanks, I see I was mistaken. tryFind is of course like List.tryFind, not like Map.tryFind, which is a different thing. The former takes a predicate and iterate through the collection to find a matching value. The latter is a Map-specific lookup by key.

it folds with the key, so having a generic folds that take both arguments inside a union (in this case a KeyValuePair) doesn't seem to be that wrong.

AFAIK one should never use this tryFind for a Map<_,_>, because the lookup would be very expensive, defeating the whole purpose of having a map in the first place. But there may of course be use-cases (particularly if it allows you to find by value, not key; I'm not entirely clear about this).

[gusty]

Regarding the Empty instance for Map<_,_> it would have to obey some rules, like distributive:
(result id <|> g) <*> x = x <|> (g <*> x).

As you can see there, it would require it to implement <|> from Alternative and also Return from Applicative.

As for <*> there is already an overload, what it does is similar to the ZipList semantic, it applies the function point-wise but here instead of indexes we have keys, so we can say key-wise.

But I said it's not an Applicative as it still lacks Return. Why?
Think about return for ZipList, it results in an infinite sequence. Why?
Because that way it will match any application to any index, an empty dictionary would do the opposite, the same way an empty ZipList does, they shortcut instead as they never match anything.

In order to match any application for any key, note that this is technically possible for finite sets, like bool, so:

(+) <!> Map.ofSeq [true,1] <*> Map.ofSeq [true,5]

as the first term which resolved to result (+) would yield

val it : Map<bool,(int -> int -> int)> = map [(false, <fun:it@130-12>); (true, <fun:it@130-11>)]

still this is far from practical for most types, we should have a kind of wildcard value for the key like for instance in the case of result (+): Map<string,int->int->int> it would give you some value like

val it : Map<string,(int -> int -> int)> = map [(*, <fun:it@9>)] where * would mean any-key, so it.["a"] = (+) and it.["b"] = (+) and it.["anything"] = (+).

Having said that, I reckon the distributive rule is rarely obeyed, that's one of the reasons I didn't include it in http://fsprojects.github.io/FSharpPlus/abstraction-alternative.html#Rules

If we look carefully those rules, we can see that empty for Map defined as Map.empty would pass them, still we'll need to add an instance for <|> but I think this is also possible by defining it like the union of both, to be consistent with ZipList's <|> we can give priority to the elements on the right.

So, I would accept a PR that treats Maps (and why not dictionaries and possibly Sets) as alternatives as long as those rules are obeyed.

[cmeeren]

Thanks for the explanation. It went a bit over my head. In any case, please don't go to the trouble of implementing this just for me to be able to write empty instead of Map.empty. Feel free to close the issue if you want. :)