Haskell衛兵如何評估？

我做了99個Haskell的問題與我碰到下面的代碼附帶的解決方案之一：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 [email protected](h_p_xs:t_p_hs) = pack' xs

我想知道當包」被調用的第一後衛，如果這是一個常見的模式在Haskell代碼中引用從函數調用返回的列表的頭部和尾部。是否有多次調用「在任何遞歸級別打包，這是一個快速解決方案？

來源

2014-12-22 Þór Óðinsson

我想知道當包」被調用第一後衛

防護x == head h_p_xs強制的h_p_xs的評價，這會觸發遞歸調用。

，如果這是在 Haskell代碼的通用模式，以引用列表的頭部和尾部從函數調用返回。

我覺得這是一個很常見的模式。您也可以使用case pack' xs of ...或let ... = pack' xs in ...代替。

請注意，使用let或where以及h_p_xs:t_p_xs等模式將在每次找到空列表時導致運行時錯誤。此代碼非常小心，以確保遞歸調用不會返回emlty列表。

是否有多個調用打包」在遞歸

的任何級別要學究，Haskell的標準沒有規定的代碼實際上是如何評價，但只的結果是什麼。所以，從理論上講，編譯器可以進行任意數量的遞歸調用。

實際上，編譯器會小心地進行一次遞歸調用 - 不這樣做會導致可怕的性能。

爲了比較起見，下面的代碼是等效的，但會導致指數的複雜性（！）

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

在這裏，你可以期望編譯器進行兩次遞歸調用。

，這是一個快速的解決方案？

是的。預計在輸入上以線性時間運行。

來源

2014-12-22 19:56:06 chi

如果我改變X ==頭h_p_xs =（X：h_p_xs）：t_p_hs爲x ==頭XS =（X：h_p_xs）：t_p_hs有在程序的運行方式的區別？ –

@ÞórÓðinsson據我現在所見，它應該是等效的。 – chi

這是引用head的常用方法，如果它使代碼更具可讀性。當然，你可以通過做在最後一行類似

[email protected]( (h_p_x : h_p_xs) : t_p_hs) = pack' xs

，而不是

[email protected](h_p_xs : t_p_hs) = pack' xs

這樣你在h_p_x變量頭去做。不過，你需要在第四行添加：

| x == head h_p_xs = (x : h_p_x: h_p_xs):t_p_hs

所以你看，這裏使用:運營商只需通過添加無用實體混亂的代碼。至於遞歸的數量，我可以在這裏看到每個級別只有一個遞歸調用，所以基本上它是線性運行時間，因此是有效的。

來源

2014-12-22 19:54:39

pack'似乎像一樣工作Data.List.group - 它將連續相等的元素分組到列表中。所以，pack [1,1,3,2,2]將返回[[1,1]，[3]，[2,2]]。

模式匹配是慣用的哈斯克爾。在這裏，在聲明中，

h_p_xs:t_p_hs = pack' hs

我們知道pack'hs會返回一個列表。所以，h_p_xs匹配到它的頭部，而t_p_hs匹配到它的尾部。 LHS和RHS都必須具有與此類似的結構（這裏雙方都有列表結構），以便在Haskell中進行模式匹配。 p_xs在這裏匹配到整個RHS（@ pattern）。所以，是的，這在Haskell中是非常常見的成語。

在包裝定義中，前兩行用於處理空單和單列表。因此，只有當輸入列表具有多個元素並且其第一和第二元素相等時，第一個守衛條件才適用。

在任何級別，最多隻有一次遞歸調用，因此時間複雜度爲O（n）。應該快。

來源

2014-12-22 19:54:43 VinyleEm

其實，這不是尾遞歸。儘管如此，複雜性仍然是O（n）。 – chi

謝謝。我將編輯我的帖子。 – VinyleEm

Haskell衛兵如何評估？

回答

相關問題