2

I'm starting to learn Haskell using the University of Pennsylvania's free online course materials. These have been put online deliberately so I presume I'm not helping anyone's homework by asking this question.

I get a number of compiler errors from the following function, which I'm using to answer part of the first assignment, and I can't figure out why. My function is:

doubleEveryOther :: [Integer] -> [Integer]
doubleEveryOther [] = []
doubleEveryOther [x] = [x]
doubleEveryOther [x:y] = [x:(y*2)]
doubleEveryOther [x:y:ys] = [x:y*2:doubleEveryOther ys]

The errors I get are:

01.hs:18:19:
    Couldn't match expected type ‘Integer’ with actual type ‘[a0]’
    In the pattern: x : y
    In the pattern: [x : y]
    In an equation for ‘doubleEveryOther’:
        doubleEveryOther [x : y] = [x : (y * 2)]

01.hs:18:27:
    Couldn't match expected type ‘Integer’ with actual type ‘[a0]’
    Relevant bindings include
      y :: [a0] (bound at 01.hs:18:21)
      x :: a0 (bound at 01.hs:18:19)
    In the expression: x : (y * 2)
    In the expression: [x : (y * 2)]
    In an equation for ‘doubleEveryOther’:
        doubleEveryOther [x : y] = [x : (y * 2)]

01.hs:19:19:
    Couldn't match expected type ‘Integer’ with actual type ‘[Integer]’
    In the pattern: x : y : ys
    In the pattern: [x : y : ys]
    In an equation for ‘doubleEveryOther’:
        doubleEveryOther [x : y : ys] = [x : y * 2 : doubleEveryOther ys]

01.hs:19:30:
    Couldn't match expected type ‘Integer’ with actual type ‘[Integer]’
    In the expression: x : y * 2 : doubleEveryOther ys
    In the expression: [x : y * 2 : doubleEveryOther ys]
    In an equation for ‘doubleEveryOther’:
        doubleEveryOther [x : y : ys] = [x : y * 2 : doubleEveryOther ys]

Can anyone help me understand why my patterns are not matching the right types?

1
  • Too tired for a full answer, sorry, but the following might give you an idea: [x,y], (x:y:ys).
    – Zeta
    Dec 10, 2014 at 22:01

3 Answers 3

3

The problem is simple: [] denotes a list of elements. And : denotes joining an element and a list. So [x:ys] means actually [[x,y1,y2..]] - note double brackets. So it's a list of lists of Integer in your case and not a list of Integer.

doubleEveryOther :: [Integer] -> [Integer]
doubleEveryOther [] = []
doubleEveryOther [x]= [x]
doubleEveryOther [x,y] = [x, y*2]
doubleEveryOther (x:y:ys) = x : y*2 : doubleEveryOther ys

If you want all 4 equations to use the same syntax, then you can't use [] as it doesn't allow ys, so you have to use : everywhere:

doubleEveryOther :: [Integer] -> [Integer]
doubleEveryOther [] = []
doubleEveryOther (x:[])= x:[]
doubleEveryOther (x:y:[]) = x : y*2 : []
doubleEveryOther (x:y:ys) = x : y*2 : doubleEveryOther ys
1
  • [x:ys] means actually [[x,y1,y2..]]. That's not 100% accurate. In the pattern [x:ys], ys can be nil, in which case there is no y1 and y2.
    – jub0bs
    Dec 10, 2014 at 22:25
2

The code should be:

doubleEveryOther :: [Integer] -> [Integer]
doubleEveryOther [] = []
doubleEveryOther [x] = [x]
doubleEveryOther (x:y:[]) = [x, (y*2)]
doubleEveryOther (x:y:ys) = x: y*2 : doubleEveryOther ys

You can't pattern match on a list directly, because the list syntax is just syntax sugar. You have to match on function calls (specifically calls to (:), the cons operator). And those matches need to be enclosed in parentheses.

And you don't enclose cons calls in brackets. [1 : 2 : []] is the same as [[1, 2]]. Just to make it a bit clearer, in your code you have [x : y*2]. x and y are both Ints. But cons (:) is of type (:) :: a -> [a] -> [a]. You're calling it with two Ints, not an Int and a [Int] like you should.

3
  • 1
    [x] is a valid pattern for a singleton list, though; it doesn't have to be (x:[]). Garry got that right.
    – jub0bs
    Dec 10, 2014 at 22:14
  • Thanks, that solves it. Can you elaborate on why your final pattern match works, but using the cons operator in the penultimate match doesn't? I want to make sure I really understand this. Dec 10, 2014 at 22:19
  • Do you mean on the right hand side of the equation? x: (y*2): doubles ys works because it takes the result of doubles, conses y to the front, and then conses x to the front of that. The right of line 4 could be expressed as x: (y*2): [] to express the cons's directly. It takes an empty list, conses on y, then conses on x. But because we already know the entire list, we can use the list syntax sugar to write it directly [x, y*2]. We can't use list syntax sugar on the last line because we don't know the result of doubleEveryOther. Dec 11, 2014 at 3:32
1

In addition, your 3rd line is a part of 4th line, so

doubleEveryOther :: [Integer] -> [Integer]
doubleEveryOther [] = []
doubleEveryOther [x]= [x]
doubleEveryOther (x:y:ys) = x : y*2 : doubleEveryOther ys

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.