Tuesday, February 01, 2011

F# and polymorphic constraints

I have lots of polymorphic code these days, they are meant to work on many types, but sometimes they do not. Last night my expression mapping functions was causing me trouble. It starts:
let mapExpr mapERAcc mapLEAcc m' e = state {
let mapER = mapERAcc m'
let mapLE = mapLEAcc m'
match e with
| Arrow(le, te) ->
let! le' = mapRightState mapLE le
let! te' = mapER te
...
As you see it is not only monadic but also knows nothing about the recursion of the expression type. That is on purpose so that this map function can be combined with other map functions to transform any use of the parameterized expression type. Anyways, this functions is meant to take in one version of the expression type and produce another one. What does not work is the ability to impose that. Instead, when I see that my code does not compile "somewhere else". I need to figure out that I have made a mistake. For example, yesterday evening I had added the code:
| ExprDef e ->
let! e' = mapER e
return ExprDef e
That last line is missing a single quote and should be ExprDef e'. The compiler will not tell me that now the return expression type is the same as the input expression type. To find the bug I can make the polymorphism explicit, with the function defined as:

let mapExpr<'e1,'e2> (mapERAcc:_->'e1->StateR<_,'e2,_>) mapLEAcc m' e = ...
Now the compiler will report that 'e1 does not match 'e2. Making the polymorphism explicit would be the correct way to impose this "not equal type" constraint. The problem is that F# has a fragile type inference algorithm and if polymorphic functions are always defined explicitly the inter-module type inference simply fails with impossible errors. Therefore I do not explicitly declare the polymorphism and this hurts.

No comments: