9

我目前正在学习 Haskell，有一件事情让我感到困惑：

当我构建一个复杂的表达式（其计算需要一些时间）并且该表达式是常量（意味着它仅由已知的硬编码值构建）时，不会在编译时评估该表达式。

来自 C/C++ 背景，我习惯了这种优化。

在 Haskell / GHC 中不执行此类优化（默认情况下）的原因是什么？有什么好处，如果有的话？

data Tree a =
   EmptyTree
 | Node a (Tree a) (Tree a)
 deriving (Show, Read, Eq)

elementToTree :: a -> Tree a
elementToTree x = Node x EmptyTree EmptyTree

treeInsert :: (Ord a) => a -> Tree a -> Tree a
treeInsert x EmptyTree = elementToTree x
treeInsert x (Node a left right)
  | x == a = Node x left right
  | x < a  = Node a (treeInsert x left) right
  | x > a  = Node a left (treeInsert x right)

treeFromList :: (Ord a) => [a] -> Tree a
treeFromList []     = EmptyTree
treeFromList (x:xs) = treeInsert x (treeFromList xs)

treeElem :: (Ord a) => a -> Tree a -> Bool
treeElem x EmptyTree = False
treeElem x (Node a left right)
  | x == a = True
  | x < a  = treeElem x left
  | x > a  = treeElem x right

main = do
  let tree = treeFromList [0..90000]
  putStrLn $ show (treeElem 3 tree)

由于这将始终打印True，我希望编译后的程序几乎立即打印并退出。

4

3 回答 3

15

你可能会喜欢这个 reddit 线程。编译器可以尝试这样做，但这可能很危险，因为任何类型的常量都可以做一些有趣的事情，比如循环。至少有两种解决方案：一种是超级编译，目前还没有作为任何编译器的一部分提供，但您可以尝试各种研究人员的原型；更实用的一种是使用 Template Haskell，这是 GHC 让程序员在编译时要求运行一些代码的机制。

于 2013-10-09T00:35:36.310 回答
3

您正在谈论的过程称为超级编译，它比您想象的要困难。它实际上是计算科学中活跃的研究课题之一！有一些人正在尝试为 Haskell 创建这样的超级编译器（可能基于 GHC，我的记忆很模糊），但该功能尚未包含在 GHC 中，因为维护人员希望缩短编译时间。您提到 C++ 是一种可以做到这一点的语言——C++ 的编译时间也是出了名的糟糕！

Haskell 的替代方法是使用 Template Haskell 手动进行优化，这是 Haskells 编译时评估的宏系统。

于 2013-10-09T03:50:29.337 回答
2

在这种情况下，GHC 不能确定计算是否会完成。这不是懒惰与严格的问题，而是停止问题。对你来说，说它treeFromlist [0..90000]是一个可以在编译时求值的常量看起来很简单，但是编译器是怎么知道这一点的呢？编译器可以轻松优化[0..90000]为常量，但您甚至不会注意到这种变化。

于 2013-10-08T22:21:45.457 回答