Cover by Donald Bruce Stewart, Bryan O'Sullivan, John Goerzen

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

O'Reilly logo

Finding Matching Digits

Our first problem is to find the digits that might be encoded at a given position. For the next while, we’ll make a couple simplifying assumptions. The first is that we’re working with a single row. The second is that we know exactly where in a row the left edge of a barcode begins.

Run Length Encoding

How can we overcome the problem of not even knowing how thick our bars are? The answer is to run length encode (instead of repeating a value some number of times, run length encoding presents it once, with a count of the number of consecutive repeats):

-- file: ch12/Barcode.hs
type Run = Int
type RunLength a = [(Run, a)]

runLength :: Eq a => [a] -> RunLength a
runLength = map rle . group
    where rle xs = (length xs, head xs)

The group function takes sequences of identical elements in a list and groups them into sublists:

ghci> group [1,1,2,3,3,3,3]
[[1,1],[2],[3,3,3,3]]

Our runLength function represents each group as a pair of its length and first element:

ghci> let bits = [0,0,1,1,0,0,1,1,0,0,0,0,0,0,1,1,1,1,0,0,0,0]
ghci> runLength bits
Loading package array-0.1.0.0 ... linking ... done.
Loading package containers-0.1.0.2 ... linking ... done.
Loading package bytestring-0.9.0.1.1 ... linking ... done.
[(2,0),(2,1),(2,0),(2,1),(6,0),(4,1),(4,0)]

Since the data we’re run length encoding are just ones and zeros, the encoded numbers will simply alternate between one and zero. We can throw the encoded values away without losing any useful information, keeping only the ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required