Why does my function dropR (reverse of Prelude drop) look the way it does?

user_16940402 0
Viewed 132

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?

haskell-prelude function haskell
2 Answers

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.

user_1802860

@FyodorSoikin explained why n-1 is necessary (because you match with (x:xs), and thus xs is the tail of the list, not the entire list).

However using reverse and ++ [x] are not a good idea. reverse requires the list to have a finite number of items, and ++ [x] will turn the algorithm in an O(n2) one. A better idea to drop the n last items might be to run on the list with two iterators: the first one starts n step more to the right than the second one. In that case if the first iterator reaches the end of the list, we know that the second enumerator should stop.

We thus can implement this with:

dropR :: Int -> [a] -> [a]
dropR n xs = go (drop n xs) xs
  where go [] _ = []
        go (x:xs) ~(y:ys) = y : go xs ys

this implementation works lazily, and can process infinite lists (in which case it will never drop anything).

user_675790
Related