haskell - Haskell 守卫是如何评估的？

Question

我正在做 99 个 Haskell 问题，在其中一个解决方案中我遇到了以下代码:

pack' [] = []
pack' [x] = [[x]]
pack' (x:xs)
    | x == head  h_p_xs = (x:h_p_xs):t_p_hs
    | otherwise         = [x]:p_xs
    where p_xs@(h_p_xs:t_p_hs) = pack' xs

我想知道 pack' 何时在第一个防护中被调用，以及这是否是 Haskell 代码中引用函数调用返回的列表的头部和尾部的常见模式。在任何递归级别是否有多次调用 pack'，这是一个快速的解决方案吗？

Answer 1

I'm wondering when pack' gets called in the first guard

守卫x == head h_p_xs强制对h_p_xs求值，从而触发递归调用。

and if this is a common pattern in Haskell code to reference the head and tail of the list returned from a function call.

我认为这是一个很常见的模式。您还可能会发现使用 case pack' xs of ... 或 let ... = pack' xs in ... 的变体。

请注意，只要发现空列表，将 let 或 where 与诸如 h_p_xs:t_p_xs 之类的模式一起使用就会导致运行时错误。此代码非常小心，以确保递归调用不会返回 emlty 列表。

Are there multiple calls to pack' at any levels of recursion

说句迂腐的话，Haskell 标准并没有指定代码的实际计算方式，而只指定了结果是什么。因此，理论上，编译器可以进行任意数量的递归调用。

实际上，编译器会小心地只进行一次递归调用——不这样做会导致糟糕的性能。

为了进行比较，下面的代码是等效的，但会导致指数复杂度(!)

...
where p_xs = h_p_xs:t_p_hs
      h_p_xs = head (pack' xs)
      t_p_xs = tail (pack' xs)

在这里，您可以期望编译器进行两次递归调用。

and is this a fast solution?

是的。它预计在输入上以线性时间运行。