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

问题

1. 哪些Haskell库函数涵盖上述情况？

2. 有没有更简洁/惯用的Haskell解决方案，仍然是O(n)？

3. 上述递归是否有名称（我们在较深层次的递归中使用值以便在上一层级做出决策）？

- haroldcarr

---

哇，每一个回答都非常有趣。我希望我能把它们全部选为答案。谢谢！ - haroldcarr

Answer 1

你可以使用 foldr 来进行从右往左的递归操作：

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

- Tarmil

Answer 2

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

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

以点无式风格编写的代码：

或者以点无式风格编写：

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

- Lee Duhem

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)

- Ørjan Johansen

Answer 4

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

import Control.Lens

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

从操作上来说，这涉及到对列表进行反转，然后修改，再次反转，但无论如何，它仍然具有O(N)的时间复杂度，无论反转多少次。

- András Kovács

---

我对需要反转列表的 lens 版本感到好奇，因此我深入研究了文档，并找到了一种不会反转列表但只是遍历顺序的方法：indexing (backwards traverse) . indices odd *~ 2。 - Ørjan Johansen

@ØrjanJohansen 不错的发现。 - András Kovács

Answer 5

另一种选择是使用lens包。这可以避免显式递归，并使您在可以操作的数据结构上保持非常灵活。您可以使用elements遍历。它需要一个Int -> Bool函数来决定要操作哪些索引。双倍偶数索引或奇数索引。

> over (elements even) (*2) [8,7,6,5]
[16,7,12,5]
> over (elements odd) (*2) [8,7,6,5]
[8,14,6,10]

或者将每个第三个元素加倍：

> over (elements (\n -> mod n 3 == 0)) (*2) [8,7,6,5]
[16,7,6,10]

不仅仅是列表

这个技巧适用于任何具有Traversable实例的数据类型。

例如，考虑containers中的标准树数据类型。

> import Data.Tree
> let tree = Node 1 [Node 2 [Node 3 [], Node 4 []], Node 5 [Node 6 []]]
> let prettyTree = putStrLn . drawTree . fmap show
> prettyTree tree
1
|
+- 2
|  |
|  +- 3
|  |
|  `- 4
|
`- 5
   |
   `- 6
> prettyTree $ over (elements even) (*2) tree
2         --   1
|         --   |
+- 2      --   +- 2
|  |      --   |  |
|  +- 6   --   |  +- 3
|  |      --   |  |
|  `- 4   --   |  `- 4
|         --   |
`- 10     --   `- 5
   |      --      |
   `- 6   --      `- 6

您的问题。

1. The lens package has a number of functions that help with handling recursion with out being explicit.

2. The lens is concise, though some do not yet considered it idiomatic. I have not tested the bigO of the above functions. My understanding is that it will depend on the bigO of the traversable instance for the datatype you are using.

   The list instance in the Traversable module looks straightforward and should meet your expectations.:

   instance Traversable [] where
       {-# INLINE traverse #-} -- so that traverse can fuse
       traverse f = Prelude.foldr cons_f (pure [])
             where cons_f x ys = (:) <$> f x <*> ys
   

3. I am not sure what you are asking for here.

- Davorak

---

对于问题#3，我想知道我初始答案中的递归方案是否有一个名称，请参考http://en.wikipedia.org/wiki/Recursion_(computer_science)#Types_of_recursion。 - haroldcarr

@haroldcarr 递归方案恰好是“zygomorphism”。 - András Kovács

Answer 6

你也可以使用 map：

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 7

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

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 [] = []                                                               

- ArthurVard

Answer 8

为了完整起见，这里将你的解决方案编码为 recursion-schemes zygomorphism，正如András Kovács的评论所预期的那样：

{-# 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

- duplode