函数的有效表示
功能类型A-> B从某种意义上来说并不是很好。尽管函数是一等值，但由于效率问题，人们常常无法自由地操作它们。您不能应用太多转换 (A -> B) -> (C -> D)，在某些时候你必须计算一个值。
显然，这是由于 -> 的非严格性质所致。 。
有一些众所周知的技巧来处理 Double 类型的函数 ->双倍的。人们可以将它们表示为给定基础的向量，向量可以由三角函数、多项式等组成。
是否有任何通用技巧可以解决 A -> 的低效率问题。 B型？
或者 -> 的替代方案？
Function type A -> B in some sense is not very good. Though functions are first class values, one often cannot freely operate them due to efficiency problems. You can't apply too many transformations (A -> B) -> (C -> D), at some point you have to compute a value.
Obviously this is due to the non-strict nature of -> .
There are well know tricks to deal with functions of type Double -> Double. One can represent them as vectors given a certain basis, which can consist of trig functions, polynomials etc.
Are there any general tricks to get round the inefficiency of the A -> B type?
Or alternatives to -> ?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
您似乎担心的是，给定
h === f • g，f • g通常比h效率低。给定编译时已知的函数组合，编译器执行两个技巧可以使f • g比您想象的更高效 - 内联和融合。内联避免了第二次函数调用的额外间接，并开辟了许多新的优化机会。流融合（或构建/折叠融合）可以（举一个基本示例）转变诸如map f 之类的组合。将 g映射到map (f . g)从而将结构体的遍历次数减少一个常数因子。 Fusion 不仅可以在列表上运行，还可以在其他结构上运行，并且为 Haskell 库（例如Vector）的高效性能提供了一个原因。快捷融合： http://www.haskell.org/haskellwiki/Correctness_of_short_cut_fusion
流融合： 什么是Haskell 的流融合
Your concern seems to be that given
h === f • g,f • gis typically less efficient thanh. Given a composition of functions known at compile time, there are two tricks performed by the compiler which can renderf • gmore efficient than you would suspect -- inlining, and fusion. Inlining avoids the extra indirection of a second function call, and opens up many new opportunities for optimizations. Stream fusion (or build/foldr fusion) can (to give a basic example) turn compositions such asmap f . map gintomap (f . g)thereby reducing the number of traversals of a structure by a constant factor. Fusion operates not only on lists, but other structures, and provides one reason for the efficient performance of Haskell libraries such asVector.Short cut fusion: http://www.haskell.org/haskellwiki/Correctness_of_short_cut_fusion
Stream fusion: What is Haskell's Stream Fusion
我无法证实这一点。作为 AFRP 的高效用户和实现者，我对完全多态函数进行大量转换，深度嵌套并针对长时间运行的应用程序。请注意，Haskell 编译器不使用传统的基于堆栈的函数调用范例。他们使用图缩减算法。我们没有像 C 那样的问题。
I cannot confirm this. As a productive user and implementor of AFRP, I am performing transformations on fully polymorphic functions a lot, deeply nested and for long running applications. Note that Haskell compilers do not use the traditional stack-based function calling paradigm. They use graph reduction algorithms. We don't have the same problems as, say, C.
最常见的技巧之一是记忆——在计算函数值后存储它。链接：Haskellwiki、示例，MemoCombinators。正如您所提到的，另一个技巧是当您有一个很好的函数类型（多项式、向量、泰勒级数等）时，那么它可以表示为列表、表达式等。
One of the most general tricks is memoization - storing the value of a function after you computed it. Links: Haskellwiki, SO example, MemoCombinators. As you mentioned, the other trick is when you have a nice type of function (polynomial, vector, Taylor series etc.) - then it can be represented as a list, expression etc.
FWIW：在 Felix 中，它是一个严重依赖内联来提高性能的整个程序分析器，函数参数分为三种：eager、lazy 或“让编译器决定”。
在计算函数体之前，将对热切参数进行计算并将其分配给变量。
惰性参数的计算方法是用参数表达式替换出现的参数。
默认是“让编译器决定”。对于大量“普通”代码（无论这意味着什么），无论使用急切求值还是惰性求值都没有任何区别。
一般来说，在 Felix 中，惰性求值速度更快：请仔细注意，这并不意味着闭包。意思是内联。然而有时编译器会选择急切求值，它会减少代码膨胀，而过多的内联会适得其反。我并不声称该算法有任何好处..但是 Felix 有时可以超越 C 和 Ocaml（GHC 没有进入决赛）。
作为一个简单的例子..类型类。 Felix 有类型类，有点像 Haskell。没有或很少的性能开销..当然没有字典！
在我看来，如果你抛弃了单独编译的陈旧概念，Haskell 会好得多：整个程序分析器可以做更多的事情，并且处理文本比对象代码要快得多（考虑到缓存编译的完全自由）结果）。让一种惰性语言使用专为急切求值而设计的编译模型真是太疯狂了！
Haskell 变体可能尝试的另一件事是放弃所有函数都是惰性函数的想法，而是采用评估策略不相关的想法，除非另有说明。这可能会带来更多的优化机会。
FWIW: In Felix, which is a whole program analyser relying heavily on inlining for performance, function arguments have three kinds: eager, lazy, or "let the compiler decide".
Eager arguments are evaluated and assigned to variable before the body of the function is evaluated.
Lazy arguments are evaluated by replacing the parameter with the argument expression wherever it occurs.
The default is "let the compiler decide". For a large amount of "ordinary" code (whatever that means) it doesn't make any difference whether you use eager or lazy evaluation.
Generally in Felix lazy evaluation is faster: note carefully this does NOT mean closures. It means inlining. However sometimes the compiler will chose eager evaluation, it reduces code bloat, and too much inlining is counter productive. I make no claim the algorithm is any good .. however Felix can sometimes outperform C and Ocaml (GHC didn't get into the finals).
As a simple example .. type classes. Felix has typeclasses, sort of like Haskell. No or very little performance overhead .. certainly no dictionaries!
In my view, Haskell would be a lot better if you just chucked out the archaic concept of separate compilation: whole program analysers can do so much more, and text is much faster to work with than object code (given the complete freedom to cache compilation results). It's crazy to have a lazy language use a compilation model designed for eager evaluation!
The other thing a Haskell variant might try is to drop the idea all functions are lazy, and instead adopt the idea that the evaluation strategy is irrelevant, unless otherwise specified. That may allow a lot more optimisation opportunities.