11

In the following snippet, you can see my two collatz functions I wrote in Haskell. For the recursive application I used parentheses in the first example (collatz) to get the right precedence.

As I have just learnt function application with $, I tried to rewrite the function (collatz') using that thing. However, I encounter the following error:

Couldn't match expected type `[a]' against inferred type `a1 -> [a1]' In the second argument of `(:)', namely `collatz'' In the first argument of `($)', namely `n : collatz'' In the expression: n : collatz' $ n `div` 2

collatz :: (Integral a) => a -> [a]

collatz 1 = [1]

collatz n | even n    = n : collatz (n `div` 2)
          | otherwise = n : collatz (n * 3 + 1)

collatz' :: (Integral a) => a -> [a]

collatz' 1 = [1]

collatz' n | even n    = n : collatz' $ n `div` 2
           | otherwise = n : collatz' $ n * 3 + 1

It seamed weird to me that this didn't work. So I tried a similar example that worked:

True : [even $ 3 `div` 3]

I'd appreciate it, if somebody could take a look at it and tell me what I'm doing wrong.

Improve this question
2
  • 4
    Of topic comment: it might be cleaner code to have the collatz function just calculate the next step (so collatz :: Integral => a -> a ) and then build the lists in a separate step using something like takeWhile (/= 1) . iterate Commented Dec 4, 2011 at 21:38
  • 2
    Although sometimes $ can eliminate parens, it cannot always do so, and other times it is simply cleaner to use parens. Commented Dec 5, 2011 at 5:22

4 Answers 4

Reset to default
18

$ has lower precedence then : (and also anything else) so your function is parsing as

(n : collatz') $ (n `div` 2)

This leads to your type error. The second argument of : expects a list but you are passing the collatz function instead.

If you still want to avoid the parenthesis around the 3n+1 part you can do something like the following

(n:) . collatz' $ n `div` 2
n : (collatz' $ n `div` 2)

although these are not necessarily cleaner then the original. In case you are wondering, the (n:) in the first example is a syntactic sugar for \x -> n : x

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

10

Since others have explained what the problem is, I figured I'll explain how you could have figured this out on your own. (Teaching a man to fish and so on...)

Note this part of the error message:

In the first argument of '($)', namely 'n : collatz''

That's the clue to noticing that this is a precedence problem. GHC is telling you that n : collatz' was parsed as the first argument of $, while you were expecting the first argument to be just collatz'.

At this point, I usually fire up GHCi and check the precedences involved using the :info command:

> :info :
data [] a = ... | a : [a]   -- Defined in GHC.Types
infixr 5 :
> :info $
($) :: (a -> b) -> a -> b   -- Defined in GHC.Base
infixr 0 $

It says that the precendence of : is 5, while the precedence of $ is 0, which explains why the : is binding "tighter" than the $.

Improve this answer

Comments

6

: binds more strongly than $. Consider

Prelude> let f x = [x]
Prelude> 1 : f 2
[1,2]
Prelude> 1 : f $ 2

<interactive>:1:5:
    Couldn't match expected type `[a0]' with actual type `t0 -> [t0]'
    In the second argument of `(:)', namely `f'
    In the expression: 1 : f
    In the expression: 1 : f $ 2

Note the "expression" 1 : f found by the parser; it sees (1 : f) $ 2 rather than 1 : (f $ 2).

Improve this answer

Comments

3

As @missingno stated, it's an operator precedence problem. You could rewrite it like this

collatz' n | even n    = n : (collatz' $ n `div` 2)
           | otherwise = n : (collatz' $ n * 3 + 1)

But that obviously doesn't buy you much, because you still have parenthesis.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.