Library for binary

1 1 1 1 1 1 1 1 1 1 1 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*]

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