CS 61A

This page is under construction!

Lists

Q1: Write a function attach which returns a new list with elem added to the end of a list. Do not use the built-in function append.

scm> (attach 1000 '())
(1000)
scm> (attach 4 '(1 2 3))
(1 2 3 4)
scm> (attach 2 (list 4 3 5))
(4 3 5 2)

(define (attach elem lst)
    "YOUR CODE HERE"
  )

TOGGLE SOLUTION

(define (attach elem lst)
    (if (null? lst) 
        (list elem)
        (cons (car lst) (attach elem (cdr lst)))
      )
  )

What will the following call return?

scm> (attach '(d e) '(a b c))

(a b c (d e))

TOGGLE SOLUTION

Q2: Implement append, which takes two lists and combines them into one.

scm> (append '() '(1 2 3))
(1 2 3)
scm> (append '(a b c) '())
(a b c)
scm> (append '(c s) '(6 1 a))
(c s 6 1 a)

(define (append lst1 lst2)
    "YOUR CODE HERE"
  )

TOGGLE SOLUTION

(define (append lst1 lst2)
    (if (null? lst1) lst2
        (cons (car lst1) (append (cdr lst1) lst2))
      )
  )

Tail Recursion

Q1: Look at the solutions I’ve provided for attach and append. What are the tail calls? Are the functions tail recursive?

attach is not tail recursive. The tail calls are a call to list and a call to cons. The tail call for append is to cons. This is also not tail recursive, since the recursive call is passed as an argument to cons.

TOGGLE SOLUTION

Q2: Implement len-tail, which is a tail recursive procedure that returns the length of the input list.

scm> (len-tail '())
0
scm> (len-tail '(1 2 3))
3

(define (len-tail lst)
    "YOUR CODE HERE"
  )

Hint: Use a helper function to keep track of and increment the length.

TOGGLE SOLUTION   TOGGLE HINT

(define (len-tail lst)
    (define (helper lst result) 
        (if (null? lst) result
            (helper (cdr lst) (+ 1 result)))
      )
    (helper lst 0)
  )

Q3: Without using len-tail, implement compare-len, which takes in two lists and outputs 0 if they’re the same length, 1 if lst1 is longer, or 2 if lst2 is longer.

scm> (compare-len (list 1 2 3) (list 4 5 6)
0
scm>  (compare-len '(3 3 3 3) '(5 5 5))
1
scm>  (compare-len '(h i) '(b y e))
2

(define (compare-len lst1 lst2)
    "YOUR CODE HERE"
)

TOGGLE SOLUTION

(define (compare-len lst1 lst2)
    (cond ((and (null? lst1) (null? lst2)) 0)
          ((null? lst1) 1)
          ((null? lst2) 2)
          (else (compare-len (cdr lst1) (cdr lst2)))
      )
  )

Streams

Write a function powers that returns a stream of all the powers of n.

scm> (powers 3)
(3 . #[promise (not forced)])
scm> (stream-to-list (powers 3) 10)
(3 9 27 81 243 729 2187 6561 19683 59049)
scm> (stream-to-list (powers 2) 10)
(2 4 8 16 32 64 128 256 512 1024)
    
(define (powers n)
    "YOUR CODE HERE"
  )

TOGGLE SOLUTION

(define (powers n)
    (define (helper curr)
        (cons-stream curr (helper (* n curr)))
      )
    (helper n)
  )