haskell - 在 Haskell 中使用什么代替显式递归？

Question

编写一个函数，从右边的第二个数字开始，将其他数字加倍:

例子:

doubleEveryOther   [8,7,6,5]
=> [16,7,12,5]

doubleEveryOther     [1,2,3]
=> [1,4,3]

O(n) 解决方案:

doubleEveryOther :: Num a => [a] -> [a]
doubleEveryOther xs0 =
    let (_,r)   = deo xs0
        deo xs1 = case xs1 of
            []     -> (False, [])
            (x:xs) -> let (b, xs') = deo xs in ((not b), (if b then 2*x else x) : xs')
    in r

上面显式递归的使用通常被认为是糟糕的 Haskell 风格(例如，尽可能使用 fold*、scan 等)。

问题

什么 Haskell 库函数涵盖了上述情况？

什么是仍然是 O(n) 的更简洁/惯用的 Haskell 解决方案？

上述递归类型是否有名称(我们使用来自更深递归的值来做出下一个级别的决定)？

Answer 1

您可以使用 foldr从右边做这种递归:

doubleEveryOther = snd . foldr go (False, [])
    where go x (b, xs) = (not b, (if b then 2*x else x) : xs)