CODEWITHSUNDEEP
haskellnumbers
afkbowflexin
afkbowflexin

Reputation: 4089

Haskell Numeric Type Frustration

I'm having an issue with a simple Haskell program. It's supposed to factor a number n-1 into the form (2^r)s where n is a Carmichael number. This isn't really pertinent to my question, but it's what the following set of functions aims to do.

divides::Int->Int->Bool
divides x y = not $ y `mod` x == 0

carmichaeltwos::Int->Int
carmichaeltwos n
    | not $ divides 2 n =0
    | otherwise = (+ 1) $ carmichaeltwos (n/2)

carmichaelodd::Int->Int
carmichaelodd n
    | not $ divides 2 n = n
    | otherwise = carmichaelodd (n/2)

factorcarmichael::Int->(Int, Int)
factorcarmichael n = (r, s)
    where
        nminus = n-1
        r = carmichaeltwos nminus
        s = carmichaelodd nminus

When I try to load this into GHCi, Haskell spits up:

No instance for (Fractional Int)
  arising from a use of `/'
Possible fix: add an instance declaration for (Fractional Int)
In the first argument of `carmichaelodd', namely `(n / 2)'
In the expression: carmichaelodd (n / 2)
In an equation for `carmichaelodd':
    carmichaelodd n
      | not $ divides 2 n = n
      | otherwise = carmichaelodd (n / 2)

I know that the function / has type (/)::(Fractional a)=>a->a->a, but I don't see how to fix my program to make this work nicely.

Also, I realize that I'm basically computing the same thing twice in the factorcarmichael function. I couldn't think of any easy way to factor the number in one pass and get the tuple I want as an answer.

Upvotes: 1

Views: 389

Answers (1)

jwodder
jwodder

Reputation: 57450

To divide two Ints when you know, as in this case, that the dividend is divisible by the divisor, use the div or quot function, i.e., div n 2 or quot n 2. (div and quot differ only in their handling of negative operands when the "true" quotient isn't an integer.)

Also, why are you defining divides as not $ mod y x == 0? Unless you're using a nonstandard meaning of "divides," you should be using just mod y x == 0 — x divides y iff y modulo x is zero.

As for combining carmichaeltwos and carmichaelodd, try using the until function:

factorcarmichael n = until (\(_, s) -> not $ divides 2 s)
                           (\(r, s) -> (r+1, div s 2))
                           (0, n-1)

Upvotes: 5

Related Questions