Haskell - Filtering Odds in function that shows powers of 2

user_15891293 0
Viewed 66

I have this developed function that shows the powers of 2 from the range you choose:

import Data.Bits(Bits, (.&.))
isPower2 :: (Bits i, Integral i) => i -> Bool
isPower2 n = n .&. (n-1) == 0

This works well but i need to filter only the powers of 2 from odds numbers of the range choosed, for example :

filter isPower2 [0 .. 1000]
[0,1,2,4,8,16,32,64,128,256,512]

This input and output above shows all the powers between 0 and 1000 but what i need is only the powers from odds, so my output that i need is:

[2,8,32,128,512]

Is there a way to filter this function pointing only to odds numbers? Thanks.

haskell
2 Answers

I'd recommend first writing a function that checks whether a power of two is odd power of two.

power2isOddPower2 :: (Bits i, Integral i) => i -> Bool

Maybe first think how to do this for the concrete case Word8, then generalize it to arbitrary positive integers.

Then you can combine this to a predicate that checks whether an arbitrary number is an odd power of two, and use that for the filtering:

filter (\n -> isPower2 n && power2isOddPower2 n) [0 .. 1000]
user_7459030

That's a clever algorithm for checking whether a number is a power of 2. But unfortunately, it's not well suited to this kind of further analysis. So I'm going to propose a slightly different technique. Let's split the problem into pieces. Haskell has a power function called (^) (actually, it has three that are subtly different, but for our purposes the simplest one will do just fine). So let's start by getting all of the powers of two. Yes, all of them.

> map (2 ^) [0..]
[1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,...]

That's an infinite list, which Haskell has no problem with. If you run it in GHCi, you'll need to hit Ctrl+C to stop it from outputting forever.

Now we want to take the ones smaller than some limit.

> takeWhile (< 1000) $ map (2 ^) [0..]
[1,2,4,8,16,32,64,128,256,512]

takeWhile is a function which, as the name implies, stops once the condition is false. It's like filter, but once it encounters one false value, it stops completely (filter will never terminate on infinite lists, because it insists on checking every value).

So now we have a way to get the list you have in the OP. But we started with the powers ([0..]). So if we want to filter some powers, we can add a filter to the right-hand side

> takeWhile (< 1000) . map (2 ^) . filter (\x -> x `mod` 2 == 1) $ [0..]
[2,8,32,128,512]

Of course, we would want to split this into a few helper functions (isOdd, for instance, is pretty easy to factor out into a where clause), as it's getting a bit long on its own. But that's the basic idea.

user_22886590
Related