Comparing templates with functions (higher order) in Haskell

Question

I'm trying to learn a bit of Haskell with the online book Teach You Haskell, and I have a question about higher features.

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

*** Exception: euler13.hs: (11.0) - (15.39): Non-exhaustive templates in the function apply

And the function I define is this:

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

I want to apply "n" to a specific function called "f" to the list "[x]". I tried to make this function polymorphic, so the parameter type is "a". But I also want to use numbers and lists, so I use the list directly (if I want to use the function only for a number, it will be [number] obviously)

Can someone help me? I like this language, but it's a little complicated when you study, because it is different from Java or c (for example)

Thanks!

Answer 1

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

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

Answer 2

This is no different from what others have said, but maybe it should be difficult? There are two main “constructors” for lists and, therefore, two main cases that you need to consider when defining functions from lists: form arguments [] and (:) . the last one, (:) can join everything with a list of these kinds of things, thus 1 s [] - 1:[] or [1] . Or he can join 1 with something like this: 1:(1:[]) ie 1:[1] , i.e. [1,1] , as the special syntax allows.

It would be more obvious what would be wrong if you yourself defined the lists by writing:

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

Using [] and x:xs is just spicy sugar for something like that. Similarly, special String sugar allows you to write "abc" rather than ['a','b','c'] , which is 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 for a short string!), Although it also explains why ByteString and Text should be preferred for string representation for many goals.) With a more detailed 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) 

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

Or maybe you didn’t get to the general discussion of a class like Functor in LYAH - in this case, just think 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 canceled list type correspondence, your actual function definition will be:

 apply :: (Num b, Ord b) => (a -> a) -> b -> List a -> List a apply fn Nil = Nil apply fn (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)) 

You have considered the following cases:

 apply fn Nil apply fn (Cons first Nil) 

Cons first Nil matches first : [] or [first] - i.e. [x] when you write it. But this means that you did not cover all cases, your definition of "is not exhaustive." You did not say how to apply f and n to a list if it contains more than one member. What if the list is of the form Cons x (Cons y Nil) or Cons x (Cons y (Cons z Nil)) , and not Nil (your first line) or Cons x Nil (second line)?

The solution is similar to how others have indicated, or using our list type:

 apply :: (Num b, Ord b) => (a -> a) -> b -> List a -> List a apply fn Nil = Nil apply fn (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 obtain:

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

like you, but also:

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

Answer 3

You define apply for two cases: n and the empty list, and n and the list of one element. What happens when a list contains more than one item? This is the missing template.

Answer 4

This is not a new answer compared to others, but hopefully it is insightful nonetheless.

You have already demonstrated some understanding of pattern matching in function definitions; when the first pattern does not match, the evaluation proceeds to the next. Patterns that may not match are considered “refutable”.

Generally, it’s a good idea to have your last function definition “incontrovertible,” which means that it always matches. From the Haskell 2010 report:

Irrefutable patterns are as follows: variable, wildcard, N apat, where N is the constructor defined by newtype and apat, irrefutable, var @apat where apat is irrefutable, or forms ~ apat. All other patterns are refutable.

Your misunderstanding was that you thought that [x] is a variable (irrefutable pattern) when it is actually a rebuttable pattern (a template for a one-element list that binds x to this single element).

Suppose you wrote a function that works only on lists of length 3. If you need a more descriptive error message than "non-exhaustive patterns", you can use an irrefutable wildcard (underscore) pattern. Trivial example:

 sum3 [x,y,z] = x+y+z sum3 _ = error "sum3 only works on lists of length 3"