This page is under construction!
These problems are designed to be around exam difficulty. For more basic problems, see the topic-based guides and practice problems!
Scheme Lists
Write a function non-contiguous that checks whether subseq is a non-contiguous subsequence of lst. A sequence is a non-contiguous subsequence if its elements appear in the list in order but not necessarily immediately next to each other.
scm> (non-contiguous '() lst)
True
scm> (non-contiguous '(1 3 6) '(1 2 3 4 5 6))
True
scm> (non-contiguous '(1 5 2) '(1 2 3 4 5 6))
False
(define (non-contiguous subseq lst)
"YOUR CODE HERE"
)(define (non-contiguous subseq lst)
(cond ((null? subseq) #t)
((null? lst) #f)
((= (car subseq) (car lst)) (non-contiguous (cdr subseq) (cdr lst)))
(else (non-contiguous subseq (cdr lst))))
)Tail Recursion
Write keep-first-n which takes a list and a number n and returns a list that consists of the first n numbers of n, assuming lst is at least length n.
scm> (keep-first-n (list 1 2 3 4 5) 3)
(1 2 3)
scm> (keep-first-n (list 'a 'b 'c) 1)
(a)
(define (keep-first-n lst n)
"YOUR CODE HERE"
)TOGGLE SOLUTION OPEN EXPLANATION
(define (keep-first-n lst n)
(define (helper i result lst)
(if (= i n) result
(helper (+ i 1) (append result (list (car lst))) (cdr lst)))
)
(helper 0 '() lst))
)Streams
Write a function that creates a cyclic stream out of the first n elements of lst, or the entire lst if the length of lst is less than n.
scm> (cycle-first-n 3 (list 1 2 3 4))
(1 . #[promise (not forced)])
scm> (stream-to-list (cycle-first-n 3 (list 1 2 3 4)) 10) ; prints stream as list
(1 2 3 1 2 3 1 2 3 1)
scm> (stream-to-list (cycle-first-n 7 (list 1 2 3 4)) 10)
(1 2 3 4 1 2 3 4 1 2)
(define (cycle-first-n n lst)
"YOUR CODE HERE"
)(define (cycle-first-n n lst)
(define (stream-helper i curr-lst)
(if (or (zero? i) (null? curr-lst))
(cycle-first-n n lst)
(cons-stream (car curr-lst) (stream-helper (- i 1) (cdr curr-lst)))
))
(stream-helper n lst))
)SQL
Check back later!
Logic
Write a fact that states that one list is a suffix of another list.
(query (suffix (a b c) (a b c)))
; expect Success!
(query (suffix (4 5) (1 2 3 4 5)))
; expect Success!
(query (suffix (1 2) (1 2 3 4 5)))
; expect Failed.TOGGLE SOLUTION TOGGLE EXPLANATION
(fact (suffix ?suf ?suf))
(fact (suffix ?suf (?first . ?rest))
(suffix ?suf ?rest))
Explanation: Our base case takes care of the case where the two lists are the same. Our recursive case then states that for the first list to be a suffix of the second, it must be a suffix of the rest of the list. When ?rest is assigned to a list that is the same as ?suf, the fact becomes a Success!.