如何在F#中实现“高效广义折叠”？

Question

在 paper of Martin et al. 中，我读到了关于嵌套数据类型的高效广义折叠。论文讲的是Haskell，想在F#中试试

到目前为止，我设法遵循 Nest 示例，包括 gfold.

的实施

type Pair<'a> = 'a * 'a
type Nest<'a> = Nil | Cons of 'a * Nest<Pair<'a>>

let example =
    Cons(1,
        Cons((2, 3),
            Cons(((4, 5), (6, 7)),
                Nil
            )
        )
    )

let pair (f:'a -> 'b) ((a, b):Pair<'a>) : Pair<'b> = f a, f b

let rec nest<'a, 'r> (f:'a -> 'r) : Nest<'a> -> Nest<'r> = function
    | Nil -> Nil
    | Cons(x, xs) -> Cons(f x, nest (pair f) xs)

//val gfold : e:'r -> f:('a * 'r -> 'r) -> g:(Pair<'a> -> 'a) -> _arg1:Nest<'a> -> 'r
let rec gfold e f g : Nest<'a> -> 'r = function
    | Nil -> e
    | Cons(x, xs) ->
        f(x, gfold e f g (nest g xs))

let uncurry f (a, b) = f a b

let up = uncurry (+)

let sum = example |> gfold 0 up up

不幸的是，gfold 似乎具有二次复杂度，这就是作者想出 efold 的原因。正如您可能猜到的那样，那是我无法开始工作的那个。在摆弄了许多类型注释之后，我想出了这个版本，它只剩下一个小小的波浪线：

let rec efold<'a, 'b, 'r> (e:'r) (f:'a * 'r -> 'r) (g:(Pair<'a> -> Pair<'a>) -> 'a -> 'a) (h:_) (nest:Nest<'a>) : 'r =
    match nest with
    | Nil -> e
    | Cons(x, xs) -> f(h x, efold e f g ((g << pair) h) xs)
                                                        ^^

唯一剩下的未指定类型是 h 中的一种。编译器推断 val h : ('a -> 'a) 但我认为需要有不同的类型。

提供的错误消息显示为

Error Type mismatch. Expecting a
Nest<'a>
but given a
Nest<Pair<'a>>
The resulting type would be infinite when unifying ''a' and 'Pair<'a>'

使用正确的 h 类型，错误应该消失。但我对 Haskell 的理解还不够，无法将其翻译成 F#。

另请参阅 this discussion 了解论文中可能出现的拼写错误。

更新： 这是我从kvb的回答中了解到的：

所以 h 将输入类型转换为中间类型，就像在累加器可能是不同类型的常规折叠中一样。 g 然后用于将两个中间类型值减少为一个，而 f 获取中间类型和输入类型以生成输出类型值。当然e也是那种输出类型。

h 确实直接应用于递归过程中遇到的值。另一方面，g 仅用于使 h 适用于逐渐更深的类型。

只看第一个 f 示例，除了应用 h 和推动递归之外，它本身似乎没有做太多工作。但在复杂的方法中，我可以看到它是最重要的方法。结果是什么，即它是工作马。

差不多吧？

Answer 1

Haskell 中 efold 的正确定义是这样的：

efold :: forall n m b.
    (forall a. n a)->
    (forall a.(m a, n (Pair a)) -> n a)->
    (forall a.Pair (m a) -> m (Pair a))->
    (forall a.(a -> m b) -> Nest a -> n b) 
efold e f g h Nil = e 
efold e f g h (Cons (x,xs)) = f (h x, efold e f g (g . pair h) xs

这不能完全通用地转换为 F#，因为 n 和 m 是 "higher-kinded types" - 它们是在给定参数时创建类型的类型构造函数 - 这不是在 F# 中不受支持（并且在 .NET 中没有清晰的表示）。

解读

您的更新询问如何解释折叠的参数。了解折叠如何工作的最简单方法可能是扩展将折叠应用于示例时发生的情况。你会得到这样的东西：

efold e f g h example ≡
    f (h 1, f ((g << pair h) (2, 3), f ((g << pair (g << pair h)) ((4,5), (6,7)), e)))

所以 h 将值映射到可以用作 f 的类型的第一个参数。 g 用于将 h 应用于更深的嵌套对（这样我们就可以从使用 h 作为类型 a -> m b 的函数到 Pair a -> m (Pair b) 再到 Pair (Pair a) -> m (Pair (Pair b)) 等），并且 f 被重复应用到书脊上以将 h 的结果与对 f 的嵌套调用的结果组合起来。最后，e 仅使用一次，作为对 f.

最深层嵌套调用的种子

我认为这个解释与您的推论基本一致。 f 对于组合不同层的结果当然是至关重要的。但是 g 也很重要，因为它告诉你如何在一个层中组合各个部分（例如，当对节点求和时，它需要对左右嵌套总和进行求和；如果你想使用折叠来构建一个新嵌套，其中每个级别的值都与输入值相反，您可以使用 g，它看起来大致类似于 fun (a,b) -> b,a).

简单的方法

一种选择是为您关心的每个 n、m 对创建 efold 的专门实现。例如，如果我们想要对包含在 Nest 中的列表的长度求和，那么 n _ 和 m _ 都将是 int。我们可以稍微概括一下 n _ 和 m _ 不依赖于它们的参数的情况：

let rec efold<'n,'m,'a> (e:'n) (f:'m*'n->'n) (g:Pair<'m> -> 'm) (h:'a->'m) : Nest<'a> -> 'n = function
| Nil -> e
| Cons(x,xs) -> f (h x, efold e f g (g << (pair h)) xs)

let total = efold 0 up up id example

另一方面，如果 n 和 m 确实使用它们的参数，那么您需要定义一个单独的特化（另外，您可能需要为每个多态创建新类型参数，因为 F# 对 higher-rank 类型的编码很笨拙）。例如，要将嵌套的值收集到列表中，您需要 n 'a = list<'a> 和 m 'b = 'b。然后我们可以观察到类型 forall 'a.list<'a> 的唯一值是 []，而不是为 e 的参数类型定义新类型，因此我们可以写：

type ListIdF =
    abstract Apply : 'a * list<Pair<'a>> -> list<'a>

type ListIdG =
    abstract Apply : Pair<'a> -> Pair<'a>

let rec efold<'a,'b> (f:ListIdF) (g:ListIdG) (h:'a -> 'b) : Nest<'a> -> list<'b> = function
| Nil -> []
| Cons(x,xs) -> f.Apply(h x, efold f g (pair h >> g.Apply) xs)

let toList n = efold { new ListIdF with member __.Apply(a,l) = a::(List.collect (fun (x,y) -> [x;y]) l) } { new ListIdG with member __.Apply(p) = p } id n

复杂的方法

虽然 F# 不直接支持更高种类的类型，但事实证明可以以某种忠实的方式模拟它们。这是 Higher 库采用的方法。这是它的最小版本。

我们创建一个类型 App<'T,'a>，它将代表某种类型应用程序 T<'a>，但是我们将在其中创建一个虚拟伴随类型，它可以作为 App<_,_> 的第一个类型参数:

type App<'F, 'T>(token : 'F, value : obj) = 
    do
        if obj.ReferenceEquals(token, Unchecked.defaultof<'F>) then
            raise <| new System.InvalidOperationException("Invalid token")

    // Apply the secret token to have access to the encapsulated value
    member self.Apply(token' : 'F) : obj =
        if not (obj.ReferenceEquals(token, token')) then
            raise <| new System.InvalidOperationException("Invalid token")
        value

现在我们可以为我们关心的类型构造函数定义一些伴随类型（这些通常可以存在于一些共享库中）：

// App<Const<'a>, 'b> represents a value of type 'a (that is, ignores 'b)
type Const<'a> private () =
    static let token = Const ()
    static member Inj (value : 'a) =
        App<Const<'a>, 'b>(token, value)
    static member Prj (app : App<Const<'a>, 'b>) : 'a =
        app.Apply(token) :?> _

// App<List, 'a> represents list<'a>
type List private () = 
    static let token = List()
    static member Inj (value : 'a list) =
        App<List, 'a>(token, value)
    static member Prj (app : App<List, 'a>) : 'a list =
        app.Apply(token) :?> _

// App<Id, 'a> represents just a plain 'a
type Id private () =
    static let token = Id()
    static member Inj (value : 'a) =
        App<Id, 'a>(token, value)
    static member Prj (app : App<Id, 'a>) : 'a =
        app.Apply(token) :?> _

// App<Nest, 'a> represents a Nest<'a>
type Nest private () =
    static let token = Nest()
    static member Inj (value : Nest<'a>) =
        App<Nest, 'a>(token, value)
    static member Prj (app : App<Nest, 'a>) : Nest<'a> =
        app.Apply(token) :?> _

现在我们可以一劳永逸地为有效折叠的参数定义更高级别的类型：

// forall a. n a
type E<'N> =
    abstract Apply<'a> : unit -> App<'N,'a>

// forall a.(m a, n (Pair a)) -> n a)
type F<'M,'N> =
    abstract Apply<'a> : App<'M,'a> * App<'N,'a*'a> -> App<'N,'a>

// forall a.Pair (m a) -> m (Pair a))
type G<'M> =
    abstract Apply<'a> : App<'M,'a> * App<'M,'a> -> App<'M,'a*'a>

所以弃牌就是：

let rec efold<'N,'M,'a,'b> (e:E<'N>) (f:F<'M,'N>) (g:G<'M>) (h:'a -> App<'M,'b>) : Nest<'a> -> App<'N,'b> = function
| Nil -> e.Apply()
| Cons(x,xs) -> f.Apply(h x, efold e f g (g.Apply << pair h) xs)

现在要调用 efold，我们需要对各种 Inj 和 Prj 方法进行一些调用，但除此之外一切看起来都与我们预期的一样：

let toList n = 
    efold { new E<_> with member __.Apply() = List.Inj [] } 
          { new F<_,_> with member __.Apply(m,n) = Id.Prj m :: (n |> List.Prj |> List.collect (fun (x,y) -> [x;y])) |> List.Inj }
          { new G<_> with member __.Apply(m1,m2) = (Id.Prj m1, Id.Prj m2) |> Id.Inj }
          Id.Inj
          n
    |> List.Prj

let sumElements n =
    efold { new E<_> with member __.Apply() = Const.Inj 0 }
          { new F<_,_> with member __.Apply(m,n) = Const.Prj m + Const.Prj n |> Const.Inj }
          { new G<_> with member __.Apply(m1,m2) = Const.Prj m1 + Const.Prj m2 |> Const.Inj }
          Const.Inj
          n
    |> Const.Prj

let reverse n = 
    efold { new E<_> with member __.Apply() = Nest.Inj Nil }
          { new F<_,_> with member __.Apply(m,n) = Cons(Id.Prj m, Nest.Prj n) |> Nest.Inj }
          { new G<_> with member __.Apply(m1,m2) = (Id.Prj 2, Id.Prj m1) |> Id.Inj }
          Id.Inj
          n
    |> Nest.Prj

希望这里的模式是清晰的：在每个对象表达式中，应用程序方法投射出每个参数，对它们进行操作，然后将结果注入回 App<_,_> 类型。通过一些 inline 魔法，我们可以使它看起来更加一致（以一些类型注释为代价）：

let inline (|Prj|) (app:App< ^T, 'a>) = (^T : (static member Prj : App< ^T, 'a> -> 'b) app)
let inline prj (Prj x) = x
let inline inj x = (^T : (static member Inj : 'b -> App< ^T, 'a>) x)

let toList n = 
    efold { new E<List> with member __.Apply() = inj [] } 
          { new F<Id,_> with member __.Apply(Prj m, Prj n) = m :: (n |> List.collect (fun (x,y) -> [x;y])) |> inj }
          { new G<_> with member __.Apply(Prj m1,Prj m2) = (m1, m2) |> inj }
          inj
          n
    |> prj

let sumElements n =
    efold { new E<Const<_>> with member __.Apply() = inj 0 }
          { new F<Const<_>,_> with member __.Apply(Prj m, Prj n) = m + n |> inj }
          { new G<_> with member __.Apply(Prj m1,Prj m2) = m1 + m2 |> inj }
          inj
          n
    |> prj

let reverse n = 
    efold { new E<_> with member __.Apply() = Nest.Inj Nil }
          { new F<Id,_> with member __.Apply(Prj m,Prj n) = Cons(m, n) |> inj }
          { new G<_> with member __.Apply(Prj m1,Prj m2) = (m2, m1) |> inj }
          inj
          n
    |> prj

如何在F#中实现“高效广义折叠”？

How to implement “efficient generalized fold” in F#?

f#

nested

polymorphism

fold

recursive-type

解读

简单的方法

复杂的方法