# Library for binary

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

The following is a library I often use for any processing that involves binary. (E.g., addresses on binary trees, compression algorithms, etc.) It defines the types `Bit`, `Bits = [Bit]`, and various conversion functions.

This code is provided in case somebody finds it useful/interesting/amusing. Feel free to hack it to bits. (Get it? Sorry...)

```module Bits where

import Data.List (foldl', unfoldr)

data Bit = Zero | One deriving (Eq)

instance Show Bit where
showsPrec _ (Zero) = ("+0+"++)
showsPrec _ (One)  = ("+1+"++)
showList ls st = "*" ++ foldr (\b cs -> bit_to_character b : cs) "" ls ++ "*" ++ st

bit_to_integer :: (Integral i) => Bit -> i
bit_to_integer Zero = 0
bit_to_integer One  = 1

bit_to_boolean = (One ==)

bit_to_character Zero = '0'
bit_to_character One  = '1'

bit_from_integer :: (Integral i) => i -> Bit
bit_from_integer 0 = Zero
bit_from_integer 1 = One
bit_from_integer _ = error "bit_from_integer: Invalid integer."

bit_from_boolean b = if b then One else Zero

bit_from_character '0' = Zero
bit_from_character '1' = One
bit_from_character _   = error "bit_from_character: Invalid character."

type Bits = [Bit]

bits_trim  = dropWhile (Zero ==)
bits_pad n = reverse . take n . (++ repeat Zero) . reverse

bits_to_string   = map bit_to_character
bits_from_string = map bit_from_character

bits_from_integer :: (Integral i) => i -> Bits
bits_from_integer = reverse . unfoldr (\n -> if n == 0 then Nothing else Just (bit_from_integer \$ n `mod` 2, n `div` 2)) . positive

bits_to_integer :: (Integral i) => Bits -> i
bits_to_integer = foldl' (\n b -> 2*n + bit_to_integer b) 0

bits_inc  = reverse . work . reverse where   -- Next binary integer
work [] = [One]
work (Zero : bs) = One  : bs
work (One  : bs) = Zero : (work bs)

bits_next = reverse . work . reverse where   -- Next (balanced) tree address
work [] = [Zero]
work (Zero : bs) = One  : bs
work (One  : bs) = Zero : (work bs)

positive n = if n < 0 then error "Negative argument." else n
```

Perhaps the functions `bits_inc` and `bits_next` require some explanation...

```> take 9 \$ iterate bits_inc []
[**,*1*,*10*,*11*,*100*,*101*,*110*,*111*,*1000*,*1001*]

> take 9 \$ iterate bits_next []
[**,*0*,*1*,*00*,*01*,*10*,*11*,*000*,*001*]
```