# 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.