Haskell: Function application with $

Question

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.

Answer 1

$ 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

Answer 2

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 $.

Answer 3

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

Answer 4

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.