Example answers to past paper questions on key lists

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
(define (m-tr l1 l2)
  (define (rdc l) (reverse(cdr(reverse l))))
  (define (m-tr-i l1 l2 nl)
    (cond ((null? l1) (append l2 nl))
          ((null? l2) (append l1 nl))
          (else (m-tr-i (rdc l1) (rdc l2) (cons(car(reverse l1)) (cons(car(reverse l2)) nl))))))
  (m-tr-i l1 l2 '()))

;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 '() '()))

Q2 b: this doesn't work in cases where one list is longer than the other - see fork

2009 different solution - see fork.