tags:

views:

154

answers:

5

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.
+2  A: 
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)
Matt
+1  A: 

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
gawi
Apparently, Matt has edited his answer while I was typing mine.
gawi
Yours looks better. Haha. But can you explain what $ is. Still new to haskell myself. Thanks.
Matt
From the haskell98 report: $ has low, right-associative binding precedence, so it sometimes allows parentheses to be omitted; for example: f $ g $ h x = f (g (h x))
gawi
A: 

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.

Travis Brown
This could also be modified to eliminate the division and the separate call to length. The basic strategy I have in mind would be to implement a `dropExact :: Int -> [a] -> Maybe [a]` function and call it repeatedly with successive powers of 2 (starting off with an extra `1`). Ultimately the operation would terminate with either `Nothing` (indicating an invalid length) or `Just []` (indicating success, with length equal to the next power of 2 that would've been dropped).
mokus
A: 

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).

mokus
I got myself curious about the speed of this strategy vs. logBase, so I threw together a quick and dirty criterion test. For input randomly distributed from 0 to 2^31, this strategy is about twice as fast as using logBase on my system. In practice it would typically be faster, since typical lists will be far shorter than that, and this implementation is faster on shorter lists.
mokus
+1  A: 

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)

Piet Delport