 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2016/functional-programming-design-and-analysis-of-algorithms-resit/2/a/solution

All three Haskell definitions have filter :: (a -> Bool) -> [a] -> [a]. A recursive list filter is

filter p [] = []
filter p (x:xs)
  | p x       = x : filter p xs
  | otherwise = filter p xs

A list comprehension gives filter p xs = [x | x <- xs, p x]. A right fold gives

filter p = foldr (\x ys -> if p x then x:ys else ys) []

Each version retains the input order and needs no equality or Haskell Ord class constraint on the element type.

 New to topics? Read the docs here!