# 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

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

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 =
if (b &&& bitMask) >>> bitPosition = byte(0) then Zero
```

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.