Wednesday, January 18, 2012

A naive Adler32 example in Clojure and Scala

Houdy,

between administrative intricacies this week, among other things, I took the time to reproduce both in Clojure and Scala a small exercise found in Real World Haskell (RWH). 
This blog entry will be very small as I simply provided in each language a way to implement the algorithm. 

The algorithm is the Adler32 checksum algorithm as presented in RWH. (You will be able to see the link at the end the protest on the Wikipedia site). Trying to decode the three code samples while the Wikipedia link is blacked out for protest, can be also seen as an interesting exercise :). 

The Adler32 algorithm is an algorithm invented by Mark Adler in 1995 and used in the zlib compression library. I see these katas as an interesting mean of learning new things on a daily base (isn't it our job to learn and understand better than use blindly external frameworks?). 
For copyright purpose I provide here my version of the algorithm and not the one in the book, as I tried to produce my own haskell version

import Data.Char (ord)
import Data.Bits (shiftL, (.&.), (.|.)) base = 65521 cumulate::(Int, Int) -> Char -> (Int, Int) cumulate (a, b) x = let a' = (a + (ord x .&. 0xff)) `mod` base b' = (a'+ b) `mod` base in (a', b') adler32::[Char] -> Int adler32 xs = let (a, b) = foldl cumulate (1, 0) xs in (b `shiftL` 16) .|. a

The authors use this algorithm on purpose in order to present an application of the use of the higher order fold function. Let give it a try:

ghci>adler32 "Thumper is a cute rabbit"
1839204552
ghci>

That gives us meat for our tests in Scala and Clojure (I have not learn yet about quickCheck Haskell) Logically, in Clojure our test should look like:

(ns algorithms.test.adler32-spec
  (:use algorithms.adler32)
  (:use clojure.test))

(deftest checksum-with-favourit-sentence-should-produce-result
  (is (= 1839204552 (checksum "Thumper is a cute rabbit"))))

that runs  green for the following implementation:

(ns algorithms.adler32)

(def base 65521)

(defn cumulate [[a b] x]
  (let [a-prim (rem (+ a (bit-and x 255)) base)]
    [a-prim (+ b a-prim)]))

(derive clojure.lang.LazySeq ::collection)

(defmulti checksum class)
(defmethod checksum String [data]
  (checksum  (lazy-seq (.getBytes data))))
(defmethod checksum ::collection [data]
  (let [[a b] (reduce cumulate [1 0] data)]
    (bit-or (bit-shift-left b 16) a)))


where I naively used a derive routine in order to dispatch my multimethod using the class function as a dispatcher. My dispatching mechanism resolves now the clojure.lang.LazySeq instances as children of ::collection :

algorithms.adler32=> (parents clojure.lang.LazySeq)
#{java.util.List clojure.lang.Obj clojure.lang.ISeq clojure.lang.IPending clojure.lang.Sequential :algorithms.adler32/collection}
algorithms.adler32=>

Test ok.

 Following the same reasoning in Scala, the test will be :


package com.promindis.algorithms.cheksum

import org.specs2.Specification


class Adler32Specification extends Specification { def is =
  "Adler32Specification"   ^
                          p^
    "checksum for input"   ^
    "Should restore the expected checksum value" !e1


  def e1 =
    new DefaultAdler32()
      .checksumText("Thumper is a cute rabbit".toCharArray)
      .should(beEqualTo(1839204552))
}

leading to

package com.promindis.algorithms.cheksum

trait Adler32 {
  val base = 65521

  def rebased(value: Int) = value % base

  def cumulated(acc: (Int, Int), item : Byte): (Int, Int) = {
    val a = rebased(acc._1 + (item & 0xff ))
    (a, (a + acc._2) % base)
  }

  def checksum(data: Traversable[Byte]): Int

  def checksumText(data: Traversable[Char]): Int
}


final class DefaultAdler32 extends Adler32 {

  override def checksum(data: Traversable[Byte]): Int = {
    val result = data.foldLeft((1, 0)) {cumulated(_, _)}
    (result._2 << 16) | result._1
  }

  def checksumText(data: Traversable[Char]) = {
    checksum(data.toSeq.map(_.toByte))
  }
}

Tests green :)
 That's all folks (I promised it would not be long). And don't take for granted what comes from closed boxes !

Be seeing you !!! :)

3 comments:

jimi said...

You'll now recover information from pen drive simply. Pen drive brings us unpredictable risk and great convenience. the positioning is always accustomed to save our handy files in an exceedingly pen drive instead of in a very pc.
boot disk for windows 7

Rebecca Lopez said...

The stuff you are writing blows out my mind.
http://c2logix.com

Isolde Alexeyeva said...

Your contents are wonderful and advisory.
price per head software

Post a Comment