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.
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:
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 justcollatz'
.At this point, I usually fire up GHCi and check the precedences involved using the
:info
command:It says that the precendence of
:
is 5, while the precedence of$
is 0, which explains why the:
is binding "tighter" than the$
.$
has lower precedence then:
(and also anything else) so your function is parsing asThis 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
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
As @missingno stated, it's an operator precedence problem. You could rewrite it like this
But that obviously doesn't buy you much, because you still have parenthesis.
:
binds more strongly than$
. ConsiderNote the "expression"
1 : f
found by the parser; it sees(1 : f) $ 2
rather than1 : (f $ 2)
.