Subversion Repositories programming

Rev

Rev 100 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
65 irasnyd 1 
;Written By: Ira Snyder
2 
;Due Date:   02-11-2005
3 
;Homework #: hw07
108 ira 4 
;License: Public Domain
65 irasnyd 5 
 
6 
;;; The next two functions define a special insertion sort
7 
;;; that will sort a Polynomial-Normal-Form list
8 
(defun ISORT (L)
9 
  (cond
10 
    ((null L) nil)
11 
    (t        (ISORT1 (car L) (ISORT (cdr L))))
12 
  )
13 
)
14 
 
15 
;;; Helper for ISORT
16 
(defun ISORT1 (N L)
17 
  (cond
18 
    ((null L)       (list N))
19 
    ((>= (cadr N) (cadar L)) (cons N L))
20 
    (t              (cons (car L) (ISORT1 N (cdr L))))
21 
  )
22 
)
23 
 
24 
;;; Combines the coefficients of a two part list, L1,
25 
;;; and a list comprised of two part lists, L2
26 
;;; Example: L1 <- (1 1)
27 
;;;          L2 <- ((2 2) (3 3) (4 4) (1 1))
28 
;;; Returns: (2 1)
29 
;;;
30 
;;; It is good for combining the parts of a PNF expression
31 
(defun COMBINE (L1 L2)
32 
  (cond
33 
    ((null L2)                L1)
34 
    ((= (cadr L1) (cadar L2)) (COMBINE (list (+ (car L1) (caar L2)) (cadr L1))
35 
                                       (cdr L2)))
36 
    (t                        (COMBINE L1 (cdr L2)))
37 
  )
38 
)
39 
 
40 
;;; Deletes any two part list contained within the
41 
;;; list L with the exponent given as an argument
42 
;;; Example: EXP <- 1
43 
;;;          L <- ((1 2) (1 1) (3 1) (1 4))
44 
;;; Returns: ((1 2) (1 4))
45 
(defun DEL-EXP (EXP L)
46 
  (cond
47 
    ((null L)          nil)
48 
    ((= EXP (cadar L)) (DEL-EXP EXP (cdr L))) ;remove an element
49 
    (t                 (cons (car L) (DEL-EXP EXP (cdr L))))
50 
  )
51 
)
52 
 
53 
;;; Combines all like terms in a PNF expression, reducing it
54 
;;; completely. It does NOT sort the resulting list however.
55 
(defun MY-REDUCE (L)
56 
  (cond
57 
    ((null L) nil)
58 
    (t        (cons (COMBINE (car L) (cdr L))
59 
                    (MY-REDUCE (DEL-EXP (cadr (COMBINE (car L) (cdr L))) L))))
60 
  )
61 
)
62 
 
66 irasnyd 63 
(defun DEL-ZERO (L)
64 
  (cond
65 
    ((null L) nil)
66 
    ((= 0 (caar L)) (DEL-ZERO (cdr L)))
67 
    (t              (cons (car L) (DEL-ZERO (cdr L))))
68 
  )
69 
)
70 
 
65 irasnyd 71 
;;; This takes a non-reduced, unsorted list representing a
72 
;;; PNF expression, and reduces and sorts it into correct
73 
;;; Polynomial-Normal-Form.
66 irasnyd 74 
(defun PNF (L) (ISORT (DEL-ZERO (MY-REDUCE L))))
65 irasnyd 75