Seq.unfold and creating bit masks

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.