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.
没有评论:
发表评论