更新函数以包含尾递归

Question

我有以下函数来确定给定列表的最大元素。

maxList :: Ord a => [a] -> a
maxList l =
    let iMaxList :: Ord a => [a] -> a
        iMaxList [] = error( "Empty list" )
        iMaxList [x] = x
        iMaxList ( x:xs )
            | x > t = x
            | otherwise = t
            where t = iMaxList xs
    in iMaxList l

然而，它不使用尾递归，我希望它这样做。我尝试使用累加器来遵守Haskell中的尾递归原则。

maxList :: Ord a => [a] -> a
maxList ( x:xs ) = loop( xs, x )
                  where loop( x:xs, m )
                            | ( null xs ) = m
                            | ( x >= m ) = loop( xs, x )
                            | otherwise = loop( xs, m )

然而，由于这个守卫(null xs) = m，它在逻辑上失败了。事实上，如果我们采用列表 [1,2,3,4]，4 将永远不会被评估。

我该如何解决？

Answer 1

我想这就是您要搜索的内容：

maxList' :: Ord a => [a] -> a
maxList'     []   = error "Empty List"
maxList'    [x]   = x
maxList' (x:y:xs) = maxList' (max x y:xs)

该函数使用正在处理的同一个列表来存储迄今为止找到的最大数字。它似乎符合尾递归定义，即：递归调用是函数计算中的最后一件事。

Answer 2

listMax :: Ord a => [a] -> a
listMax [] = error "Tried to find maximum of an empty list."
listMax (x:xs) = listMax' xs x where
  listMax' :: Ord a => [a] -> a -> a
  listMax' [] y = y
  listMax' (x:xs) y | x > y     = listMax' xs x
                    | otherwise = listMax' xs y

在这种情况下，y 是保存迄今为止找到的最大值的累积参数。正确性的简要证明：算法终止，因为每次尾递归调用都会从输入列表中删除一个元素，直到它为空。 y 和 returns 的最终值是最大值，因为对于输入中的每个其他元素 x，y > x 或 y > z > x 对于某些 z 在 x 之后和 y 之前。（这假设 > 是可传递的。）

你也可以这样写辅助函数：

listMax' :: Ord a => [a] -> a -> a
listMax' [] y = y
listMax' (x:xs) y = listMax' xs (max x y)

这个实现做同样的事情：

listMax2 :: Ord a => [a] -> a
listMax2 [] = error "Tried to find maximum of an empty list."
listMax2 list = foldl1 max list

foldl1 函数是从前到后的尾递归惰性求值，但严格的 foldl1' 版本或 foldr1 在这种情况下可能更有效。第一个版本比惰性更接近严格评估。

Answer 3

别担心。

我在文件中写了以下内容：

module MaxList (maxList) where

import Data.List

maxList :: Ord a => [a] -> a
maxList = foldl1' max

然后我用-O2 -ddump-simpl编译了它，看看优化后的Core。经过一番清理后 - GHC 生成了许多名称难以阅读的变量 - 生成的代码如下所示：

maxList [] = error "empty list"
maxList (x:xs) = go xs x
    where go ys y =
              case ys of
                   [] -> y;
                   (z:zs) -> case y of  -- force y to WHNF before continuing
                                  _ -> go zs (max y z)

go 是尾递归。其实和里面的代码是一样的！我使用了 foldl1' - 一个高级控制结构 - 如果你想编写尾递归循环，GHC 生成的代码与你手写的代码完全相同。

Haskell 的哲学是你应该使用高级工具，如折叠、展开、monad、类等，并依靠编译器生成好的代码。编写 GHC 可以很好地优化的代码当然是一门艺术——你并不总是免费获得它——但你通常不需要将高级结构展开到低级循环中，因为 GHC 很好

更新函数以包含尾递归

Update a function to include tail recursion

recursion

haskell

functional-programming

tail-recursion