Last active
August 29, 2015 14:01
-
-
Save ConnorAtherton/96c2cdcb9d128b56167e to your computer and use it in GitHub Desktop.
Example answers to past paper questions on key lists
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
;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 '() '())) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
2009 different solution - see fork.