1

我试图了解如何在 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
4

2 回答 2

6

这里有几件事要考虑。首先，您不希望用户必须输入一些起始值，因此我们需要一个仅将列表作为参数的函数。由于您想要一个尾递归实现，我们确实需要一个带有第二个参数的函数，因此我们将创建一个名为的内部函数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-12T18:01:00.840 回答
0

最小值或最大值的正常尾递归版本存在问题，即累加器作为参数。更具体地说，累加器参数的初始值必须从列表中提供，列表的第一项，即函数的第二个参数，您可以在其中找到最小值或最大值。重申一下，最小或最大尾递归函数通常必须采用两个参数。第一个参数是累加器，第二个是要分析的列表。问题是第一个参数的初始值。它只能从要分析的列表中提供。接下来，尾递归函数的基础是累加器。累加器是存储最后一个最小值或最大值并传递给函数以与列表的下一个值进行比较的地方。一个基本功能可以是

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) 将提供的列表拆分为头部和尾部。head 成为被调用函数中的初始 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-23T18:16:36.163 回答