Haskell 2014.0.0: Two 'Could not deduce' errors occur when executing simple function

Question

I want to program a function 'kans' (which calculates the chance of a repetition code of length n being correctly decoded) the following way:

fac 0 = 1
fac n = n * fac (n-1)

comb n r = ceiling (fac n / ((fac (n - r))*(fac r)))

kans 0 = 1
kans n = sum [ (comb (n+1) i) * 0.01^i * 0.99^(n+1-i) | i <- [0..(div n 2)]]

Now, calling 'kans 2' in GHCi gives the following error message: https://i.sstatic.net/PHEES.jpg The functions 'fac' and 'comb' function normally. I even get an error message when I call 'kans 0', which I defined seperately.

I would greatly appreciate your help.

Answer 1

short dirty answer:

because both fac and comb always return Integers and only accept Integers, use this code:

fac 0 = 1
fac n = n * fac (n-1)


comb n r =fac n `div` ((fac (n - r))*(fac r))

kans 0 = 1
kans n = sum [ fromIntegral (comb (n+1) i) * 0.01^i * 0.99^(n+1-i) | i <- [0..(div n 2)]]

actual explanation:
looking at your error messages, GHC complains about ambiguity.

let's say you try to run this piece of code:

x = show (read "abc")

GHC will complain that it can't compute read "abc" because it doesn't have enough information to determine which definition of read to use (there are multiple definitions ; you might want to read about type classes, or maybe you already did. for example, one of type String -> Int which parses Integers and one of type String -> Float etc.). this is called ambiguity, because the result type of read "abc" is ambiguous.

in Haskell, when using arithmetic operators (which like read usually have multiple definitions in the same way) there is ambiguity all the time, so when there is ambiguity GHC checks if the types Integer or Float can be plugged in without problems, and if they do, then it changes the types to them, resolving the ambiguity. otherwise, it complains about the ambiguity. this is called defaulting. the problem with your code is that because of the use of ceiling and / the types require instances of Fractional and RealFrac while also requiring instances of Integral for the same type variables, but no type is instance of both at once, so GHC complains about ambiguity. the way to fix this would be to notice that comb would only work on whole numbers, and that (fac n / ((fac (n - r))*(fac r))) is always a whole number. the ceiling is redundant. then we should replace / in comb's definition by \div`` to express that only whole numbers will be the output.

the last thing to do is to replace comb (n+1) i with fromIntegral (comb (n+1) i) (fromIntegral is a function which casts whole numbers to arbitrary types) because otherwise the types would mismach again - adding this allowes us to separate the type of comb (n+1) i (which is a whole number) from the type of 0.01^i which is of course a floating-point number.

this solves all problems and results in the code I wrote above in the "short dirty answer" section.

Answer 2

The error messages both contain telling parts of the form

Could not deduce [...]
    from the context (Integral a, Fractional a)

This says that you are trying to use a single type as both a member of the class Integral and as a member of the class Fractional. There are no such types in Haskell: The standard numerical types all belong to exactly one of them. And you are using operations that require one or the other:

• / is "floating point" or "field" division, and only works with Fractional.
• div is "integer division", and so works only with Integral.
• the second argument of ^ must be Integral.

What you probably should do is to decide exactly which of your variables and results are integers (and thus in the Integral class), and which are floating-point (and thus in the Fractional class.) Then use the fromIntegral function to convert from the former to the latter whenever necessary. You will need to do this conversion in at least one of your functions.

On mathematical principle I recommend you do it in kans, and change comb to be purely integral by using div instead of /.

As @Mephy suggests, you probably should write type signatures for your functions, this helps make error messages clearer. However Num won't be enough here. For kans you can use either of

kans :: Integer -> Double
kans :: (Integral a, Fractional b) => a -> b

The latter is more general, but the former is likely to be the two specific types you'll actually use.