F# generic constraint union type

Question

I have been working with F# for a few months but did not find any satisfying solution for my problem. I would like to describe a succession of operations as a discriminated union of values, or operations on these values. In this way, my type Val<'o> is defined as follow:

type Val<'o> =
    | Val of 'o
    | Func1 of ('a->'o) * Val<'a>
    | Func2 of ('a->'b->'o) * Val<'a> * Val<'b>

The type Val<'o> can be converted into a 'o type by recursively applying all operations, and still keep the list of operations.

But I can't define the generic types 'a and 'b and their constraints if I don't use Val<'a,'b,'o>. If I do, I have to define the sub-Val generic types, which I want to stay generic:

type Val<'a, 'b, 'o> =
    | Val of 'o
    | Func1 of ('a->'o) * Val<?, ?, 'a>
    | Func2 of ('a->'b->'o) * Val<?, ?, 'a> * Val<?, ?, 'b>

Is there any F# structure that could be adapted for this issue?

Many thanks

[edit]

To describe my problem further, I am trying to get an exhaustive representation of a FRP structure (but the genericity problem is the same for events/signals that for values).
The representation could be either serialized for database storage, translated into text for display and user edit or evaluated to get a result:

"Func (x -> x²) (Val(3.4))" <--> representation <--> 11.56
             |
            user 

I made a prototype working quite well using a PrimitiveValue union type, and functions strings compiled at runtime into generic obj[] -> obj functions, but evaluation is very heavy on type checking and casting (especially because I am also using arrays and options in PrimitiveValue), so I was looking for a more elegant and strongly-typed solution.

Answer 1

The basic problem here is that F# does not let you say that the 'a and 'b in the case of the discriminated union are "parameters" of the data stored in the case. Some other languages support this (it's called generalized algebraic data types in Haskell), but there is a usual trade-off of making the language more complicated.

You can actually emulate this in F#, but it is ugly - so I would think twice before going that way. The idea is that you can define an interface with a generic method that gets invoked with the appropriate type arguments 'a and 'b.

type Val<'T> =
  | Val of 'T
  | Func of IFunc<'T>

and IFunc<'T> = 
  abstract Invoke<'R> : IFuncOperation<'T, 'R> -> 'R

and IFuncOperation<'T2, 'R> =
  abstract Invoke<'T1> : ('T1 -> 'T2) * Val<'T1> -> 'R

The value wrapped in Func can be given IFuncOperation and it will invoke it with your 'a being the type argument of the generic method - the 'T1 in my naming.

You can make construction of the values reasonably nice:

let makeFunc f v =
  Func({ new IFunc<_> with member x.Invoke(op) = op.Invoke(f, v) })    
let makeVal v = Val(v)

let valString = makeFunc (fun n -> sprintf "Got: %d" n) (makeVal 42)

Now, valString represents a int -> string transformation applied to Val<int>.

The code you need to write to do pattern matching on Func is pretty ugly though:

let rec eval<'T> (value:Val<'T>) : 'T = 
  match value with
  | Val r -> r
  | Func f -> 
      { new IFuncOperation<'T, 'T> with
          member x.Invoke<'S>(f, value:Val<'S>) = f (eval<'S> value) }
      |> f.Invoke

eval valString

I have used similar pattern in some of the internals of Deedle, but never in code that would be even close to what end users would write. I think this is acceptable at some very well hidden internal level, but I would definitely avoid using it in something that's called frequently.

Depending on what your original problem was, there is probably a nicer way - you could define a discriminated union PrimitiveValue to hold the various primitive values that your computation can produce, or you could just represent the operations using an interface - but it's hard to say what is better in your case without knowing the context.