Haskell卫兵如何评估？

问题描述

  pack''我在做99个Haskell问题，并在其中一个解决方案中遇到以下代码： [] = [] 
 pack'[x] = [[x]] 
 pack'（x：xs）
 | x == head h_p_xs =（x：h_p_xs）：t_p_hs 
 |否则= [x]：p_xs 
其中p_xs @（h_p_xs：t_p_hs）=包'xs 
  

我想知道pack'在第一个守卫中被调用，如果这是Haskell代码中的一种常见模式，以引用从函数调用返回的列表的头部和尾部。是否有多次调用在任何递归级别打包，并且这是一个快速解决方案？

解决方案

后卫 x == head h_p_xs 强制评估 h_p_xs ，这会触发递归调用。

我认为这是一种很常见的模式。您也可以使用 case pack'xs of ... 或 let ... = pack'xs in ... b
$ b

请注意，使用 let 或其中使用诸如 h_p_xs：t_p_xs 之类的模式时，只要找到空列表，就会导致运行时错误。此代码非常谨慎，以确保递归调用不会返回emlty列表。

为了迂回，Haskell标准没有指定如何实际评估代码，而只是结果如何。因此，从理论上讲，编译器允许进行任意数量的递归调用。

实际上，编译器会小心地进行一次递归调用 - 不这样做会导致一个可怕的表现。

为了便于比较，下面的代码是等价的，但会导致指数复杂性（！）

  ... 
其中p_xs = h_p_xs：t_p_hs 
 h_p_xs = head（pack'xs）
 t_p_xs = tail包'xs）
  

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

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

I'm doing the 99 Haskell Problems and in one of the solutions I came across the following code:

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

I'm wondering when pack' gets called in the first guard and if this is a common pattern in Haskell code to reference the head and tail of the list returned from a function call. Are there multiple calls to pack' at any levels of recursion and is this a fast solution?

解决方案

The guard x == head h_p_xs forces the evaluation of h_p_xs, which triggers the recursive call.

I think this is a quite common pattern. You might also find variations using case pack' xs of ... or let ... = pack' xs in ... instead.

Note that using let or where with a pattern such as h_p_xs:t_p_xs will cause a runtime error whenever an empty list is found. This code is careful to ensure the recursive call will not return an emlty list.

To be pedantic, the Haskell standard does not specify how code is actually evaluated but only what is the result. So, in theory, the compiler is allowed to make any number of recursive calls.

Pragmatically, compilers will be careful to make just one recursive call -- not doing that would lead to a horrible performance.

For the sake of comparison, the code below is equivalent, but would lead to an exponential complexity (!)

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

Here, you can expect the compiler to make two recursive calls.

Yes. It is expected to run in linear time on the input.

这篇关于Haskell卫兵如何评估？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！