Pattern-matching with (higher-order) functions in Haskell

Question

I'm trying to learn a bit of Haskell with the online book "Learn you a Haskell" and I have a question about higher-order functions.

I saw some examples and I want to do a few more advanced functions but I don't know why I always read the following exception:

*** Exception: euler13.hs:(11,0)-(15,39): Non-exhaustive patterns in function apply

And the function I defined is this one:

apply :: (Num b, Ord b) => (a -> a) -> b -> [a] -> [a]
apply f n [] = []
apply f n [x]
    | n <= 1    = map f [x]
    | otherwise = apply f (n-1) (map f [x])

I want to apply 'n' times a concrete function called 'f' to a list '[x]'. I tried to make this function polymorphic so the type of the param is 'a'. But I want to use numbers and lists also, so directly I'm using a list (if I want to use the function just for a number, it would be [number] obviously)

Could anybody help me please? I love this language but it's a bit difficult when you are learning because it's so different of Java or c (for example)

Thanks!

Answer 1

Remove the [] around the x. Otherwise the 2nd pattern can only match lists with 1 element only.

apply f n x
    | n <= 1    = map f x
    | otherwise = apply f (n-1) (map f x)

Answer 2

This is no different from what others have said, but maybe the point should be labored? There are two basic 'constructors' for lists, and thus two basic cases you need to consider in defining functions from lists: arguments of the form [] and (:). the latter, (:) can join anything with a list of that kind of thing, thus 1 with [] -- 1:[] or [1]. Or it can join 1 with something of just that kind: 1:(1:[]) i.e. 1:[1], i.e. [1,1] as the special syntax lets us write.

It would be more obvious what would had gone wrong if you had defined lists yourself, writing:

data List a = Nil | Cons a (List a) deriving (Show, Eq, Ord)

The use of [] and x:xs is just swank sugar for something like this. Similarly, the special String sugar lets us write "abc" rather than ['a','b','c'], which is way better than 'a':'b':'c':[]. (With the above definition we would have to write Cons 'a' (Cons 'b' (Cons 'c' Nil))) which is a bit much for a short string! -- though it also brings out why one should prefer ByteString and Text representations of strings for many purposes.) With a more verbose list definition like this, we need to add our own map (or rather fmap), so we can say

instance Functor List where 
   fmap f Nil = Nil
   fmap f (Cons first rest) = Cons (f first) (fmap f rest)

Notice that in defining fmap for this case I had to consider both types of constructor for my List type, Nil and Cons first rest (or Cons x xs as it is often written).

Or maybe you haven't got up to the general discussion of the Functor type class in LYAH -- in that case, just consider that you can define your own map as

listMap f Nil = Nil
listMap f (Cons first rest) = Cons (f first) (listMap f rest)

In any case, given this desugared rewrite of the list type, your actual function definition would be:

apply :: (Num b, Ord b) => (a -> a) -> b -> List a -> List a
apply f n Nil = Nil
apply f n (Cons first Nil)
    | n <= 1    = fmap f (Cons first Nil)  -- or listMap f (Cons first Nil)
    | otherwise = apply f (n-1) (fmap f (Cons first Nil))

The cases you have covered are:

apply f n Nil 
apply f n (Cons first Nil)

Cons first Nil is the same as first : [] or [first] -- i.e. [x] as you write it. But this means you haven't covered every case, your definition is 'non-exhaustive'. You haven't said how to apply f and n to a list if it has more than one member. What if a list has the form Cons x (Cons y Nil) or Cons x (Cons y (Cons z Nil)) rather than Nil (your first line) or Cons x Nil (your second line)?

The solution is as others said, or using our desugared list-type:

apply :: (Num b, Ord b) => (a -> a) -> b -> List a -> List a
apply f n Nil = Nil
apply f n (Cons first rest)
    | n <= 1    = fmap f (Cons first rest)
    | otherwise = apply f (n-1) (fmap f (Cons first rest))

Here the 'variable' rest covers all lists, Nil or not. Thus we get:

*Main> apply (+1) 3 Nil
Nil
*Main> apply (+1) 3 (Cons 3 Nil)
Cons 6 Nil

as you would, but also:

*Main> apply (+1) 3 (Cons 0 (Cons 1 (Cons 2 Nil)))
Cons 3 (Cons 4 (Cons 5 Nil))