Personal tools

Library for binary

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(domgete)
m (acraceltzelg)
Line 1: Line 1:
 +
1
1
1
1
1

Revision as of 00:55, 24 December 2007

1 1 1 1 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*]
Retrieved from "http://www.haskell.org/haskellwiki/Library_for_binary"

Category: Code