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

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 <- g

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.

StackExchange Code Review Q#46228, answer score: 3