I'm still new to programming and to practice writing functions, I attempted to reverse the effects of the Prelude drop;

drop :: Int -> [a] -> [a]
drop 0 [] = []
drop 0 (x:xs) = x:xs
drop n [] = []
drop n (x:xs) = drop (n-1) xs

into something I very originally named dropR.

dropR :: Int -> [a] -> [a] -- drops from the right of the list
dropR 0 [] = []
dropR 0 (x:xs) = x:xs
dropR n [] = []
dropR n (x:xs) = reverse (drop (n-1) (reverse xs    [x]))

Unfortunately, this didn't work, as the input dropR 2 [1,2,3,4,5] returned [1,2,3,4] and not [1,2,3] as I'd hoped. Using drop 2, I would've gotten 3 values in the list and not 4. I changed the function to;

dropR :: Int -> [a] -> [a] -- drops from the right of the list
dropR 0 [] = []
dropR 0 (x:xs) = x:xs
dropR n [] = []
dropR n (x:xs) = reverse (drop n (reverse xs    [x]))

which worked in the way I wanted, but I don't understand why the first one doesn't work. I thought that it would've just reversed the list and taken the same amount of values as the regular drop would after which I could just reverse it.

Why does drop need drop (n-1) and my dropR just need drop n? Does it happen because of recursion in drop and not in dropR?

CodePudding user response：

Let's look at an example:

dropR 2 [1, 2, 3, 4]

In your first attempt, the last line matches, and in it:

• n = 2
• x = 1
• xs = [2, 3, 4]

Therefore:

• reverse xs = [4, 3, 2]
• reverse xs [x] = [4, 3, 2, 1]
• drop (n-1) (reverse xs [x]) = drop 1 [4, 3, 2, 1] = [3, 2, 1]
• reverse (drop (n-1) (reverse xs [x])) = [1, 2, 3]
• Q.E.D.

In your second attempt, on the other hand:

• reverse xs = [4, 3, 2]
• reverse xs [x] = [4, 3, 2, 1]
• drop n (reverse xs [x]) = drop 2 [4, 3, 2, 1] = [2, 1]
• reverse (drop (n-1) (reverse xs [x])) = [1, 2]
• Q.E.D.

But have a deeper look.

Observe that reverse xs [x] is actually the same as reverse (x:xs): you're reversing the tail and then sticking the head to the end of it. That's the same as reversing the whole list in the first place.

So what you're really doing there is:

• reversing the whole list
• dropping n from it
• reversing it again

So you might as well just do away with all the cases you have there and just do:

dropR n xs = reverse (drop n (reverse xs))

Or a bit shorter:

dropR n = reverse . drop n . reverse

I think this variant is slightly better, because it expresses the idea more clearly: reverse, then drop n, then reverse again.