CODEWITHSUNDEEP
haskell
Tengu
Tengu

Reputation: 1034

Drop nth Element from list

I have been teaching myself Haskell for a month or so and today I was reading the solution of 16th problem and came up with a question.

Here is a link : http://www.haskell.org/haskellwiki/99_questions/Solutions/16

Basically, this question asks to make a function that drops every N'th element from a list. For example,

*Main> dropEvery "abcdefghik" 3

"abdeghk"

The first solution in the link is

dropEvery :: [a] -> Int -> [a]
dropEvery [] _ = []
dropEvery (x:xs) n = dropEvery' (x:xs) n 1 
  where
       dropEvery' (x:xs) n i = (if (n `divides` i) then [] else [x])++ (dropEvery' xs n (i+1))
       dropEvery' [] _ _ = []
       divides x y = y `mod` x == 0

My question is why dropEvery defines the case of empty lists while dropEvery' can take care of empty list? I think dropEvery [] _ = [] can be simply eliminated and modifying a bit of other sentences as following should work exactly the same as above and looks shorter.

dropEvery :: [a] -> Int -> [a]
dropEvery xs n = dropEvery' xs n 1 
  where
       dropEvery' (x:xs) n i = (if (n `divides` i) then [] else [x])++ (dropEvery' xs n (i+1))
       dropEvery' [] _ _ = []
       divides x y = y `mod` x == 0

Can anyone help me figure out about this?

Upvotes: 6

Views: 695

Answers (1)

Tarrasch
Tarrasch

Reputation: 10547

I think they are the same and the author could have simplified the code as you suggested. For the heck of it I tried both versions with QuickCheck and they seem to be the same.

import Test.QuickCheck

dropEvery :: [a] -> Int -> [a]
dropEvery [] _ = []
dropEvery (x:xs) n = dropEvery' (x:xs) n 1 
  where
       dropEvery' (x:xs) n i = (if (n `divides` i) then [] else [x])++ (dropEvery' xs n (i+1))
       dropEvery' [] _ _ = []
       divides x y = y `mod` x == 0

dropEvery2 :: [a] -> Int -> [a]
dropEvery2 xs n = dropEvery' xs n 1 
  where
       dropEvery' (x:xs) n i = (if (n `divides` i) then [] else [x])++ (dropEvery' xs n (i+1))
       dropEvery' [] _ _ = []
       divides x y = y `mod` x == 0

theyAreSame xs n = (dropEvery xs n) == (dropEvery2 xs n)
propTheyAreSame xs n = n > 0 ==> theyAreSame xs n

And in ghci you can do

*Main> quickCheck propTheyAreSame 
+++ OK, passed 100 tests.

I also tested a few corner cases by hand

*Main> dropEvery [] 0
[]
*Main> dropEvery2 [] 0
[]
*Main> dropEvery [] undefined
[]
*Main> dropEvery2 [] undefined
[]

So them seem to the same.

So our learning outcomes:

  1. Quickcheck is perfect for this kind of stuff
  2. Don't underestimate yourself. :)

Upvotes: 7

Related Questions