Value restriction woes

I was experimenting with an implementation of Clojure Transducers in F#, and quickly hit the dreaded Value Restriction error.

The whole point of Transducers is to be composable. This is some sample code:

type Reducer<'a,'b,'c> = ('a -> 'b -> 'a) -> 'a -> 'c -> 'a

module Transducers =
   [<GeneralizableValue>]
   let inline map proj : Reducer<'result,'output,'input> =
      fun xf ->
        fun result input ->
            xf result (proj input)

   let inline conj xs x = x :: xs
   let inline toList xf input = List.fold  (xf conj) [] input

   let xform = map (fun i -> i + 9) >> map (fun a -> a * 5)
   //let xs = toList xform [1;2] // if you apply this, type will be fixed to 'a list
                                 // which makes xform unusable with eg 'a seq

Play on dotnetfiddle

GeneralizableValue was supposed to lift the value restriction, but does nothing, it seems. Your mission is to make this code compile without applying toList (Type inference will fix the type to 'a list, so you could not use the same xform with a seq) and without changing the type of xform (at least not in a way so as to make it not composable). Is this simply not possible in F#?

Solution

Why would annotating map with [<GeneralizableValue>] affect whether xform is subject to the value restriction? (in any case, map is already generalizable since it's defined by a lambda; also I don't see the point of all the inlines).

If your requirements are:

xform must be generic, but not an explicitly annotated type function
xform is defined by the application of an operator ((>>) in this case)

then you're out of luck; xform's body is not a generalizable expression (see §14.7 in the F# spec), so the value restriction applies here.

Furthermore, I would argue that this makes sense. Imagine that the value restriction didn't apply, and that we tweaked the definition of map:

let map proj : Reducer<_,_,_> =
    printfn "Map called!"
    fun xf result input ->
        xf result (proj input)

Now enter these definitions one-by-one:

let xform<'a> : Reducer<'a,int,int> = map (fun i -> i + 9) >> map (fun a -> a * 5)

let x1 = xform (+)
let x2 = xform (*)
let x3 = xform (fun s i -> String.replicate i s)

When do you expect "Map called!" to be printed? Does the actual behavior match your expectations? In my opinion it's good that F# forces you to go out of your way to treat non-values as generic values.

So you're not going to get exactly what you want. But perhaps there's a different encoding that would work just as well for your use cases. If every reducer will be generic in the result type, then you could do this instead:

type Reducer<'b,'c> = abstract Reduce<'a> : ('a -> 'b -> 'a) -> 'a -> 'c -> 'a

module Transducers =
    let map proj =
        { new Reducer<_,_> with 
            member this.Reduce xf result input = xf result (proj input) }

    let (>!>) (r1:Reducer<'b,'c>) (r2:Reducer<'c,'d>) =
        { new Reducer<_,_> with 
            member this.Reduce xf result input = (r1.Reduce >> r2.Reduce) xf result input }

    let conj xs x = x :: xs
    let toList (xf:Reducer<_,_>) input = List.fold  (xf.Reduce conj) [] input

    let xform = map (fun i -> i + 9) >!> map (fun a -> a * 5)

Unfortunately, you've got to lift each operator like (>>) to the reducer level before you can use it, but this at least works for your example, since xform is no longer a generic value, but a non-generic value with a generic method.