如何编写一个 haskell 函数，将函数应用于列表，直到其参数之一变为 0？

Question

我必须编写以下 haskell 函数：

它接收一个整数（我们称之为

h

）和一个整数列表： 参数。它应该遍历列表，并增加 每个能被 2 整除的元素的值。每当它这样做时， 它将

h

的值减 1。它应该重复此过程 直到

h

为0。如果到达列表末尾则

h

的值 不为零，它应该重新开始整个过程，直到 它确实变成了 0。它也应该适用于无限列表。在里面 以下测试用例：

inc_until 4 [1,2,3,4,5]

它应该返回

[1,4,3,6,5]

除了我自己编写的守卫、模式匹配和辅助函数之外，我不允许使用任何东西。

inc_until :: Integer -> [Integer] -> [Integer]
inc_until _ [] = []
inc_until h (x:xs)
 | x 'mod' 2 == 0 = (x+1) : inc_until (h-1) xs
 | otherwise = inc_until h xs

这只迭代列表一次，因此即使 h 的值不为零，它也会停止。

Answer 1

与规范相比，您的实现存在两个问题。

1. 当

   h

   为 0 时，您不会停止。您可以通过为这种情况添加显式子句来轻松解决此问题。

   inc_until 0 xs = {- ... -}
   

2. 当

   h

   太大时，您不会重新开始。在这里，我发现规范有点含糊：您应该从修改后的列表开始，还是原始列表开始？无论如何，一种前进的方法是实现一个最多迭代列表一次的辅助函数，不仅返回更新的列表，还返回

   h

   的更新值。

   inc_until_once :: Integer -> [Integer] -> (Integer, [Integer])
   inc_until_once h xs = {- ... -}
   

   然后你可以根据这个实现你的顶级函数，循环直到

   h

   下降到

   0

   。

   inc_until h xs = case inc_until_once h xs of
       (0 , xs') -> xs'
       (h', xs') -> inc_until h' {- xs or xs' depending on what the spec means -}
   

   另一种可能吸引某些人的策略是观察

   inc_until _ []

   案例的真正问题是我们不知道要从哪个列表重新开始。如果规范意味着使用修改后的列表重新启动，我们可以通过传递一个（反向）前缀来扔到答案的前面来解决这个问题，而不是直接发出答案。

   inc_until_acc prefix 0 xs = reverse prefix ++ xs
   inc_until_acc prefix h [] = {- we now know that prefix is related to the list we should restart with -}
   inc_until_acc prefix h (x:xs) = {- ... -}
   
   inc_until = inc_until_acc []