3

我目前正在尝试解决以下练习：

给定一个Ints 列表，计算一个元素大于其后元素的次数。该练习迫使我不要使用显式递归。

以下是给出的一些示例输出function :: [Int] -> Int：

function [1, 2, 3, 4, 5]         == 0  -- only increasing numbers
function [5, 4, 3, 2, 1]         == 4  -- only decreasing numbers

function [2,  1,  3,  1,  0,  4] == 3
--        2 > 1  
--                3 > 1
--                    1 > 0

function [1] == 0 -- no successor
function [ ] == 0 -- no numbers at all

我想以某种方式使用，foldl但经过多次尝试和不可行的想法，我不得不放弃。

如何在不使用递归的情况下计算元素大于其后继元素的次数？

4

1 回答 1

7

首先我们需要配对连续的元素，

foo :: [Int] -> Int
foo xs = result
  where
      pairs = zip xs (drop 1 xs)

然后我们可以处理每一对

      biggers = [ () | (x,y) <- pairs, x > y]

现在我们可以数一数了，

      result = .......

所有嵌套名称都属于相同的、共享的嵌套范围。result必须利用 的值biggers, 并biggers指代 的值pairs指的是foo的参数 ,的值xs。确保将这些代码行放入相同的定义中，所有的缩进量与第一个相同，for pairs，一个在另一个之下。

实际上也可以使用左折叠：

foo (h:t) = snd ( foldl' (\ (a, !c) x -> (x, if (a > x) then (c+1) else c)) 
                         (h,0) t )
foo [] = 0

我想你会同意，尽管这比第一个定义不那么明显。另请注意，它使用“爆炸模式”,!与foldl', not一起foldl在我们沿着输入列表进行时尽快进行计数，而不是延迟它直到所有输入列表都被完整遍历，foldl这是不必要的，损害整体效率。

于 2021-02-02T08:51:20.550 回答