Library for binary
(Difference between revisions)
|(34 intermediate revisions by 3 users not shown)|
Latest revision as of 08:57, 13 December 2009The 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
, and various conversion functions.
Bits = [Bit]
This code is provided in case somebody finds it useful/interesting/amusing. Feel free to hack it to bits. (Get it? Sorry...)
Perhaps the functions
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
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*]