在Haskell中使用什么而不是显式递归？

Question

编写一个函数，将右边第二个数字开头的其他数字翻倍：

例：

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

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

Ono Sochen：

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等）。

质询

1. Haskell库函数涵盖了上述情况？
2. 什么是更简洁/惯用的Haskell解决方案仍然是O（n）？
3. 是否有上述类型的递归的名称（我们使用更深层递归的值来做出下一级别的决定）？

Answer 1

您可以使用foldr从右侧执行此类递归：

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

Answer 2

使用标准库函数定义此函数的另一种方法：

doubleEveryOther ls = reverse $ zipWith (*) (cycle [1,2]) (reverse ls)

或者以无点的风格

doubleEveryOther = reverse . zipWith (*) (cycle [1,2]) . reverse

Answer 3

这里有很多有用的答案，但还没有人提到mapAccumR中罕见的函数Data.List几乎完全适合这个特殊用例：

doubleEveryOther :: Num a => [a] -> [a]
doubleEveryOther = snd . mapAccumR step False
  where
    step False x = (True, x)
    step True  x = (False, 2*x)

Answer 4

对于问题1和2，使用lens，您可以以声明方式定义函数：

import Control.Lens

doubleEveryOther :: Num a => [a] -> [a]
doubleEveryOther = reversed . traversed . indices odd *~ 2 

在操作上，这涉及反转列表，然后修改，然后再次反转，但当然它仍然是O（N）具有任何恒定数量的反转。

Answer 5

你也可以使用地图：

Prelude> let f ns = map (\(a,b) -> if (even (length ns) && even b) || (odd (length ns) && odd b) then a else a * 2) $ zip ns [1..]

Prelude> f [8,7,6,5]
[16,7,12,5]

Prelude> f [8,7,6]
[8,14,6]

Answer 6

我使用相互递归的解决方案

doubleEveryOther :: [Integer] -> [Integer]                                      
doubleEveryOther xs                                                             
    | even n =  doubleOdd xs                                                    
    | otherwise = doubleEven xs                                                 
  where n = length xs     

-- | use mutual recursion
doubleEven :: Num a => [a] -> [a]
doubleEven (x:xs) = x : doubleOdd xs     
doubleEven [] = []                                                              

doubleOdd :: Num a => [a] -> [a]
doubleOdd (x:xs) = (2*x) : doubleEven xs 
doubleOdd [] = []                                                               

Answer 7

为了完整起见，这里是你的解决方案编码为递归方案zygomorphism，正如András Kovács's remark预期的那样：

{-# LANGUAGE LambdaCase #-}

import Data.Functor.Foldable

doubleEveryOther :: Num a => [a] -> [a]
doubleEveryOther = zygo flagAlg emitAlg
    where
    flagAlg = \case
        Nil -> False
        Cons _ b -> not b
    emitAlg = \case
        Nil -> []
        Cons x (b, xs) -> (if b then 2*x else x) : xs