Haskell - Collatz Conjecture and how to read my error message

user_6530372 0
Viewed 328

I'm trying to learn Haskell and doing some exercises. One of those exercises is to write a function that "Calculates the number of steps to reach 1 using the Collatz conjecture." Source

The Collatz conjecture is a conjecture in mathematics that concerns sequences defined as follows: start with any positive integer n. Then each term is obtained from the previous term as follows: if the previous term is even, the next term is one half of the previous term. If the previous term is odd, the next term is 3 times the previous term plus 1. The conjecture is that no matter what value of n, the sequence will always reach 1.

My solution is:

collatzConjecture :: (Integral a1, Fractional a1, Num a2) => a1 -> a2
collatzConjecture x = collatzConjecture' x 0
    where 
        collatzConjecture' 1 n = n
        collatzConjecture' x n
            | odd x = collatzConjecture' (x*3+1) (n+1)
            | even x = collatzConjecture' (x/2) (n+1)

But when I try to use the function I get the following error:

ghci> collatzConjecture 5

<interactive>:6:1: error:
    * Could not deduce (Integral a10)
        arising from a use of `collatzConjecture'
      from the context: Num a2
        bound by the inferred type of it :: Num a2 => a2
        at <interactive>:6:1-19
      The type variable `a10' is ambiguous
      These potential instances exist:
        instance Integral Integer -- Defined in `GHC.Real'
        instance Integral Int -- Defined in `GHC.Real'
        instance Integral Word -- Defined in `GHC.Real'
        ...plus one instance involving out-of-scope types
        (use -fprint-potential-instances to see them all)
    * In the expression: collatzConjecture 5
      In an equation for `it': it = collatzConjecture 5

<interactive>:6:19: error:
    * Could not deduce (Num a10) arising from the literal `5'
      from the context: Num a2
        bound by the inferred type of it :: Num a2 => a2
        at <interactive>:6:1-19
      The type variable `a10' is ambiguous
      These potential instances exist:
        instance Num Integer -- Defined in `GHC.Num'
        instance Num Double -- Defined in `GHC.Float'
        instance Num Float -- Defined in `GHC.Float'
        ...plus two others
        ...plus two instances involving out-of-scope types
        (use -fprint-potential-instances to see them all)
    * In the first argument of `collatzConjecture', namely `5'
      In the expression: collatzConjecture 5
      In an equation for `it': it = collatzConjecture 5

My question now is where did I go wrong and how do I even read the error message?

haskell
1 Answers

While technically possible, it makes no sense that a type is both a member of the Integral typeclass and the Fractional typeclass.

The reason that a1 is fractional is because you use x / 2 and (/) :: Fractional a => a -> a -> a requires that the two operands and the result have the same type, and that that type is a member of the Fractional typeclass.

You can make use of div :: Integral a => a -> a -> a to perform integral division:

collatzConjecture :: (Integral a, Num b) => a -> b
collatzConjecture x = collatzConjecture' x 0
    where 
        collatzConjecture' 1 n = n
        collatzConjecture' x n
            | odd x = collatzConjecture' (x*3+1) (n+1)
            | even x = collatzConjecture' (div x 2) (n+1)
user_675790
Related