Non exhaustive pattern in function noThirds

Question

So, my Problem is, that I have to write a program that filters all 3 * x (3,6,9...) elements from a list. My program looks like:

length'  :: [a] -> Int
length' = foldr (\_ -> (+1)) 0

help_ :: [a] -> [a] -> [a]
help_ (x:xs) [] = help_ (xs) [x]
help_ [] (x) = (x)
help_ (x:xs) (y)
    |((length' [xs]) ==0) = (y)
    |((length' [y]) `mod` 2 ==0) = help_ (xs) (y)
    |otherwise = help_ (xs) (y++[x])

noThirds :: [a] -> [a]
noThirds [x] = help_ [x] []

The compiler accepts this but gives the error "Non exhaustive pattern in function noThirds" when I enter "noThirds [1,2,3,4,5,6,7,8]" . I guess it's cause im missing a variety of "help_ .." but I don't get it. Im grateful for every help! Btw predefined list and arithmetic functions are not allowed.

Answer 1

It's because noThirds only has one pattern, [x] which only matches against a single element list. [x] is exactly equivalent to (x : []). What I think you meant was

noThirds :: [a] -> [a]
noThirda xs = help_ xs []

Answer 2

jozefg has already answered your question. I'll point out a couple more things.

Beware! The expressions

((length' [xs]) ==0)
((length' [y]) `mod` 2 ==0)

evaluate to

(1 ==0)
(1 `mod` 2 ==0)

so they are both false. You want instead

((length' xs) ==0)
((length' y) `mod` 2 ==0)

Also, in functions like these, computing length often leads to a low performance, and is considered poor style. Consider pre-processing your list in this way instead

addPosition :: [a] -> [(Int,a)]
addPosition xs = go 0 xs
    where go n []     = ...
          go n (y:ys) = ...
-- Example: addPosition [33,66,20] ===> [(0,33),(1,66),(2,20)]
-- This is equivalent to (zip [0..]) but we can not use list functions.

Then, add some postprocessing to filter the wanted elements: this is now easier since every element has been tagged by its position.

Answer 3

The structure of a list is:

• the empty list []
• or an element followed by the rest of the list (x:xs)

Use the structure of the list to define the results (by using a guard expression):

noThirds :: [Int] -> [Int]

noThirds [] = []
noThirds (x:xs)
  | x `mod` 3 == 0 = rest
  | otherwise      = x : rest
    where
      rest = noThirds xs

The function now filters out all elements that are divisible by 3.

You probably want to filter all elements at an index divisible by 3. To do this introduce an helper function that passes along the index you are currently at and use the guard on the index instead:

noThirds :: [Int] -> [Int]
noThirds xs = noThirds' xs 1

noThirds' :: [Int] -> Int -> [Int]
noThirds' [] _ = []
noThirds' (x:xs) i
  | i `mod` 3 == 0 = rest
  | otherwise      = x : rest
    where
      rest = noThirds' xs (succ i)

Now you don't need to calculate the length of the list.

More answers on solution 16 of the H-99: Ninety-Nine Haskell Problems: http://www.haskell.org/haskellwiki/99_questions/Solutions/16