使用尾递归查找列表的最大值 [英] Finding the max of a list using tail recursion

问题描述

我试图理解如何使用Haskell中的尾递归编写函数。在下面的例子中，该函数获取一个列表并输出列表中的最大值。我的意图是使用 c 变量来存储当前的最大值。我想知道是否有人可以解释如何使用尾递归为这个实例工作？

I am trying to understand how to write functions using tail recursion in Haskell. In my example below, the function takes in a list and outputs the maximum value in the list. My intention is to use the c variable to store the current max. I was wondering if someone can explain how using tail recursion would work for this instance?

    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

推荐答案

这里有几件事要考虑。首先，你不希望用户输入一些开始值，所以我们需要一个只有一个列表作为其参数的函数。既然你想要一个尾递归实现，我们确实需要一个接受第二个参数的函数，所以我们将创建一个名为 go 的内函数，它取当前的最大值和剩余的值

There are a couple things to think about here. First You don't want the user to have to enter some beginning value, so we want a function that takes only a list as its parameter. Since you want a tail recursive implementation we do need a function that takes a second parameter though, so we'll create an inner function named go which takes the current max and the remaining list.

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中很重要，因为不允许使用变量变量。

Note that we never changed the value of any variable here. We update the current max value by passing it as a parameter to the next step in the function. This is critical to understand in Haskell because mutating variables is not allowed.

这篇关于使用尾递归查找列表的最大值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！