tehgeekmeister’s blog

January 11, 2008

one line binary reader in haskell

Filed under: computer science, math, programming — Tags: , , — tehgeekmeister @ 4:22 pm

update: apparently this is now in the first page of google results for “binary reader”, so i feel obligated to point out that i posted an update on this, with better versions thanks to commenters both here and on reddit.

i post this in the tradition of pointlessly showing how concisely one’s favorite language can perform a given task. also, i’m slightly proud of this version, as my previous wasn’t nearly as to the point (and wasn’t point free!). so, here it is:

readBin = (`div` 2) . foldl (\x y -> (x + y) * 2) 0 . map (\c -> case c of {’0′ -> 0; ’1′ -> 1; _ -> error “Input is not a binary string.”})

previous to this, i was using:

readBin xs = core (map bin xs) 0
where
core [x] n = n + x
core (x:xs) n = core xs ((x + n) * 2)
bin c = case c of {’0′ -> 0; ’1′ -> 1; _ -> error ” Input is not a binary string.”}

which, while absolutely equivalent, is overly verbose. now i’ll explain the algorithm for those of you to whom it’s not blindingly obvious (i’m not doing anything tricky or special here, i swear. i’m not that cool.). so, first off, we’re mapping over this string (strings are lists of chars in haskell), and converting each ’0′ or ’1′ to the 0 or 1, respectively. also, if we come across something aside from a ’0′ or ’1′, we raise an error. once the string is converted to a list of ints, we consume the first value of the list, add it to an accumulator, and multiply that by two. why? because by definition any binary integer has the decimal value of the sum of all the digits, going from right to left, to the nth power, where n is the index starting from zero of the right to left position in the binary representation.

so, wait, if we’re summing and raising to the nth power each digit from right to left, then why are we using a left fold (foldl)? because, in this case, adding the digit to the accumulator (x in the lambda passed to foldl) and then multiplying that times two is exactly equivalent to the previous definition i gave of the decimal value of a binary integer. i’ll leave figuring out exactly why that’s the case to the reader. also, in case you didn’t notice, the fold i’m using in the first definition does one more multiplication by two than the other version, which is why, to reap the benefit of a more elegant, pointfree version, we must divide by two at the end.

the point, on the whole, of this? well, as i already said, it’s pointless. but if there were to be one, it’d be this: damn, haskell is cool. i couldn’t have ever done that in other languages i’ve used. (but i’m sure someone else could. i’m just not that cool.)

p.s.: if anyone finds any flaws with any of what i’ve said here, please take the time to comment — while this algorithm has passed a few test runs, and it seems right intuitively, i’m just not experienced enough to be sure it actually is.

About these ads

10 Comments »

  1. The most readable version, unfortunately it works in reverse:

    rBin (’0′:xs) = 0 + 2 * rBin xs
    rBin (’1′:xs) = 1 + 2 * rBin xs
    rBin [] = 0

    readBin1 = rBin . reverse

    If you don’t care for the sort of error reporting, the shortest code I could come up with is:

    readBin2 = foldl (\ x y -> fromJust(elemIndex y “01″) + 2*x ) 0

    This will give you an pattern-match-failure with fromJust with badly formatted string. If you want a nicer error message:

    readBin4 = foldl (\ x y -> fromMaybe (error “Input is not binary”) (elemIndex y “01″) + 2*x ) 0

    Still a pretty oneliner. But not points-free. Let’s make it points-free!

    readBin5 = flip foldl 0 $ flip $ (+) . (*2) . (fromMaybe (error “Input is not binary”)) . (flip elemIndex “01″)

    Just to show that you can truly program brainfuck style in Haskell if you want to.

    If you want to actually deal with the error, rather than crash, you are better off using something like the Maybe datatype:

    readBin :: String -> Maybe Integer
    readBin = foldl (\ x y -> do { c <- x; d <- elemIndex y “01″; return (d + (2*c)) }) (return 0)

    I’ll leave the point-free version of this one as an excersize. You could either use Maybe utitily functions, or the monadic functions to achieve this.

    Comment by Meneer R — January 11, 2008 @ 7:32 pm

  2. On reddit i found even a pretties version!

    readBin = foldM (\a d -> (a*2 +) elemIndex d “01″) 0

    Autheur: PjdePort
    Link: http://programming.reddit.com/info/6597u/comments/c02vlf9

    Comment by Meneer R — January 11, 2008 @ 7:39 pm

  3. Meneer: your first fold version is the one i prefer for readability and my purposes of all your versions (i’m merely converting already parsed binary strings in the course of going thru http://halogen.note.amherst.edu/~jdtang/scheme_in_48/tutorial/overview.html, so there’s really no need for any error reporting at all, i only added it for the purposes of the post.). also, a maybe based version is certainly more elegant than throwing an error, but i didn’t know how to do that in a one-liner, so thanks for showing me a few versions.

    also, i must admit that the version in the reddit comment is beautifully succint. i’m glad i posted this so that i could see some better versions.

    Comment by tehgeekmeister — January 11, 2008 @ 9:09 pm

  4. As you might be able to glean from comment #2, the (`div` 2) in your version is unneeded if you change the fold around a bit:

    readBin = foldl (\x y -> x*2 + y) 0 . map (\c -> case c of {’0′ -> 0; ‘1′ -> 1; _ -> error “Input is not a binary string.”})

    And I would be inclined to put the body of the map into the fold too:

    readBin = foldl (\x y -> x*2 + case y of {’0′ -> 0; ’1′-> 1;_ -> error “Input is not a binary string”}) 0

    You should also use foldl’ from Data.List to cut down on lazyness. (That buys you nothing – readBin always needs to read the whole list). As cool as the one line thing is, I’d really be inclined to do it in a couple more, since I don’t care for either one-line case expressions or lambdas.

    Comment by Mike Laiosa — January 12, 2008 @ 2:01 am

  5. import Data.Char
    readBin = foldl (\a b -> 2*a + digitToInt b) 0

    Comment by Paczesiowa — January 12, 2008 @ 6:17 pm

  6. Mike: that’s true, i figured there was probably a way to get around that. my head isn’t alway so clear when i’m going thru these exercises, and i’ve not done that much programming, it being a hobby and certainly not my job. that being said, i’m glad to know where the problem in my algorithm was! good point about using foldl’, too.

    Paczesiowa: that’s very concise and elegant, but i really don’t like that it would successfully parse non-binary strings. of course, in the case where the string has already been parsed (exactly what i’m doing) that’s not a problem. that aside, i think i like that version the very best of all the versions i’ve seen.

    Comment by tehgeekmeister — January 12, 2008 @ 6:30 pm

  7. [...] — tehgeekmeister @ 10:08 pm apparently submitting that last post to reddit has gotten my previous post to be in the first page of google results for “binary reader“. cool, i’m fine [...]

    Pingback by huh. google knows about me now, go figure. « tehgeekmeister’s blog — January 13, 2008 @ 10:08 pm

  8. Here is an alternative that will convert between any number system:

    stringToDecimal s base = (`div` base) ( foldl (\x y -> (x + y) * base) 0 ( map (\c -> charToDecimal c base) s ) )

    However you must also have a support function, charToDecimal c base, which converts each character in the string to a decimal value.

    Comment by Daniel — August 6, 2010 @ 4:39 pm

    • I’d implemented something like this when I wrote that post, though it was probably after I wrote the post. I love how it’s possible to do things like that so concisely in haskell. =D

      Comment by tehgeekmeister — September 24, 2010 @ 10:03 am

  9. It was difficult to find your site in google. You should create some hi
    PR contextual backlinks in order to rank your site.
    I know – writing articles is very time consuming,
    but contextual backlinks are the best type of backlinks.
    I know one cool tool that will help you to create unique, readable articles in minute, just search
    in google – rewriter creates an unique article in a minute

    Comment by Israel — October 13, 2014 @ 11:57 pm


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Theme: Silver is the New Black. Get a free blog at WordPress.com

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: