Haskell's if statement for error checking

Question

I wrote a function for the Haar wavelet transformation given that the input is a List with a power of 2. I was trying to error check by making sure that the length of the List is a power of 2 before preforming the transformation. I am comparing the log base 2 of the length of the list to see if it comes out evenly (nothing to the right of the decimal point). I think there is something going on with the if statement in haskell that I am not used to in other languages. It works perfectly if I don't error check and just call haar with the proper argument.

haar :: (Fractional a) => [a] -> [a]
haar xs = if logBase 2 (fromIntegral (length xs)) /= truncate (logBase 2 (fromIntegral (length xs)))
             then error "The List must be a power of 2"
             else haarHelper xs (logBase 2 (fromIntegral (length xs)))

haarHelper xs 1 = haarAvgs xs ++ haarDiffs xs
haarHelper xs level = haarHelper (haarAvgs xs ++ haarDiffs xs) (level - 1)

haarAvgs [] = []
haarAvgs (x:y:xs) = ((x + y) / 2.0) : haarAvgs xs 

haarDiffs [] = []
haarDiffs (x:y:xs) = ((x - y) / 2.0) : haarDiffs xs

I am getting the following error message:

functions.hs:52:13:
    Ambiguous type variable `t' in the constraints:
      `Floating t'
        arising from a use of `logBase' at functions.hs:52:13-48
      `Integral t'
        arising from a use of `truncate' at functions.hs:52:53-99
    Probable fix: add a type signature that fixes these type variable(s)
Failed, modules loaded: none.

Answer 1

haar :: (Fractional a) => [a] -> [a]
haar xs | r /= (truncate r) = error "The List must be a power of 2"
        | otherwise = haarHelper xs (logBase 2 (fromIntegral (length xs)))
            where r = logBase 2 (fromIntegral (length xs))

Yea, seems like its something with truncate. Easier way to write if then statements with haskell is shown above. Might help with the debugging a bit.

I think i may know. I think truncate is returning an int where the other number is a float.

Try this

haar :: (Fractional a) => [a] -> [a]
haar xs | r /= w = error "The List must be a power of 2"
        | otherwise = haarHelper xs (logBase 2 (fromIntegral (length xs)))
            where 
                r = logBase 2 (fromIntegral (length xs))
                w = intToFloat (truncate r) 

haarHelper xs 1 = haarAvgs xs ++ haarDiffs xs
haarHelper xs level = haarHelper (haarAvgs xs ++ haarDiffs xs) (level - 1)

haarAvgs [] = []
haarAvgs (x:y:xs) = ((x + y) / 2.0) : haarAvgs xs 

haarDiffs [] = []
haarDiffs (x:y:xs) = ((x - y) / 2.0) : haarDiffs xs

intToFloat :: Int -> Float
intToFloat n = fromInteger (toInteger n)

Answer 2

To complement Matt's answer:

haar :: (Fractional a) => [a] -> [a]
haar xs | r /= (fromIntegral $ truncate r) = error "The List must be a power of 2"
        | otherwise = haarHelper xs r
            where r = logBase 2 (fromIntegral (length xs))

1. Convert the Integral result of truncate using fromIntegral
2. You can use the definition of r in haarHelper xs r

Answer 3

Here's a version of haar that I'll argue is a little nicer:

haar :: (Fractional a) => [a] -> [a]
haar xs = maybe (error "The List must be a power of 2")
                (haarHelper xs)
                (intLogBase 2 $ length xs)

intLogBase :: (Integral a) => a -> a -> Maybe Int
intLogBase b n = intLogBase' b 1 n
  where
    intLogBase' b p 1 = Just p
    intLogBase' b p n
      | r /= 0    = Nothing
      | otherwise = intLogBase' b (p + 1) q 
      where (q, r) = quotRem n b

intBaseLog is a variation of baseLog that works for integers and returns Nothing if the given number isn't a power of the given base. Otherwise it returns the power wrapped in a Just. Unlike with logBase and truncate there's no conversion to floating point numbers: we've got integers all the way through.

The maybe function in Haar takes three arguments. It will evaluate its last argument, and if it's a Nothing it will return the first argument (in this case the error). If the last argument evaluates to a Just, it applies the second argument to the thing inside the Just and returns that.

Answer 4

The problem here is unrelated to the if expression. As mentioned in other answers, it is in your condition where you compare "logBase (...)" to "truncate (logBase (...))". One returns a Floating type, the other returns an Integral type. There are no types (in the standard libraries) that implement both classes, so that condition can't be well-typed as-is.

A pattern I use occasionally when working with powers of two is to keep a list of powers of two and just check whether the number is in that list. For example:

powersOfTwo :: [Integer]
powersOfTwo = iterate (*2) 1
isPowerOfTwo x = xInt == head (dropWhile (<xInt) powersOfTwo)
    where xInt = toInteger x

I haven't tested, but my gut tells me that for most purposes this is probably faster than "logBase 2". Even if not, it's more appropriate because it doesn't involve any floating-point math. In particular, your current approach isn't going to work even with the types fixed: truncate (logBase 2 512) == truncate (logBase 2 550) (Edit: although I think I probably misunderstood your intent when I wrote this at first, i realize now that you probably meant to check whether logBase 2 (...) is an exact integer value by comparing the truncated version to a non-truncated version, not by comparing to any known value).

Answer 5

There's a much simpler and faster implementation to check that a positive integer is a power of two:

import Data.Bits

powerOfTwo' n = n .&. (n-1) == 0

(Note: this omits the check that n is positive, assuming we can rely on it coming from length.)

Explanation, for the curious:

This algorithm relies on the unique property that only powers of 2 have a single 1 bit (by definition), and decrementing them inverts all the lower bits:

2^n      =  100000...
2^n - 1  =  011111...

This leaves no bits in common, making their bitwise-and zero.

For all non-powers-of-two, the decrement will leave at least the highest 1 bit unchanged, keeping the bitwise-and result non-zero.

(Wikipedia: Fast algorithm to check if a positive number is a power of two)