What to use instead of explicit recursion in Haskell?

Question

Write a function that doubles other number beginning with the 2nd number from the right:

Example:

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

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

O(n) solution:

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

The use above of explicit recursion is generally considered poor Haskell style (e.g., use fold*, scan, etc where possible).

QUESTIONS

1. what Haskell library functions cover the above case?

2. what would be a more concise/idiomatic Haskell solution that is still O(n)?

3. is there a name for the above type of recursion (where we use the value from a deeper recursion to make a decision the next level up)?

Answer 1

You can use foldr to do this kind of recursion from the right:

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

Answer 2

Another way to define this function by using standard library functions:

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

Or in pointfree style

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

Answer 3

Lots of useful answers here, but no one yet mentioned the rarely seen function mapAccumR from Data.List which fits this particular use case almost perfectly:

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

Answer 4

As to question 1 and 2, with lens you can define the function in a declarative manner:

import Control.Lens

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

Operationally, this involves reversing the list, then modifying, then reversing again, but of course it's still O(N) with any constant number of reversals.

Answer 5

An alternative is to use the lens package.

This allows you to avoid explicit recursion and remain very flexible on what data structures you can operate on.

You can use the elements traversal. It takes a Int -> Bool function to decide what indices to act on.

Double even indices or odd indices.

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

Or double every third element:

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

Not just lists

This technique will work for any datatype that has a Traversable instance.

For example take the standard tree datatype for the 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

Your questions.

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.

Answer 6

You can use map as well:

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

My solution using mutual recursions

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 8

For the sake of completeness, here is your solution encoded as a recursion-schemes zygomorphism, as anticipated by 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