是否可以在 F# 中递归具有不同泛型参数的类型层次结构？

Question

假设我有以下 F# 代码：

[<AbstractClass>]
type Base<'a>() =
    class end
and Test<'a, 'b>(b: Base<'b>, c: 'b -> 'a) =
    inherit Base<'a>()
    member this.B = b
    member this.C = c

let rec test (b : Base<'a>) : _ =
    match b with
    | :? Test<'a, 'b> as t -> let result = test t.B
                                test (t.C result)
    | _                    -> failwith "Not supported!"

基本上，我想递归一个类型（在本例中为 Base<'b>），其通用参数不同于我当前在当前函数调用中使用的参数（在本例中为 Base<'a>这个案例）。例如，在代码中我在一些 Base<'a> b 上进行模式匹配，它可能是 Test 的一个实例，这意味着我在一个函数中当前使用 Base<'a> 调用。

测试模式匹配，我想递归它是 Base<'b> 的字段 b，即 Base 的实例可能具有与 'a 不同的通用参数。但是，当我这样做时，在 (test t.B) 的线上，我收到以下警告，这完全破坏了我正在尝试做的事情：

Warning FS0064: This construct causes code to be less generic than indicated by the type annotations. The type variable 'a has been constrained to be type 'b.

我的问题：是否可以在 F# 中以某种方式解决这个 constraint/warning？我不明白为什么对 t.B 的递归调用（让结果 = 测试 t.B）会导致 'a 与 'b 的类型相同。我需要两者能够与我正在尝试做的事情有所不同。

谢谢。

编辑：添加了给出此问题的实际代码（位于：return NaiveEval con.Eff）：

   type Channel<'a>() =
        let queue = ConcurrentQueue<'a>()
    
        member internal this.Send value =
                queue.Enqueue value
    
        member internal this.Receive =
                let status, value = queue.TryDequeue()
                if status then value else this.Receive

    [<AbstractClass>]
    type Effect<'Result>() =
        class end
    and Input<'Result>(chan : Channel<'Result>, cont : 'Result -> Effect<'Result>) = 
        inherit Effect<'Result>()
        member internal this.Chan = chan
        member internal this.Cont = cont
    and Output<'Result>(value : 'Result, chan : Channel<'Result>, cont : unit -> Effect<'Result>) =
        inherit Effect<'Result>()
        member internal this.Value = value
        member internal this.Chan = chan
        member internal this.Cont = cont
    and Concurrent<'Result, 'Async>(eff: Effect<'Async>, cont: Async<'Async> -> Effect<'Result>) = 
        inherit Effect<'Result>()
        member internal this.Eff = eff
        member internal this.Cont = cont
    and Await<'Result, 'Async>(future: Async<'Async>, cont: 'Async -> Effect<'Result>) =
        inherit Effect<'Result>()
        member internal this.Future = future
        member internal this.Cont = cont
    and Return<'Result>(value : 'Result) =
        inherit Effect<'Result>()
        member internal this.Value = value

    let Send(value, chan, cont) = Output(value, chan, cont)
    let Receive(chan, cont) = Input(chan, cont)
    
    let rec NaiveEval (eff : Effect<'Result>) : 'Result =
        match eff with
        | :? Input<'Result> as input             -> let value = input.Chan.Receive
                                                    NaiveEval <| input.Cont value
        | :? Output<'Result> as output           -> output.Chan.Send output.Value
                                                    NaiveEval <| output.Cont ()
        | :? Concurrent<'Result, 'Async> as con  -> let work = async {
                                                        return NaiveEval con.Eff
                                                    }
                                                    let task = Async.AwaitTask <| Async.StartAsTask work
                                                    NaiveEval <| con.Cont task
        | :? Await<'Result, 'Async> as await     -> let res = Async.RunSynchronously await.Future
                                                    NaiveEval <| await.Cont res
        | :? Return<'Result> as ret              -> ret.Value
        | _                                      -> failwith "Unsupported effect!"

Answer 1

这里有几个问题：

您不能对具有自由类型参数的类型进行模式匹配 - 因此 :? Test<'a, 'b> as t 将不起作用 - 理想情况下，这将匹配任何 Test 并设置 'a 和 'b 到正确的类型，但这不是模式匹配的工作方式（编译器必须知道类型参数）。
您还试图拥有一个使用不同类型参数调用自身的递归函数，这在 F# 中也是不允许的。

您可以想出各种或多或少优雅的解决方法。以下是一种选择：

type IOperation = 
  abstract Invoke : Test<'a, 'b> -> unit

and [<AbstractClass>] Base() = 
  abstract Invoke : IOperation -> unit

and [<AbstractClass>] Base<'a>() = 
  inherit Base()

and Test<'a, 'b>(b: Base<'b>, c: 'b -> 'a) =
  inherit Base<'a>()
  member this.B = b
  member this.C = c
  override this.Invoke(op) =
    op.Invoke(this)

let rec test (b : Base) : _ =
    b.Invoke
      ({ new IOperation with 
          member x.Invoke<'b, 'c>(t:Test<'b, 'c>) = 
            test t.B
      })

它添加了一个非泛型 Base（以便您可以编写递归 test 函数），然后它有一个采用 IOperation 的调用方法。然后，它有一个通用的 Invoke 方法，该方法通过 Test.

中的实现使用 Test<'b, 'c> 调用 - 使用正确的类型参数

我认为这可能会让你做你需要做的事 - 但如果不知道你具体想做什么就很难说！

Answer 2

好的，经过大量的实验，我终于能够解决这个问题。感谢@TomasPetricek，我已经成功地建立了一种允许我尝试做的访问者模式。

type EffectVisitor =
    abstract member VisitInput<'Result> : Input<'Result> -> 'Result
    abstract member VisitOutput<'Result> : Output<'Result> -> 'Result
    abstract member VisitConcurrent<'Result, 'Async> : Concurrent<'Result, 'Async> -> 'Result
    abstract member VisitAwait<'Result, 'Async> : Await<'Result, 'Async> -> 'Result
    abstract member VisitReturn<'Result> : Return<'Result> -> 'Result
and [<AbstractClass>] Effect() =
    abstract member Visit : EffectVisitor -> 'Result
and [<AbstractClass>] Effect<'Result>() =
    abstract member Visit<'Result> : EffectVisitor -> 'Result
and Input<'Result>(chan : Channel<'Result>, cont : 'Result -> Effect<'Result>) =
    inherit Effect<'Result>()
    member internal this.Chan = chan
    member internal this.Cont = cont
    override this.Visit<'Result>(input) =
    input.VisitInput<'Result>(this)
and Output<'Result>(value : 'Result, chan : Channel<'Result>, cont : unit -> Effect<'Result>) =
    inherit Effect<'Result>()
    member internal this.Value = value
    member internal this.Chan = chan
    member internal this.Cont = cont
    override this.Visit<'Result>(input) =
    input.VisitOutput<'Result>(this)
and Concurrent<'Result, 'Async>(eff : Effect<'Async>, cont : Async<'Async> -> Effect<'Result>) =
    inherit Effect<'Result>()
    member internal this.Eff = eff
    member internal this.Cont = cont
    override this.Visit<'Result>(con) =
        con.VisitConcurrent<'Result, 'Async>(this)
and Await<'Result, 'Async>(task : Async<'Async>, cont : 'Async -> Effect<'Result>) =
    inherit Effect<'Result>()
    member internal this.Task = task
    member internal this.Cont = cont
    override this.Visit<'Result>(await) =
        await.VisitAwait<'Result, 'Async>(this)
and Return<'Result>(value : 'Result) =
    inherit Effect<'Result>()
    member internal this.Value = value
    override this.Visit<'Result>(input) =
        input.VisitReturn<'Result>(this)

let Send(value, chan, cont) = Output(value, chan, cont)
let Receive(chan, cont) = Input(chan, cont)

let rec NaiveEval<'Result> (eff : Effect<'Result>) : 'Result =
    eff.Visit({
        new EffectVisitor with
            member _.VisitInput<'Result>(input : Input<'Result>) : 'Result =
                let value = input.Chan.Receive
                NaiveEval <| input.Cont value
            member _.VisitOutput<'Result>(output : Output<'Result>) : 'Result =
                output.Chan.Send output.Value
                NaiveEval <| output.Cont ()
            member _.VisitConcurrent(con) =
                let work = async {
                    return NaiveEval con.Eff
                }
                let task = Async.AwaitTask <| Async.StartAsTask work
                NaiveEval <| con.Cont task
            member _.VisitAwait(await) =
                let result = Async.RunSynchronously await.Task
                NaiveEval <| await.Cont result
            member this.VisitReturn<'Result>(ret : Return<'Result>) : 'Result =
                ret.Value
    })

是否可以在 F# 中递归具有不同泛型参数的类型层次结构？

Is it possible to recurse on a type hierarchy with distinct generic parameters in F#?

generics

recursion

parameters

f#

warnings