Posts Tagged ‘count’

Programming Praxis – Population Count

January 28, 2011

In today’s Programming Praxis, our task is to count the active bits in a number. Let’s get started, shall we?

Some imports:

import Data.Bits
import Data.Word
import qualified Data.IntMap as I

We’ll be implementing three different versions. The first is the trivial naive one: go through all the bits and count how many are active. It works for positive and negative numbers of 32 bits or less.

popCount1 :: Bits a => a -> Int
popCount1 n = length $ filter (testBit n) [0..31]

Next is Wegner’s algorithm, which works best on sparse bit strings. It works on positive and negative numbers of any length.

popCount2 :: Bits a => a -> Int
popCount2 = length . takeWhile (/= 0) . iterate (\n -> n .&. (n - 1))

Finally, there’s the lookup table version, which is faster on large numbers. Unfortunately, it doesn’t handle negative numbers.

popCount3 :: (Integral a, Bits a) => Int -> a -> Int
popCount3 k = sum . map ((ps I.!) . fromIntegral . (.&. (2^k - 1))) .
              takeWhile (/= 0) . iterate (\n -> shiftR n k) where
     ps = I.fromList $ map (\i -> (i, popCount2 i)) [0..2^k - 1]

Some unit tests to see if everything is working properly:

main :: IO ()
main = do print $ popCount1 (23 :: Int) == 4
          print $ popCount1 (-4 :: Int) == 30
          print $ popCount1 (5 :: Word8) == 2

          print $ popCount2 (23 :: Int) == 4
          print $ popCount2 (-4 :: Int) == 30
          print $ popCount2 (5 :: Word8) == 2
          print $ popCount2 (2^200000 - 1 :: Integer) == 200000

          print $ popCount3 1 (23 :: Int) == 4
          print $ popCount3 8 (5 :: Word8) == 2
          print $ popCount3 16 (2^200000 - 1 :: Integer) == 200000

Yep. Though unless you’re going to be working with very large numbers I’d recommend using the second version.

Programming Praxis – Word Count

December 8, 2009

In today’s Programming Praxis exercise, we have to implement the Unix wc command line utility. Let’s get started.

First, we need some imports.

import System.Environment
import Text.Printf

We handle the command line arguments with a bit of pattern matching.

parseOpts :: [String] -> ([Bool], [String])
parseOpts (('-':ps):args) = (map (`elem` ps) "lwc", args)
parseOpts args            = (replicate 3 True, args)

Next, we need to do the actual counting:

count :: [Bool] -> [(String, String)] -> [String]
count opts = map (\(name, text) -> concat
    [printf "%8s" $ if opt then show . length $ f text else "-"
    | (f, opt) <- zip [lines, words, map return] opts] ++ " " ++ name)

And finally, the program itself.

main :: IO ()
main = do args <- getArgs
          let (opts, files) = parseOpts args
          mapM_ putStrLn . count opts =<< if null files
              then fmap (\x -> [("", x)]) getContents
              else fmap (zip files) $ mapM readFile files