[ create a new paste ] login | about

Link: http://codepad.org/FPUIwVp0    [ raw code | output | fork ]

programmingpraxis - Scheme, pasted on Oct 8:
; functional-style linked lists

(define (error symb str)
  (display "error: ")
  (display (symbol->string symb))
  (display ": ")
  (display str)
  (newline))

(define nil (vector)) ; '()

(define (nil? xs) (zero? (vector-length xs))) ; null?

(define (pair x xs) (vector x xs)) ; cons

(define (head xs) ; car
  (if (nil? xs)
      (error 'head "exhausted")
      (vector-ref xs 0)))

(define (tail xs) ; cdr
  (if (nil? xs)
      (error 'tail "exhausted")
      (vector-ref xs 1)))

(define xs (pair 0 (pair 1 (pair 2 (pair 3 (pair 4 (pair 5 (pair 6 (pair 7 nil)))))))))
(display (head xs)) (newline)
(display (head (tail (tail (tail xs))))) (newline)

(define (nth xs n) ; list-ref
  (if (nil? xs)
    (error 'nth "exhausted")
    (if (zero? n)
        (head xs)
        (nth (tail xs) (- n 1)))))

(define (len xs) ; length
  (if (nil? xs)
      0
      (+ (len (tail xs)) 1)))

(display (nth xs 5)) (newline)
(display (len xs)) (newline)

(define (app x1 x2) ; append
  (if (nil? x1) x2
    (pair (head x1)
          (app (tail x1) x2))))

(display (nth (app xs (pair 8 (pair 9 nil))) 9)) (newline)
(display (nth (app xs (pair 8 (pair 9 nil))) 10)) (newline)

(define (rev-recursive xs) ; reverse
  (if (nil? xs) nil
    (app (rev-recursive (tail xs))
         (pair (head xs) nil))))

(define (rev-iterative xs) ; reverse
  (let loop ((xs xs) (rs nil))
    (if (nil? xs)
        rs
        (loop (tail xs) (pair (head xs) rs)))))

(display (nth (rev-recursive xs) 4)) (newline)
(display (nth (rev-iterative xs) 4)) (newline)


Output:
1
2
3
4
5
6
7
8
9
0
3
5
8
9
error: nth: exhausted
#<void>
3
3


Create a new paste based on this one


Comments: