2

Exercise 2 of this pdf reads:

Once we have the digits in the proper order, we need to double every other one. Define a function doubleEveryOther :: [Integer] -> [Integer] Remember that doubleEveryOther should double every other number beginning from the right, that is, the second-to-last, fourth-to-last, ... numbers are doubled.

I created an implementation but it is not doing what I expect it to. Here is my code:

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

and a few examples of it running:

*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]

However, I expected

*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]

You see, in the case of an even number of entries, it malfunctions partially through the sequence. My guess is that I am not treating the end of list item [] correctly or I am not using an as-pattern correctly.

Enlico
  • 23,259
  • 6
  • 48
  • 102
machismo
  • 21
  • 2
  • 3
    You should only need `reverse` twice in the whole computation. Right now you are reversing the list at each recursive call, which looks weird. It's possible that the wrong result is caused by too much reversing at the wrong time. – chi Dec 14 '20 at 20:17
  • 1
    Here's an observation that may help you. Suppose for a moment that `doubleEveryOther''` did what it was intended to: it doubles every other element starting from the end of its argument. Now notice that `xs` is in reverse order compared to the argument; so `doubleEveryOther'' xs` is doubling every other element from the end of `xs` -- but this is every other element from the *start* of the original argument! – Daniel Wagner Dec 14 '20 at 21:52
  • These were helpful hints. It’s hard to localise where things are happening at my current level. That makes sense. Also since reverse has 2 states and we are doing something to every other element it makes sense that the period is 4. – machismo Dec 14 '20 at 22:14

1 Answers1

3

As suggested in the comment, since working from left is easier, you can use this procedure:

  • reverse the list
  • work from left
  • reverse the result

and this will be like having worked from right.

Here's a solution using a recursive function to do the job

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

Here's a solution not using recursion

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

which is probably not as good as the previous, because we are wasting time multiplying half of the numbers by 1; but we're not recursing... Well, honestly my level is low enough that I have no clue which solution is better; nor I know why the second solution heap overflows on [1..1000000], while the first still has to give me a result after several seconds. I've also tried doing take 10 $ doubleEveryOther'' [1..1000000] in the two cases, but that does not work. Probably neither solution is lazy.

Enlico
  • 23,259
  • 6
  • 48
  • 102
  • Here's an updated version based off yours ```doubleEveryOther :: [Integer] -> [Integer] doubleEveryOther = reverse . zipWith ($) (cycle [id, (*2)]) . reverse``` This does not say heap overflow but it did stop evaluating after some time on my laptop. My guess is that your problem comes from the concat on the repeat?? It's merely a guess. – machismo Dec 14 '20 at 22:26
  • Oh, yeah, `cycle` is consceptually the same as `concat . repeat`. Nonetheless, they behave differently (for me, on `[1..1000000]`, it starts computing a printing to screen, but then it heap overflows anyway. This is the trailing part of the output: `...,92334,46168,92338,46170,923*** Exception: heap overflow`. I think this difference is all about laziness, and it would deserve a question on its own, though I think one exists already. – Enlico Dec 15 '20 at 08:11
  • As regards using `$`/`[id, (*2)]` insteadof `*`/`[1,2]`, I think that's a very good modification nonetheless, as it saves one multiplication for each two. – Enlico Dec 15 '20 at 08:13