3n+1 implementing with Haskell, compile error

Question

everyone. I'm a newcomer to Haskell and just implemented the '3n + 1' problem with it. I checked a lot but the type error seemed strange, could you please help me find what the problem is?

import qualified Data.Vector as V
import qualified Data.Matrix as M

nMax = 1000000

table = V.fromList $ 0 : 1 : [cycleLength x | x <- [2 .. nMax]] where
    cycleLength x = if x' <= nMax then table V.! x' + 1 else cycleLength x' + 1 where 
        x' = if even x then x `div` 2 else 3 * x + 1

sparseTable = M.fromLists $ [] : [[f i j | j <- [0 .. ceiling $ logBase 2 nMax]] | i <- [1 .. nMax]] where
    f i 0 = table V.! i
    f i j = maxValue i j

maxValue i j = max $ (leftValue i j) (rightValue i j) where
    leftValue i j = sparseTable M.! (i, j - 1)
    rightValue i j = sparseTable M.! (i + 2 ^ (j - 1), j - 1)

I used the Vector and Matrix (download with cabal) modules to implement the functions. I think the first function (table) has been proved that no mistakes in it, probably mistakes are in the last two function, which I used to implement the sparse table algorithm.

Since I just signed up and don't have enough reputation now, I just paste the error message here:

[1 of 1] Compiling Main             ( 001.hs, interpreted )

001.hs:14:39:
    Occurs check: cannot construct the infinite type: s0 ~ s0 -> s0
    Relevant bindings include
      leftValue :: Int -> Int -> s0 -> s0 (bound at 001.hs:15:9)
      rightValue :: Int -> Int -> s0 -> s0 (bound at 001.hs:16:9)
      maxValue :: Int -> Int -> s0 -> s0 (bound at 001.hs:14:1)
    In the third argument of ‘leftValue’, namely ‘(rightValue i j)’
    In the second argument of ‘($)’, namely
      ‘(leftValue i j) (rightValue i j)’
Failed, modules loaded: none.

In the `maxValue` function, get rid of the `$`, it's causing the error you have displayed. — randomusername, Oct 14 '14 at 19:59

score 4 · Accepted Answer · edited May 23 '17 at 12:11

4

The problem is the $ in max $ (leftValue i j) (rightValue i j).

The ($) operator binds less tightly than any other operator, including the 'normal function application you get when you just use a space.

So with the $, it parses as

max ((leftvalue i j) (rightValue i j))

if you remove it that should parse as you intended, which was presumably

max (leftValue i j) (rightValue i j)

You can get a hint of this from the error message, where it talks about the "third argument of leftValue".

There's some more information about ($) in When should I use $ (and can it always be replaced with parentheses)?

edited May 23 '17 at 12:11

Community

1
1

answered Oct 14 '14 at 19:59

Ganesh Sittampalam

28,821
4
79
98

It's worth noting that this _could_ be written as `max (leftValue i j) $ rightValue i j`, if a `$` was really desired. Alternatively, you can avoid parentheses altogether with ```leftValue i j `max` rightValue i j```, but I find this harder to read – bheklilr Oct 14 '14 at 20:02
Thank you very much, the problem solved. However new problems occured, I think I should get more practice in Haskell....:) – kiss_lawrence Oct 15 '14 at 07:41

3n+1 implementing with Haskell, compile error

1 Answers1