99 Haskell problems, problem 18

Question

The problem is here, the solutions are here. I don't see a solution like mine (maybe the 4th), it seems to work though.

-- ---------------------------
-- 18 (**) Extract a slice from a list (idx start from 1)
slice _ _ 0 = []
slice (x:xs) 1 k = x : slice xs 1 (k-1)
slice (x:xs) i k = slice xs (i-1) (k-1)

I tried testing it with QuickCheck against the drop/take solution, but it gives up because of the very restrictive conditions (1 <= i <= k <= len xs) and I don't want to get deeper in testing right now.

Is this good Haskell code? Am I forgetting any edge case? (...should I suggest it on the solutions wiki?)

Answer 1

Yes you forgot to cover some cases.

Your compiler should be able to detect one of them. Here is what ghc -Wall says:

slice.hs:2:1: Warning:
 Pattern match(es) are non-exhaustive
 In an equation for `slice':
 Patterns not matched: [] _ (GHC.Types.I# #x) with #x `notElem` [0#]
slice.hs:4:8: Warning: Defined but not used: `x'

This version fixes those two warnings:

slice [] _ _ = []
slice _ _ 0 = []
slice (x:xs) 1 k = x : slice xs 1 (k-1)
slice (_:xs) i k = slice xs (i-1) (k-1)

But it is still incorrect, because there is another case that the compiler doesn't warn you about: a negative k value. Your code will return the entire list instead of an empty list.

Consequently, if you use a negative k on an infinite list you get an infinite loop:

> print $ slice [1..] 1 (-1)
[1,2,3,4,5,6,7,8,9,...

• bigstones: Very exhaustive (negative i too is a problem). Indeed, I supposed strictly valid input. +1 also for the -Wall suggestion (which told me about other bad habits I was developing).