Library for binary
Jump to navigation
Jump to 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 = "*" ++ map bit_to_character 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*]