Library for binary
Jump to navigation
Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
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*]