显示标签为“Haskell SICP Programming”的博文。显示所有博文
显示标签为“Haskell SICP Programming”的博文。显示所有博文

2008年12月6日星期六

Huffman Tree Decoder

Section 2.3.3 of SICP contains a program that decodes messages from a pre-built Huffman tree.

 

The Scheme code:

 

(define (make-leaf symbol weight)

  (list 'leaf symbol weight))

 

(define (leaf? object)

  (eq? (car object) 'leaf))

 

(define (symbol-leaf x) (cadr x))

(define (weight-leaf x) (caddr x))

(define (make-code-tree left right)

  (list left

        right

        (append (symbols left) (symbols right))

        (+ (weight left) (weight right))))

 

(define (left-branch tree) (car tree))

(define (right-branch tree) (cadr tree)) 

(define (symbols tree)

  (if (leaf? tree)

      (list (symbol-leaf tree))

      (caddr tree)))


(define (weight tree)

  (if (leaf? tree)

      (weight-leaf tree)

      (cadddr tree))) 


(define (decode bits tree)

  (define (decode-1 bits current-branch)

    (if (null? bits)

        '()

        (let ((next-branch

               (choose-branch (car bits) current-branch)))

          (if (leaf? next-branch)

              (cons (symbol-leaf next-branch)

                    (decode-1 (cdr bits) tree))

              (decode-1 (cdr bits) next-branch)))))

  (decode-1 bits tree))

 

(define (choose-branch bit branch)

  (cond ((= bit 0) (left-branch branch))

        ((= bit 1) (right-branch branch))

        (else (error "bad bit -- CHOOSE-BRANCH" bit))))

 

The Haskell code that does the same thing:

 

data Bit = B0 | B1

           deriving (Eq, Ord)

 

instance Show Bit where

    show B0 = "0"

    show B1 = "1"

 

type Symbol = Char

type Weight = Int

 

data Tree = Leaf Symbol Weight

          | Node [Symbol] Weight Tree Tree

 

decode :: Tree -> [Bit] -> [Symbol]

decode tree [] = []

decode tree bits = s : decode tree rest

    where (s, rest) = decode1 tree bits

 

decode1 :: Tree -> [Bit] -> (Symbol, [Bit])

decode1 (Node _ _ (Leaf sym _) _           ) (B0:rest) = (sym, rest)

decode1 (Node _ _ left         _           ) (B0:rest) = decode1 left rest

decode1 (Node _ _ _            (Leaf sym _)) (B1:rest) = (sym, rest)

decode1 (Node _ _ _            right       ) (B1:rest) = decode1 right rest

 

-- Test

 

sample_message :: [Bit]

sample_message = [B0, B1, B1, B0, B0, B1, B0, B1, B0, B1, B1, B1, B0]

 

sample_tree :: Tree

sample_tree = Node ['A', 'B', 'C', 'D'] 8

                   (Leaf 'A' 4)

                   (Node ['B', 'C', 'D'] 4

                         (Leaf 'B' 2)

                         (Node ['C', 'D'] 2

                               (Leaf 'C' 1)

                               (Leaf 'D' 1)))

 

-- decode sample_tree sample_message

-- "ACABBDA"

 

Comments:

I think everybody will agree that the Haskell code is much cleaner and more concise than the corresponding Scheme code. I attribute the cleanness and conciseness to Haskell's algebraic data type and pattern matching structure: where in Scheme one express any data structure in lists in Haskell one defines data structures more naturally in data types; where in Scheme one fetch fields of data structures using ca(d*)r, in Haskell one binds fields of data structures to formal parameters via pattern matching.

 

During the course of learning Haskell, I come to the feeling that Scheme is the assembly language for functional programming comparing with Haskell (or ML and the like) in the sense that assembly languages are low-level comparing to C or even C++ in the imperative languages world.

 

Saying Scheme is a low-level language by no means implies that Scheme is a bad functional language. No. I thought and still believe that Scheme is the one of the most elegant programming language in the world. Just as learning an assembly language will help make one a better C programmer, learning Scheme will get one closer to the underlying computation model (Lambda Calculus) that underpins all functional programming languages, so that one can distinguish the essentials from the non-essentials and don't get lost in the complex constructs offered by a modern language like Haskell (However, I do think typing is something essential but totally missing in Scheme).

 

All I am saying is that Scheme remains as a good (perhaps the best) programming language for educational purpose, but for real-world product development, Haskell (or the ML family) is probably a better candidate.

 

P.S.:

Philip Walder has a paper discussing the merit of statically typed, lazy functional programming languages (KRC/Miranda) over dynamically typed, eager evaluation languages (Scheme/Lisp). An enlightening reading.


 

2008年11月30日星期日

Probabilistic Primitivity Testing

I have been learning Haskell and as an exercise once in a while I will pick up SICP and try to implement some of the programs in Haskell. 

Section 1.2.6 of SICP contains the definition of a function that probabilistically tests if a given natural number n is a prime based on Fermat's Little Theorem. Below is the Scheme code:

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))        

(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1)))))

(define (fast-prime? n times)
  (cond ((= times 0) true)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else false)))

And here is the equivalent Haskell code that I wrote:

> import System.Random
> import System.IO.Unsafe
>
> fast_prime         :: Integer -> Int -> Bool
> fast_prime n times = and $ map fermat_test (mkRandomList n times)
>     where fermat_test a = expmod a n n == a
>           expmod base exp m 
>               | (exp == 0) = 1
>               | (even exp) = (square (expmod base (exp `div` 2) m)) `mod` m
>               | otherwise  = (base * (expmod base (exp -1) m)) `mod` m
>           square a = a * a
>           
> mkRandomList :: Integer -> Int -> [Integer]
> mkRandomList n len = 
>     take len $ 
>         unsafePerformIO $ 
>             do g <- getStdGen
>                return $ randomRs (1, n - 1) g

The major difference between the Haskell code and the Scheme code is the part dealing with the random number generator. Where in Scheme a simple call to random() can do, in Haskell, I have to resort to monad, which makes the Haskell code less cleaner than its Scheme counterpart (which is usually not the case in my experience).  But the part that makes me feel most uncomfortable is the call to unsafePerformIO whose very existence implies something "incorrect" here. 

But I have my reasons: I do not want mkRandomList itself to be a monad because that would force all the functions along the calling chain to be inside a monad which is way too clumsy from the point of view of the callers of that function (fast_prime in this case). After all, conceptually mkRandomList is a pure function whose very responsibility is to return a list of seemingly non-related numbers in a certain range. It is supposed to be used just once so it does not matter that subsequent call to it produce the same list.

Or maybe there are better approaches that did not occur to me?