使用尾遞歸來查找列表的最大值

我想了解如何使用Haskell中的尾遞歸編寫函數。在下面的例子中，該函數獲取一個列表並輸出列表中的最大值。我的意圖是使用c變量來存儲當前的最大值。我想知道是否有人可以解釋如何使用尾遞歸適用於此實例？使用尾遞歸來查找列表的最大值

myMax [] c = error "max of empty list" 
    myMax [x] c = x 
    myMax (x:xs) c = 
       if x > myMax xs then c = x 
       else myMax xs c 

--currently getting a parse error

來源

2013-02-12 AnchovyLegend

你想在if語句中用'c = x'做什麼？ if語句必須在兩個分支中返回相同類型的值。它看起來像你試圖破壞性地修改Haskell不允許的'c'。我不確定它的意圖是什麼，因爲即使它被允許，我也沒有看到期望的結果是什麼。 – asm 2013-02-12 17:49:51

感謝您的回覆。我試圖在'c'中存儲當前的最大值，因爲我將比較列表中的越來越多的值與它進行比較。當我沒有更多的值進行比較時，我輸出最後的'max'值。這是我的意圖，再次尾部遞歸令我感到困惑，這就是爲什麼我決定嘗試獲得一些幫助。 – AnchovyLegend 2013-02-12 17:53:43

haskell中沒有賦值語句。您不能爲現有變量賦值（術語「變量」非常具有誤導性），您只能引入新的綁定。 – pat 2013-02-12 18:03:29

這裏有幾件事要考慮。首先，你不希望用戶輸入一些開始值，所以我們需要一個只有一個列表作爲其參數的函數。既然你想要一個尾遞歸實現，我們確實需要一個接受第二個參數的函數，所以我們將創建一個名爲go的內函數，它取當前的最大值和剩餘的列表。

myMax [] = error "Empty List" 
myMax (x:xs) = go x xs -- Initialize current max to head of list. 
    where 
    -- go takes the current max as the first argument and the remaining list 
    -- as the second. 
    -- m is the current max, if there are no more elements it is the max. 
    go m [] = m 
    -- Otherwise we compare m to the current head. 
    -- If the head (y) is greater than m it becomes the current max. 
    go m (y:ys) = if m > y then go m ys else go y ys

請注意，我們這裏從來沒有改變任何變量的值。我們將當前最大值作爲參數傳遞給函數中的下一個步驟。這在Haskell中很重要，因爲不允許使用變異變量。

來源

2013-02-12 18:01:00 asm

+1感謝您的明確解釋，這有助於！ – AnchovyLegend 2013-02-12 18:04:11

很高興幫助，哈斯克爾是一個很好玩的學習:) – asm 2013-02-12 18:04:44

我基本上有相同的答案准備！我會將遞歸go的因數分解爲： 'go m（y：ys）= go（if m> y then m else y）ys'，or even'go m（y：ys）= go（max我）ys'，但發揮到了極致，你只需要'myMax = maximum'。 – pat 2013-02-12 18:05:41

最小值或最大值的正常尾遞歸版本存在問題，即累加器作爲參數。更具體地說，累加器參數的初始值必須從列表中提供，該列表是列表的第一項，也就是函數的第二個參數，您可以在其中找到最小值或最大值。重申，最小或最大尾遞歸函數通常必須帶兩個參數。第一個參數是累加器，第二個參數是要分析的列表。問題是第一個參數的初始值。除了要分析的列表之外，它不能提供。接下來，尾部遞歸函數的基礎是累加器。累加器是最後一個最小值或最大值存儲的位置，並傳遞給函數以與列表的下一個值進行比較。基本功能可以是

fix (\f v (x:xs) -> if xs == [] then v else if x < v then f x xs else f v xs) 9999999 [6,5,4,3,2,1,10,7,8]

第一個參數是在在列表中比任何高的值猜測和註定要失敗，並且不能自動化。第一個參數應該來自列表，也許是第一個項目。前一個函數中的第一個參數是'v'。它包含最後的最小值或最大值。對前面的函數使用另一個調用很容易。

t= \(y:ys) -> (fix (\f v (x:xs) -> if xs == [] then v else if x < v then f x xs else f v xs) y ys)

第一部分使用圖案匹配（Y：YS）於所提供的列表分割成頭部和尾部。頭部成爲被調用函數中的初始v參數。尾巴成爲第二個。這似乎令人費解和複雜的我。累加器初始值是問題。它必須被計算。如何才能做到這一點？通過消除第一個參數。擺脫它。但是我們仍然必須保留一個累加器值來傳遞，以便與列表的下一個值進行比較。我們在哪裏可以保留它？唯一可能的地方，在列表本身。

minf :: (Num b, Ord b) => [b] -> b 
minf [x]  = x 
minf (x:xs) = if x > head xs then minf $ x : tail xs else minf xs

minf取一個參數，分析最小或最大列表。只需將比較標誌更改爲「<」或「>」即可。另外，我使用這個版本。

min = fix (\f (x:xs) -> if xs == [] then x else if x < head xs then f $ x : tail xs else f xs)

我只讓我的腳在Haskell溼，但我的期望值是非常高的。這是最好的語言，永遠。它是上述的一個版本，只有一個參數。

來源

2018-02-23 18:16:36 fpmora

使用尾遞歸來查找列表的最大值

回答

相關問題