3

此 pdf的练习 2内容如下：

一旦我们以正确的顺序获得数字，我们需要每隔一个加倍。定义一个函数 doubleEveryOther :: [Integer] -> [Integer] 请记住，doubleEveryOther 应该从右边开始每隔一个数字加倍，也就是说，倒数第二个、倒数第四个、... 的数字都加倍。

我创建了一个实现，但它没有做我期望的事情。这是我的代码：

doubleEveryOther'' :: [Integer] -> [Integer]
doubleEveryOther'' [] = []
doubleEveryOther'' [x] = [x]
doubleEveryOther'' s@(_:_:_) = 
    let x:y:xs = reverse s
    in reverse (x : 2 * y : doubleEveryOther'' xs)

以及它运行的一些示例：

*Main> doubleEveryOther'' [1,2,3,4,5,6,7,8,9]
[1,4,3,8,5,12,7,16,9]
*Main> doubleEveryOther'' [1,2,3,4,5,6,7,8]
[1,4,3,8,10,6,14,8]

然而，我预计

*Main> doubleEveryOther'' [1,2,3,4,5,6,7,8,9]
[1,4,3,8,5,12,7,16,9]
*Main> doubleEveryOther'' [1,2,3,4,5,6,7,8]
[2,2,6,4,10,6,14,8]

您会看到，在条目数量为偶数的情况下，它会部分地通过序列发生故障。我的猜测是我没有正确处理列表项的结尾，[]或者我没有正确使用 as-pattern。

4

1 回答 1

3

正如评论中所建议的，由于从左侧工作更容易，您可以使用以下过程：

  • 反转列表
  • 从左边工作
  • 反转结果

这就像从右边开始工作一样。

这是使用递归函数完成工作的解决方案

doubleEveryOther'' :: [Integer] -> [Integer]
doubleEveryOther'' = reverse . work . reverse
  where
    work [] = []
    work (x:y:z) = x:(2*y):work z
    work x = x

这是一个不使用递归的解决方案

-- same as above except for work:
    work = zipWith (*) (concat $ repeat [1,2])

这可能不如前一个好，因为我们浪费时间将一半的数字乘以 1；但是我们没有递归……好吧，老实说，我的水平很低，以至于我不知道哪种解决方案更好；我也不知道为什么第二个解决方案heap overflow是 on [1..1000000]，而第一个解决方案仍然必须在几秒钟后给我一个结果。我也试过take 10 $ doubleEveryOther'' [1..1000000]在这两种情况下做，但这不起作用。可能这两种解决方案都不是懒惰的。

于 2020-12-14T20:34:57.000 回答