Decomposing bitfield with Haskell: is recursion the only way to do this?

Question

Here's a program to take a bitfield like 7 and decompose it into the flags [1,2,4]. Ignore that the algorithm for doing this doesn't use bit shifting/is stupid.

Problems: it seems like I have to have the bithelp function for the sole purpose of calling the other ones, since getFlags and findPower both need to be given given a "starter value" as their second argument (since I can't find a good way to make the argument optional on the first try).

Is there any other way to do what they're doing without recursion? Is recursion like this the standard way to "loop" in FP?

I'll be pleased to be shown anything else I'm doing stupidly here:

-- Algorithm:
-- * given any integer:
-- * find largest power of 2 that fits inside the integer
-- * going from largest to smallest powers of 2, progressively substract any power of 2 that can be subtracted until you get to zero
-- * collect these powers and return them as a list
--
-- These represent the bits that are set within the bitfield
-- E.g. bithelp of 51 = [32,16,2,1]
-- process bitfield
bithelp :: Int -> [Int]
bithelp bitfield = getFlags bitfield $ findPower bitfield 0
-- find starting number: largest power of 2 to fit within bits
findPower :: Int -> Int -> Int
findPower bitfield power
 | 2^power > bitfield = 2^last -- when overshoot bitfield, return last power
 | otherwise = findPower bitfield next
 where next = power + 1
 last = power - 1
-- starting with flag, subtracts down the list of flags, returning list of matches
getFlags :: Int -> Int -> [Int]
getFlags currentBits flag
 | currentBits == flag = [flag] -- only one flag left, last item
 | found = [flag] ++ getFlags remainingBits nextFlag
 | not found = getFlags currentBits nextFlag
 where remainingBits = currentBits - flag
 nextFlag = flag `div` 2
 found = currentBits >= flag -- means bits could be substracted
-- get user input and print list of matched bits
main = do
 putStrLn "Bitfield:"
 line <- getLine
 let bitfield = read line :: Int
 let flags = bithelp bitfield
 putStrLn "List of flags:"
 print flags

• Thomas: Is there any other way to do what they're doing without recursion? Is recursion like this the standard way to "loop" in FP? Yes, recursion is the only way to loop in Pure FP languages, however very rarely should you be performing the loop yourself, you should be using higher-order functions such as map and filter to do the looping for you, and to take advantage of stream fusion and more predictable tail-recursion optimisation.
• recursion.ninja: Perhaps use Data.Bits?

Answer 1

A more common way of "initializing" values on the first call is to define an inner worker function.

findPower :: Int -> Int
findPower bitfield = go 0
 where go i = ... -- Note that the bitfield argument is still in scope

Recursion is the standard way to loop in Haskell (so much so that in lots of code you will find locally defined recursive functions named loop), but your code might be more terse without explicit recursion.

Here's my first pass at a rewrite of the findPower function using higher order functions.

findPower :: Int -> Int
findPower i = last . takeWhile (<= i) $ map (2^) [0..]

Note that this function still isn't total, i.e. it will fail when passed Ints <= 0. Your version would recurse until 2^power overflows, whereas mine will fail fast with an empty list exception due to the use of last. It's considered good style to make your Haskell functions total, so here's my second pass.

findPower :: Int -> Maybe Int
findPower 0 = Just 0
findPower i | i < 0 = Nothing
 | otherwise = Just . last . takeWhile (<= i) $ map (2^) [0..]

Using Maybe here is probably overkill, and in fact you probably want your program to crash when given bad input! Here's a final version.

findPower :: Int -> Int
findPower i | i < 0 = error "findPower: Can't find power of negative number"
 | i == 0 = 0
 | otherwise = last . takeWhile (<= i) $ map (2^) [0..]

On this line | found = [flag] ++ ..., if you're adding a single element to the front of a list, this is just regular cons! Use | found = flag : ... instead.

You've defined a lot of constants in where clauses for your two functions which only get used once. Sometimes it can be helpful to give a name to something that might be non-obvious, but in this case it makes your code longer and arguably adds a bit of cognitive overhead to what are very simple transformations. For instance, I would consider this more readable.

getFlags currentBits flag | currentBits == flag = [flag]
 | currentBits > flag = flag : getFlags (currentBits - flag) (flag `div` 2)
 | otherwise = getFlags currentBits (flag `div` 2)

In your definition of main, you can omit the type annotation from read line and the compiler will deduce you want an Int due to the type signature of bithelp. On its own this is a small change, but leveraging the type system in this way is entirely natural and reduces the number of changes you would have to make if, say, you changed your functions to operate on Integers.

See if this isn't more clear.

main = do putStrLn "Enter a positive integer:"
 nstr <- getLine
 putStrLn "List of flags:"
 print $ bithelp (read nstr)

The last thing to do would be to eliminate the bithelp function by rewriting the getFlags function with a call to findPower inside of it, passed to an inner worker function. I'll leave that as an exercise to the reader.

Answer 2

Always Use a Library When Available!

Perhaps use Data.Bits? It was designed for this kind of stuff!

Now that we have chosen the right library, lets look at the right algorithm.

There are no loops in functional languages. Functional languages use recursion when performing iterative computations. In order to generate list of variable length as output, we will need to use recursion.

Here is how I would define your function recursively:

import Data.Bits
{-- List of set flag values in ascending order --}
bithelp :: (Bits a, Integral a) => a -> [a]
bithelp n = bithelp' 0 n -- for a given n start by checking power 0
 where -- increment the power at each recursive step
 bithelp' e n -- and conditionally decide how to proceed
 | n < power = [] -- if the power is larger than n we are done
 | testBit n e = power : bithelp' (e+1) n -- if the bitflag is set add the power
 | otherwise = bithelp' (e+1) n -- otherwise just check the next power
 where power = shiftL 1 e -- precompute the power
main = do
 putStrLn "Bitfield:"
 line <- getLine
 let bitfield = read line :: Int
 let flags = bithelp bitfield
 putStrLn "List of flags:"
 print flags

Examples:

ghci> bithelp 7
[1,2,4]
ghci> bithelp 51
[1,2,16,32]
ghci> bithelp 8675309
[1,4,8,32,64,128,256,512,1024,2048,4096,16384,262144,8388608]
ghci> bithelp 93825764591328014238947101
[1,4,8,16,256,512,1024,4096,65536,131072,8388608,16777216,33554432,67108864,536870912,2147483648,4294967296,8589934592,17179869184,68719476736,274877906944,549755813888,2199023255552,4398046511104,140737488355328,281474976710656,562949953421312,1125899906842624,9007199254740992,18014398509481984,36028797018963968,72057594037927936,144115188075855872,2305843009213693952,4611686018427387904,9223372036854775808,590295810358705651712,1180591620717411303424,18889465931478580854784,37778931862957161709568,75557863725914323419136,604462909807314587353088,1208925819614629174706176,4835703278458516698824704,9671406556917033397649408,77371252455336267181195264]
ghci> (sum $ bithelp 93825764591328014238947101) == 93825764591328014238947101
True