# Diagnostic 7: Week 7 review

## 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: Youdo notneed 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)
```