In the course of working on ParsecClone I needed some code that could take in an arbitrary byte array and convert it to a corresponding bit array. The idea is if I have an array of

[|byte 0xFF;byte 0x01|]

Then I should get

[|1;1;1;1;1;1;1;0;0;0;0;0;0;0;1|]

I’ve done plenty of bit slingin’ in my day, and the trick is just to apply a sequence of bit masks to each byte and collect all the bit arrays. In other languages this is always a little bit of a pain, but in F# the solution was amazingly elegant

## Data

As with anything F#, I like to start with the data

type Bit = | One | Zero override this.ToString() = match this with | One -> "1" | Zero -> "0"

## Make bit masks

Now lets generate the meat and potatoes of this: a sequence of bit masks

let bitMasks = Seq.unfold (fun bitIndex -> Some((byte(pown 2 bitIndex), bitIndex), bitIndex + 1)) 0 |> Seq.take 8 |> Seq.toList |> List.rev

While a `fold`

takes a list and a seed and returns a single accumulated item, an `unfold`

takes a seed and generates a list. For those not familiar, `unfold`

takes a function of the signature

(State -> ('a * State) option) -> State -> Seq<'a>

Unfold takes a function with an argument that is the state, and returns an `item * state`

option tuple. The first element of the option is the element to be emitted in the sequence. The second item is the *next* state. If you return `None`

instead of `Some`

the infinite sequence will end. You can see that my state is the exponent n of *2^n* which gives you the bit mask. The first iteration is 2^0, then 2^1, then 2^2, etc. By reversing it, I now have a bitmask that look like this:

[2^7; 2^6; 2^5; 2^4; 2^3; 2^2; 2^1; 2^0]

## Byte to Bits

The next thing is to apply the bitmask to a byte.

let byteToBitArray b = List.map (fun (bitMask, bitPosition) -> if (b &&& bitMask) >>> bitPosition = byte(0) then Zero else One) bitMasks

The unusual thing here is that bitwise and is the `&&&`

operator and bitwise shift is the >>> operator. Not that weird, but different from other langauges.

## Bytes to Bits

All that’s left is applying the byteToBitArray function to byte array to get a bit array

let bytesToBits (bytes:byte[]) = bytes |> Array.toList |> List.map byteToBitArray |> List.collect id |> List.toArray

And now to test it in fsi

> bytesToBits [|byte 0xFF;byte 0x01|];; val it : Bit [] = [|One; One; One; One; One; One; One; One; Zero; Zero; Zero; Zero; Zero; Zero; Zero; One|]

## Bits To UInt

We can even take a bit array and create a uint now too

let bitsToUInt (bits:Bit[]) = let positions = Array.zip bits (Array.rev [|0..Array.length bits - 1|]) Array.fold (fun acc (bit, index) -> match bit with | Zero -> acc | One -> acc + (pown 2 index)) 0 positions

First I zip the bit array with each position in the bit array. Then we just need to fold over the array and add the accumulator to *2^n* if the bit is a one.

> [|One; One; One; One; One; One; One; Zero;|] |> bitsToUInt;; val it : int = 254

## Conclusion

I really enjoyed working with the higher order functions that F# provides to make a simple and robust conversion. Working with strongly typed data felt more robust than dealing with just integers.