Diagnostic 7: Week 7 review | CS 61A Summer 2015

Diagnostics are meant for you to check your understanding of the week's material. They are not worth any points and are not counted towards midterm recovery points; instead, diagnostics are solely for your benefit. If you find yourself struggling with the questions in this diagnostic, consider signing up for Tutoring.

Tail calls

Question 1: Concatenate

Write a tail-recursive function concatenate, which takes in s, a list of lists, and concatenates all the elements together into one list.

; Expected behavior:
;
; scm> (concatenate (list (list 1 2) (list 5 1)))
; (1 2 5 1)
; scm> (concatenate (list (list (1 2)) (list)))
; (1 2)

(define (concatenate s)
'YOUR-CODE-HERE
    (define (helper concatenated rest)
        (if (null? rest)
            concatenated
            (helper (append concatenated (car rest)) (cdr rest))))
    (helper () s)
)

Question 2: Swap

Write a tail-recursive function swap, which takes in a Scheme list s and returns a new Scheme list where every two elements in s are swapped.

; Expected behavior:
;
; scm> (swap (list 1 2 3 4))
; (2 1 4 3)
; scm> (swap (list 1 2 3 4 5))
; (2 1 4 3 5)

(define (swap s)
  'YOUR-CODE-HERE
  (define (helper sofar rest)
    (cond ((null? rest) sofar)
          ((null? (cdr rest)) (append sofar (list (car rest))))
          (else (helper (append sofar (list (car (cdr rest)) (car rest)))
                        (cdr (cdr rest))))))
  (helper () s)
)

Question 3: Insert

Write a tail-recursive function that inserts number n into a sorted list of numbers, s. s is of at least length 1. Hint: Use the built-in Scheme function append.

(define (insert n s)
  'YOUR-CODE-HERE
  (define (insert-help s so-far)
      (cond ((null? s) (append so-far (cons n s)))
               ((< n (car s)) (append so-far (cons n s)))
               (else (insert-help (cdr s) (append so-far (list (car s)))))))
  (insert-help s nil)
)

Note: This was an extra question in Lab 13.

Streams

Question 4: Cycle

Define a function cycle which takes in as input an ordinary Scheme list and returns a stream which just repeats that list over and over. For example, cycle('(a b c) )) is the stream containing elements (a b c a b c ...). If the input list is empty, output the empty stream; otherwise, the output stream should be infinite.

(define (cycle lst)
  'YOUR-CODE-HERE
  (if (null? lst)
      nil 
      (cons-stream (car lst)
         (cycle (append (cdr lst) (list (car lst))))))
)

Note: This was an extra question in Lab 13.

Question 5: Partial sums

Define a function partial_sums, which takes in a stream with elements

a1, a2, a3, ...

and outputs the stream

a1, a1 + a2, a1 + a2 + a3, ...

If the input is a finite stream of length n, the output should be a finite stream of length n. If the input is an infinite stream, the output should also be an infinite stream.

(define (partial-sums stream)
  'YOUR-CODE-HERE
  (helper 0 stream))

(define (helper sum-so-far stream-remaining)
  (if (stream-null? stream-remaining)
      the-empty-stream
      (begin (define new-sum (+ sum-so-far (stream-car stream-remaining)))
	     (cons-stream new-sum (helper new-sum (stream-cdr stream-remaining))))))
; Doctests for partial-sums
(define twos (cons-stream 2 twos))
(define p (partial-sums twos))
(assert-equal 1 "partial-sums" (ss p) '(2 4 6 8 10 12 14 16 18 20 ...))

(define ones (cons-stream 1 ones))
(define q (partial-sums (interleave ones twos)))
(assert-equal 2 "partial-sums" (ss q) '(1 3 4 6 7 9 10 12 13 15 ...))

Consider (define p (partial-sums (cycle '(1)))). What do you think the stream p looks like?

(partial-sums (cycle '(1))) contains the elements 1, 2, 3, 4, ....

SQL

You can use this online SQLite interpreter to check your answers.

A block of 10 store locations, numbered 1 through 10, already has some cafes. Cafes can serve espresso, bagels, coffee, muffins, and eggs (but nothing else).

-- Locations of each cafe
create table cafes as
  select "nefeli" as name, 2 as location union
  select "brewed"        , 8             union
  select "hummingbird"   , 6;

-- Menu items at each cafe
create table menus as
  select "nefeli" as cafe, "espresso" as item union
  select "nefeli"        , "bagels"           union
  select "brewed"        , "coffee"           union
  select "brewed"        , "bagels"           union
  select "brewed"        , "muffins"          union
  select "hummingbird"   , "muffins"          union
  select "hummingbird"   , "eggs";

-- All locations on the block
create table locations as
  with locations(n) as (
    select 1 union
    select n+1 from locations where n < 10
  )
  select * from locations;

Question 6: Open

You would like to open a new cafe. Create a table open_locations that has a single column n where each row is a location that is not already occupied by an existing cafe.

-- Locations without a cafe
create table open_locations as
  -- REPLACE THIS LINE
  select n from locations, cafes group by n having min(abs(n-location)) > 0;
-- select * from open_locations where n >= 5;
-- Expected output:
--   5
--   7
--   9
--   10

Hint: Join locations and cafes in the from clause, so that you can compare a location n with the location of an existing cafe.

Hint: A location is open if its minimum distance from an existing cafe is more than 0. The built-in abs and min functions can be used to express this condition in a having clause.

Question 7: Allowed

To limit competition, the block mandates that no cafe can have a menu item that is sold by another cafe within 2 locations. So, if location 2 already sells bagels, then a cafe located at 1, 3, or 4 cannot sell bagels. You may assume that every item is sold by at least one cafe.

Create a table allowed that has two columns, a location n and a menu item. The rows should contain every item that can be sold at every location, based on these constraints. It should include occupied locations that could expand their current menus.

-- Items that could be placed on a menu at an open location
create table allowed as
  with item_locations(item, location) as (
    select item, location from cafes, menus where name = cafe
  )
  -- REPLACE THIS LINE
  select n, item from locations, item_locations
      group by n, item having min(abs(n-location)) > 2;
-- select * from allowed where n >= 5;
-- Expected output:
--   5|bagels
--   5|coffee
--   5|espresso
--   6|espresso
--   7|espresso
--   8|espresso
--   9|eggs
--   9|espresso
--   10|eggs
--   10|espresso

Hint: Join locations and item_locations, so that you can compare how far a location n is from the location at which an item is already sold.

Hint: Group by a combination of the location n and the item that might be sold at n; use a having clause to filter the groups.

Hint: You do not need to use open_locations from the previous question.

Logic Programming

You can download a copy of the Logic interpreter to double check your answers.

Question 8: Swap

Write facts for a relation swap that swaps every pair of elements in a list:

; Expected behavior:
;
; logic> (query (swap (1 2 3 4 5 6) ?x))
; Success!
; x: (2 1 4 3 6 5)
; logic> (query (swap (1 2 3 4 5 6 7) ?x))
; Success!
; x: (2 1 4 3 6 5 7)

(fact (swap () ()))
(fact (swap (?x) (?x)))
(fact (swap (?x ?y . ?z) (?y ?x . ?e)) (swap ?z ?e))

Question 9: Nested

Write facts for a relation nest that constructs a nested pair representation of a flat list:

; Expected behavior:
;
; logic> (query (nest (1 2 3 4 5) ?nested))
; Success!
; nested: (1 (2 (3 (4 (5 ())))))

(fact (nest () ()))
(fact (nest (?a . ?rest) (?a ?nested)) (nest ?rest ?nested))

Question 10: Interleave

Write facts for interleave, which relates two smaller lists to a larger list. The interleave relation is true if the larger list is the result of interleaving elements from the two smaller lists (with all of the elements of the first small list appearing at even indices, and all of the elements of the second small list appearing at odd indices). See the tests for examples.

'YOUR-CODE-HERE
(fact (interleave () () ()))
(fact (interleave (?x . ?s) (?y . ?t) (?x ?y . ?r))
      (interleave ?s ?t ?r))
;;; interleave tests
(query (interleave ?evens ?odds (a b c d e f)))
; expect Success! ; evens: (a c e)	odds: (b d f)
(query (interleave (a b c) (d e f) ?what))
; expect Success! ; what: (a d b e c f)