Haskell的平等效率 [英] Efficiency of equality in Haskell

问题描述

我有一个可以接收数据并返回相同数据或稍作修改的版本的函数.

I've got a function that takes data and either returns the same data or a slightly modified version.

如果程序更改，我想让我做一件事，如果程序不变，我想让我做另一件事.

I want to have my program do one thing if it changed or another thing if it did not change.

以前，我是返回一对(Bool,Object)，并使用fst来检查它是否已更改.最近，我想到我可以简化代码，只需返回对象并使用==检查相等性即可.

Previously I was returning a pair (Bool,Object) and using fst to check if it changed. Lately it occurred to me that I could simplify the code by just returning the object and checking equality using ==.

但是后来我意识到Haskell不会区分深度相等检查和对象身份"(即指针相等).那么我怎么知道使用==是否会有效呢?我是否应该出于效率原因而避免使用它，还是在某些情况下可以依靠编译器来确定它不需要进行深入的相等性检查?

But then I realized that Haskell doesn't differentiate between deep equality checking and "object identity" (i.e., pointer equality). So how can I know whether using == is going to be efficient or not? Should I avoid it for efficiency reasons, or are there cases where I can depend on the compiler figuring out that it doesn't need to do a deep equality check?

通常，在编写初始程序时，我不会太担心效率，但是这会影响模块的接口，因此我想在编写太多代码之前就把它弄清楚，而且这样做似乎不值得仅仅一小段代码，该程序的效率就会大大降低.此外，我想更好地了解我可以依靠GHC进行什么样的优化.

Normally I wouldn't be too worried about efficiency while writing an initial program, but this affects the interface to my module so I want to get it right before writing too much code, and it doesn't seem worth it to make the program much less efficient just to simply a small piece of code. Moreover, I'd like to get a better idea of what kind of optimizations I can depend on GHC to help me with.

推荐答案

依靠不确定的编译器优化来提供诸如恒定时间相等与线性时间深度相等之类的重要性能保证，始终是个坏主意.使用封装了值以及有关该值是否为新值的信息的新类型，您会更好.取决于您的应用，可以是

It's always a bad idea to rely on uncertain compiler optimizations to provide such an important performance guarantee as constant-time equality vs linear-time deep equality. You're much better off with a new type that encapsulates a value plus information about whether the value is new. Depending on your application this can be either

data Changed a = Changed a | Unchanged a

或

data Changed a = Changed a | Unchanged

我们实际上在Glasgow Haskell编译器中使用了类似的类型，因此我们可以继续运行优化器，直到代码停止更改为止.我们还将运行迭代数据流分析，直到结果停止更改为止.

We actually use a similar type inside the Glasgow Haskell Compiler so we can keep running the optimizer until the code stops changing. We also run iterative dataflow analysis until the results stop changing.

我们发现将此类型设置为monad很有用，这样我们就可以使用do表示法编写一些简单的高阶函数，但这不是必需的，只是为了方便.

We found it useful to make this type a monad so that we can write some simple higher-order functions using do notation, but it's not necessary—just a convenience.

摘要::如果您要进行定期检查，请自己编写代码-不要依赖可能没有的编译器优化，或者在下一个发行版中可能会更改.

Summary: If you want constant-time checking, code it yourself—don't rely on a possible compiler optimization which might not be there—or which might change in the next release.

这篇关于Haskell的平等效率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！