; 4a
(define x 1)
(define y 2)
(define z 7)
(let ((z (+ x y z)))
  (let* ((x (+ y z))
         (y (+ x z)))
    (list x y z)))

; 4b
(define x 1)
(define y 2)
(define (f n) (+ x y n))
(set! y 3)
(define a (f y))
(define c x)
(define x 4)
(define b (let ((a 5)) (f a)))
(list a b c x y)

; 4c
(define a 4)
(define b 5)
(define c 6)
(define L1 '(a b))
(define L2 (cons a b))
(define L3 (list a b))
(list (+ a b c)
      (eq? (length L1) (length L3))
      (equal? (car L1) (car L2))
      (eqv? (cdr L2) (cdr L3))
      (equal? (cdr L2) (cadr L3)))



; 5
(define (is-sorted lst)
  (cond ((null? lst) #t)
        ((null? (cdr lst)) #t)
        (else (and (<= (car lst) (cadr lst)) (is-sorted (cdr lst))))))

(define (is-sorted2 lst)
  (cond ((null? lst) #t)
        ((null? (cdr lst)) #t)
        ((and (<= (car lst) (cadr lst)) (is-sorted2 (cdr lst))) #t)
        (else #f)))

(define (is-sorted3 lst)
  (if (or (null? lst) (null? (cdr lst))) #t
      (if (> (car lst) (cadr lst)) #f
          (is-sorted3 (cdr lst)))))

(is-sorted '(1 4 4 5 7 8 12))
(is-sorted '(1 3 2 6 7 4 5))
(and (is-sorted '()) (is-sorted '(42)))



; 6
(define (merge lst1 lst2)
  (cond ((null? lst1) lst2)
        ((null? lst2) lst1)
        ((< (car lst1) (car lst2)) (cons (car lst1) (merge (cdr lst1) lst2)))
        (else (cons (car lst2) (merge (cdr lst2) lst1)))))

(define (merge2 lst1 lst2)
  (cond ((null? lst1) lst2)
        ((null? lst2) lst1)
        (else (let* ((first1 (car lst1))
                     (first2 (car lst2))
                     (less (< first1 first2))
                     (chosen-element (if less first1 first2))
                     (new-lst1 (if less (cdr lst1) lst1))
                     (new-lst2 (if less lst2 (cdr lst2))))
                (cons chosen-element (merge new-lst1 new-lst2))))))

(define (merge lst1 lst2)
  (cond ((and (null? lst1) (null? lst2)) null)   ; or '()
        ((null? lst1) (cons (car lst2) (merge lst1 (cdr lst2))))
        ((null? lst2) (cons (car lst1) (merge lst2 (cdr lst1))))
        ((< (car lst1) (car lst2))
              (cons (car lst1) (merge (cdr lst1) lst2)))
        (else (cons (car lst2) (merge (cdr lst2) lst1)))))

(display "merge:\n")
(merge '(1 4 9 15 32 32) '(0 6 7 20))
(merge '(15 29 47) '(15 17 20 22 99))
(merge '(42) '(5 19 27 42 60))
(merge '(4 9 11) '())
(merge '() '())



; 7
; focuses on level first, then on element type
(define (level-sum lst level)
  (cond ((null? lst) 0)
        ((< level 0) 0)
        (else
         (let* ((first (car lst))
                (rest  (cdr lst))
                (first-sum            ; contribution to sum by first element
                 (if (= 0 level)
                     ; level 0: only numbers matter
                     (if (number? first) first 0)
                     
                     ; level > 0: only lists matter
                     (if (list? first) (level-sum first (- level 1)) 0))))
           ; in
           (+ first-sum (level-sum rest level))))))

(display "level-sum:\n")
(define L '(5 3 (6 4 1) 7 (2 (9 3) 5 (0 (0 (0 (42))))) 8))
(level-sum L 0)      ; 23
(level-sum L 1)      ; 18
(level-sum L 2)      ; 12
(level-sum L 3)      ; 0
(level-sum L 4)      ; 0
(level-sum L 5)      ; 42
(level-sum L 6)      ; 0
(level-sum L 7)      ; 0
(level-sum L 1000)   ; 0
(level-sum L -1)     ; 0
(level-sum L -2)     ; 0



; 8
; returns the first k elements of the given stream as a list
(define (stream-slice stream k)
  (if (<= k 0) '()
      (let ((thepair (stream)))
        (cons (car thepair)
              (stream-slice (cdr thepair) (- k 1))))))

(define (triangular)
  (define (helper n ith)
    (cons ith (lambda () (helper (+ n 1) (+ ith n)))))
  (helper 2 1))

(define (triangular)
  (define (helper x n)
    (cons x (lambda () (helper (+ x n 1) (+ n 1)))))
  (helper 1 1))

(define (triangular)
  (define (helper i sum)
    (cons (+ i sum) (lambda () (helper (+ i 1) (+ sum i)))))
  (helper 1 0))

(define (triangular)
  (define (helper n g)
    (cons g (lambda () (helper (+ n 1) (+ g n)))))
  (cons 1 (lambda () (helper 3 3))))

; works
(define (triangular)
  (define (helper i x)
    (cons x (lambda () (helper (+ i 1) (+ x (+ i 1))))))
  (helper 1 1))

; works
(define (triangular)
  (define (helper triang n)
    (cons triang (lambda () (helper (+ triang (+ n 1)) (+ n 1)))))
  (helper 1 1))

(display "stream triangular: ")
(stream-slice triangular 12)