1

考虑一个像下面这样的haskell-expression：（简单的例子，不要告诉我明显的方法是什么！;）

toBits :: Integral a => a -> [Bool]
toBits 0 = []
toBits n = x : toBits m where
 (m,y) = n `divMod` 2
  x    = y /= 0

因为这个函数不是尾递归的，所以也可以这样写：

toBits :: Integral a => a -> [Bool]
toBits = toBits' [] where
  toBits' l 0 = l
  toBits' l n = toBits (x : l) m where
    (m,y) = n `divMod` 2
     x    = y /= 0

（我希望这个表达没有错）

我想问的是，这些解决方案中哪一个更好。第一个的优点是，它可以很容易地进行部分评估（因为 Haskell:不需要在第一个处停止。），但第二个解决方案（显然）是尾递归的，但在我看来，它需要被完全评估直到你能拿出一些东西。

这个的背景是我的 Brainfuck 解析器，（见我的优化问题），它的实现非常丑陋（各种reverse指令......哦），但可以很容易地在第一个实现 - 我们称之为“半尾递归”方式.

4

3 回答 3

2

在 Haskell 中，您的首选通常是首选（我会说“总是”，但当您使用该词时，您总是错的）。累加器模式适用于不能以递增方式消耗输出的情况（例如递增计数器）。

于 2010-09-09T15:33:40.953 回答
2

我认为你已经做好了一切。第一种形式通常更好，因为可以在完成计算之前从中获得有用的输出。这意味着如果在另一个计算中使用“toBits”，编译器可能会将它们组合起来，而作为“toBits”输出的列表可能根本不存在，或者可能一次只存在一个 cons 单元格。很高兴第一个版本也更清晰易读！

于 2010-09-09T13:52:27.493 回答
1

让我重命名第二个版本并修正一些拼写错误，以便您可以测试功能。

toBits :: Integral a => a -> [Bool]
toBits 0 = []
toBits n = x : toBits m where
 (m,y) = n `divMod` 2
 x     = y /= 0

toBits2 :: Integral a => a -> [Bool]
toBits2 = toBits' [] where
  toBits' l 0 = l
  toBits' l n = toBits' (x : l) m where
    (m,y) = n `divMod` 2
    x     = y /= 0

这些函数实际上并不计算相同的东西。第一个生成从最低有效位开始的列表，而第二个从最高有效位开始。换句话说toBits2 = reverse . toBits，实际上reverse可以使用与您使用的完全相同类型的累加器来实现toBits2。

如果你想要一个从最低有效位开始的列表，那么toBitsHaskell 风格是很好的。它不会产生堆栈溢出，因为递归调用包含在 (:) 构造函数中，该构造函数是惰性的。（此外，您不能通过toBits提前强制结果列表的后期元素的值来导致参数中的 thunk 累积，因为需要在第一种情况下评估参数toBits 0 = []以确定列表是否为空。）

如果您想要从最高有效位开始的列表，则可以toBits2直接编写或定义toBits和使用reverse . toBits是可以接受的。我可能更喜欢后者，因为在我看来它更容易理解，而且你不必担心你的重新实现是否reverse会导致堆栈溢出。

于 2010-09-11T17:05:43.203 回答