; Pairs
;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define pair (cons 1 2))
pair
(car pair)
(cdr pair)

; Linked Lists
;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; How do we end it?
; (cons 1 (cons 2 (cons 3 (cons 4 (cons 5 ...)))))

; the empty list
()
nil

; Scheme Lists
(cons 1 (cons 2 (cons 3 (cons 4 (cons 5 ())))))
; displayed as (1 2 3 4 5)

; List Construction
(define a 2)

(cons 1 (cons a (cons 3 ())))
; (1 2 3)

(list 1 a 3)
; (1 2 3)

'(1 a 3)
; (1 a 3) - a is not evaluated

; Drawing Box-and-Pointer Diagrams on scheme.cs61a.org
(draw '(1 2 3))

; Or automatically draw all lists that are output
; (autodraw)

; Symbolic Programming
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(+ 1 2)
; evaluates to 3

'(+ 1 2)
; evaluates to (+ 1 2)

(eval '(+ 1 2))
; evaluates to 3

(define code '(+ 1 2))

(eval (list '* code 4))
; equivalent to (* (+ 1 2) 4) = 12

; Mutation
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define lst1 '(1 2 3))
(define lst2 lst1)
(set-car! lst1 6)
(set-cdr! (cdr (cdr lst2)) '(4 5))
lst1

; You can even mutate code
(define code '(+ 1 2))

(eval code)
; 3

(set-car! (cdr code) 5)

(eval code)
; 7

; Normal map
(define (map proc lst)
  (if (null? lst)
      nil
      (cons (proc (car lst))
            (map proc (cdr lst)))))

(if #f 4)
; when an if has only two operands and the predicate is false,
; it evaluates to a special value "undefined"
; It's not output interactively; like None in Python

(begin (print 4) (print 3) 7)
; Do multiple things in order. The last one is what the whole expression evaluates to

; Mutative map!
(define (map! proc lst)
  (if (not (null? lst))
      (begin
        (set-car! lst (proc (car lst)))
        (map! proc (cdr lst)))))

(define (square x) (* x x))

(define lst3 '(1 2 3 4 5))

(map square lst3)
; (1 4 9 16 25)

lst3
; still (1 2 3 4 5)

(map! square lst3)
; no output

lst3
; now it's (1 4 9 16 25)

; You can quote a large piece of code and draw it to see what it looks like
(define mutative-map-code
  '(define (map! proc lst)
     (if (not (null? lst))
         (begin
           (set-car! lst (proc (car lst)))
           (map! proc (cdr lst))))))

(draw mutative-map-code)

; filter!
(define (filter! pred lst)
  (cond ((null? lst) nil)
        ((and (null? (cdr lst))
              (pred (car lst)))
          lst)
        ((null? (cdr lst)) nil)
        ((not (pred (car lst)))
          (set-car! lst (car (cdr lst)))
          (set-cdr! lst (filter! pred (cdr (cdr lst))))
          lst)
        (else
          (set-cdr! lst (filter! pred (cdr lst)))
          lst)))