作者热门文章
- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
在 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#。
h
将输入类型转换为中间类型,就像在累加器可能是不同类型的常规折叠中一样。
g
然后用于将两个中间类型值减少为一个,而
f
获取中间类型和输入类型以生成输出类型值。当然
e
也是那种输出类型。
h
确实直接应用于递归期间遇到的值。
g
另一方面,仅用于使 h 适用于越来越深的类型。
f
例如,除了应用
h
之外,它本身似乎并没有做太多工作。并助长递归。但是在复杂的方法中,我可以看到它是最重要的方法。结果是什么,即它是工作马。
最佳答案
efold
的正确定义在 Haskell 中是这样的:
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
n
和
m
是“高级类型”——它们是在给定参数时创建类型的类型构造函数——在 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
)。
efold
的专用实现。对于每个
n
,
m
你关心的一对。例如,如果我们想对
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# 对更高级别类型的编码很尴尬)。例如,要将巢的值收集到您想要的列表中
n 'a
=
list<'a>
和
m 'b
=
'b
.然后不是为
e
的参数类型定义新类型我们可以观察到
forall 'a.list<'a>
类型的唯一值是
[]
,所以我们可以写:
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
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# - 如何在 F# 中实现 “efficient generalized fold”?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40659910/
我是一名优秀的程序员,十分优秀!