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))
