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 (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.

## 没有评论:

发表评论