haskell - 模板元编程的 Haskell 变体

Question

我是 Haskell 的新手。鉴于 Haskell 的整个前提是函数将始终返回相同的值，我希望有一些方法可以在编译时计算常量的斐波那契值，就像我可以在 C++ 中使用模板元编程一样，但我可以不知道怎么做。有办法吗？

Answer 1

编辑：Daniel Fischer 指出，您可以将普通表达式提升到 Template Haskell 并在编译时评估结果，但要受到输出类型的某些约束，方法是使用普通函数fib然后拼接

$(let x = fib 1000 in [|x|])

原始答案如下。

正如评论中所指出的，Template Haskell 是解决这个问题的方法。对于像斐波那契这样的归纳函数，它相当简单。您编写类似于标准定义的代码，但返回一个 ExpQ 值。由于拼接限制，您需要使用 2 个模块。

{-# LANGUAGE TemplateHaskell #-} 
module TH where

import Language.Haskell.TH

fibTH :: Int -> ExpQ
fibTH 0 = [| 0 |]
fibTH 1 = [| 1 |]
fibTH n = [| $(fibTH (n-1)) + $(fibTH (n-2)) |]

和

{-# LANGUAGE TemplateHaskell #-}
module Main where

import TH

y :: Int
y = $(fibTH 10)

main = print y

要确认工作是在编译时执行的，我们可以编译-ddump-simpl以查看内核，这可以确认。

Main.y :: GHC.Types.Int
[GblId,
 Caf=NoCafRefs,
 Str=DmdType m,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=0, Value=True,
         ConLike=True, WorkFree=False, Expandable=True,
         Guidance=IF_ARGS [] 10 20}]
Main.y = GHC.Types.I# 55

Answer 2

Don Stewart有一篇很棒的文章，他在其中展示了使用带有正确选择标志的 LLVM 后端将在编译时预先计算某些函数并用常量替换它们。