时间戳

首页 > 解决方案 > 如何为这个递归函数定义正确的边定义？

haskell - 如何为这个递归函数定义正确的边定义？

问题描述

如果有人感兴趣，解决方案：

f :: Ord a => [a] -> [a]
f [] = []
f [x] = []
f (x:y:xs)
 | x < y = max x y : f (y:xs)
 | otherwise = f (y:xs)

样本输入：

f [1,3,2,4,3,4,5] == [3,4,4,5]
f [5,10,6,11,7,12] == [10,11,12]

更新代码：

f [] = []
f [x] = [x]
f (x:y:xs)
 | x < y = max x y : f (y:xs)
 | otherwise = f (y:xs)

问题是它两次输出最后一个数字：

f [5,10,6,11,7,12] == [10,11,12,12]

以下旧内容

我正在编写一个函数，它接受一个列表并返回比前一个更大的元素。我想出了这个，但问题是当它到达最后一个元素时，xs !! 0 不存在，因此错误。在这种情况下，如何定义正确的退出点？

我的代码：

f :: Ord a => [a] -> [a]
f [] = []
f (x:xs) = max x (xs !! 0) : f xs

错误：

[3,3,4,4,4,5,*** Exception: Prelude.!!: index too large

标签： haskellfunctional-programming

解决方案

您并不总是要在结果中添加新元素；有时你什么都不会添加。

f :: Ord a => [a] -> [a]
f [] = []
f [x] = [x]
f (x:y:xs) = _  -- what goes here?

对于您的递归情况，有两种可能性：

  1. 如果x < y，您将添加y到结果中。
  2. 否则，您将不会添加y到结果中。事实上，你不会添加任何东西。

在任何一种情况下，您都需要y在递归调用中包含，而不仅仅是xs，以便在下一次迭代中，y将是第一个与它之后的元素进行比较的元素。

我把它作为一个练习来实现上述逻辑作为你的递归案例。

推荐阅读