0

最近我正在尝试使用 Foldr 解决一个问题。任务如下：

In:[5,1,3,8,2,4,7,1]
Out:[16,8]

这意味着，我会将输入列表中位于奇数索引位置和偶数位的元素加倍。我在没有使用 foldr 的情况下编写了程序，如下所示：（它显示模式匹配失败：head[]）

findPos list elt =
  map fst $ filter ((elt==).snd) $ zip [0..] list

doublePos [] = []
doublePos (x:xs)
  | ((head(findPos xs x)`mod` 2) /= 0) && (x `mod` 2 == 0) =
      [2*x] ++ doublePos xs
  | otherwise = doublePos xs

如何使用 foldr 编写此程序？

4

2 回答 2

5

foldr对于这个函数来说，这并不是一个好的选择，因为您需要从列表的前面传递每个元素的索引的奇偶校验。

列表推导可能是最干净的：

doublePos xs = [2*x | (i,x) <- zip [0..] xs, even x, odd i]

或者您可以使用普通的旧递归：

doublePos' (_:x:xs)
  | even x    = (2*x) : doublePos' xs
  | otherwise =         doublePos' xs
doublePos' _ = []

但是，如果您必须使用foldr，您可以通过将累加器作为一个函数来实现，该函数将当前索引的奇偶校验作为参数：

doublePos'' xs = foldr step (const []) xs False where
  step x next p
    | p && even x = 2*x : next (not p)
    | otherwise   = next (not p)
于 2012-11-27T16:12:16.590 回答
2

为什么您现有的代码会给您模式匹配失败：doublePos [5,1,3,8,2,4,7,1]将第二个等式与x = 5and匹配xs = [1,3,8,2,4,7,1]。这会导致head (findPos [1,3,8,2,4,7,1] 5)被评估，但这会减少到head []你得到你的错误。

对此进行扩展：您似乎希望摆脱的findPos是当前元素的索引，相对于原始列表的开头。但是你实际上从中得到的是当前元素下一次出现的索引，相对于下一个元素......如果它不再出现，你会得到一个错误。

（此处使用字符作为列表元素以避免列表索引和列表元素之间的混淆。）

 0   1   2   3   4   5   6   7   8   9  10     <-- indices relative to start
'H':'e':'l':'l':'o':' ':'t':'h':'e':'r':'e':[] <-- original list
     |           |
x = 'e'          |               V                 say we're here
   xs = 'l':'l':'o':' ':'t':'h':'e':'r':'e':[]     head (findPos xs x) = 6 but we wanted 1
                 |               ^
            x = 'o'                                say we're here instead
               xs = ' ':'t':'h':'e':'r':'e':[]     head (findPos xs x) = error "head []" but we wanted 4

唯一可行的方法是将原始列表传递给findPos. 但是您唯一可用的列表是您尚未递归到的原始列表的那部分。无论如何，正如哈马尔的回答所见，有更好的方法来做到这一点。

于 2012-11-27T16:12:36.060 回答