past_papers_scheme.scm

;Any arbitrary list s can be transformed into a key-list by transforming each item in s 
;into a key-element (choosing appropriate keys in the process).
;Write a function (make-key-list s) that returns a key-list based on its list argument s. 
;2009 Paper
(define (m-k-l s) 
  (define (m-k-l-tr s id) 
     (if (null? s) '()
     (cons(cons id (list (car s)))(m-k-l-tr (cdr s) (add1 id)))))
  (m-k-l-tr s 1))

;Write a function (get-key-list s k) that returns the key-element with key k from key-list s.
;2009 Paper
(define (g-k-l s k)
  (if (= k (car(car s))) (car s)
      (g-k-l (cdr s) k)))

(g-k-l '((1 a) (2 b) (3 (c (d))) (9 (e f))) 9)

;Write a function (insert-key-list s e) that returns a key-list that is like the given key-list s
;but with key-element e inserted in an appropriate place.
;2009 Paper
(define (i-k-l s e)
  (if (<= (car e) (car(car s))) (cons e s)
      (cons (car s) (i-k-l (cdr s) e))))

;Is right.
;2011 Paper Q2 b
(define (m l1 l2)
  (cond ((null? l1) l2)
        ((null? l2) l1)
        (else (cons (car l1) 
                    (cons (car l2) 
                          (m (cdr l1) (cdr l2)))))))
;Mildly better solution.
;2011 Paper Q2 b - Merge List - Tail recursive
(define (merge-list-tail l1 l2)
  (define (rdc l) (reverse (cdr (reverse l))))
                                     ; Accumulator argument - nl
  (define (merge-list-tail-aux l1 l2 nl) 
    (cond ((null? l1) (reverse (append (reverse l2) ; Everything is reversed so flip it back...
                                       nl))) ; Append any remaining elements from l2
          ((null? l2) (reverse (append (reverse l1) ; Everything is reversed so flip it back...
                                       nl))) ; Append any remaining elements from l1
          (else (merge-list-tail-aux (cdr l1)
                                     (cdr l2)
                                     (cons (car l2)
                                           (cons (car l1) nl))))))
  (trace merge-list-tail-aux)
  (merge-list-tail-aux l1 l2 '()))
(trace merge-list-tail)
(merge-list-tail '(a b c k) '(d e f d j l m))

;Rotten solution. Don't wanna talk about it, I feel ... dirty.
;2011 Paper Q2 c
(define (u-m l)
  (define (u-m-i l cnt l1 l2)
    (cond ((null? l) (list (reverse l1) (reverse l2)))
          ((odd? cnt) (u-m-i (cdr l) (add1 cnt) (cons (car l) l1) l2))
          (else (u-m-i (cdr l) (add1 cnt) l1 (cons (car l) l2)))))
  (u-m-i l 1 '() '()))