;;; C311
;;; Homework 1
;;; Basic Scheme

;; member-twice? returns #t if a particular atom appears more than once
;; in a list of atoms.

; with helper procedure
(define member-twice?
(lambda (a ls)
    (cond
      [(null? ls) #f]
      [(eq? a (car ls)) (member? a (cdr ls))]
      [else (member-twice? a (cdr ls))])))

(define member?
(lambda (a ls)
    (cond
      [(null? ls) #f]
      [(eq? a (car ls)) #t]
      [else (member? a (cdr ls))])))

; same function, with encapsulation
(define member-twice?
(letrec
    ([member?
       (lambda (a ls)
     (cond
       [(null? ls) #f]
       [(eq? a (car ls)) #t]
       [else (member? a (cdr ls))]))])
    (lambda (a ls)
      (cond
    [(null? ls) #f]
    [(eq? a (car ls)) (member? a (cdr ls))]
    [else (member-twice? a (cdr ls))]))))

;; list index takes an atom "a" and a list "ls" and returns the
;; zero-based index of a in ls. If the atom does not occur in ls,
;; it returns -1.

; with a weird helper function
(define list-index
(lambda (a ls)
    (cond
      [(null? ls) -1]
      [(eq? (car ls) a) 0]
      [else (maybe-add1 (list-index a (cdr ls)))])))

(define maybe-add1
(lambda (n)
    (if (= n -1)
    -1
    (add1 n))))

; same approach, with encapsulation
(define list-index
(let ([maybe-add1
      (lambda (n)
        (if (= n -1)
        -1
        (add1 n)))])
    (lambda (a ls)
      (cond
    [(null? ls) -1]
    [(eq? (car ls) a) 0]
    [else (maybe-add1 (list-index a (cdr ls)))]))))

; same approach, but without helper function:
(define list-index
(lambda (a ls)
    (cond
      [(null? ls) -1]
      [(eq? (car ls) a) 0]
      [else
    (let ([answ (list-index a (cdr ls))])
      (if (= answ -1)
          -1
          (add1 answ)))])))

; iterative approach
(define list-index
(lambda (a ls)
    (letrec ([list-index-hlp
           (lambda (ls n)
         (cond
           [(null? ls) -1]
           [(eq? (car ls) a) n]
           [else (list-index-hlp
               (cdr ls)
               (add1 n))]))])
      (list-index-hlp ls 0))))

;; duplicate takes a number n and an atom a and returns a list
;; cointaining n occurrences of a.

; straighforward approach
(define duplicate
(lambda (n a)
    (if (zero? n)
    '()
    (cons a (duplicate (sub1 n) a)))))

; iterative
(define duplicate
(lambda (n a)
    (letrec ([dup-hlp
           (lambda (n ans)
         (if (zero? n)
             ans
             (dup-hlp (sub1 n) (cons a ans))))])
      (dup-hlp n '()))))

;; assq takes an atom and an association list and returns the
;; first list in als whoe car is in a
(define assq
(lambda (a als)
    (cond
      [(null? als) #f]
      [(eq? (caar als) a) (car als)]
      [else (assq a (cdr als))])))

;; list-ref takes a number and a list and returns the n-th element
;; of the list
(define list-ref
(lambda (n ls)
    (if (zero? n)
    (car ls)
    (list-ref (sub1 n) (cdr ls)))))

;; snoc takes a list ls and a datum i and returns a new list where
;; i has been added to the end of the list

; a valid solution
(define snoc
(lambda (ls i)
    (if (null? ls)
    (list i)
    (cons (car ls) (snoc (cdr ls) i)))))

; a not so valid solution
(define snoc
(lambda (ls i)
    (append ls (list i))))

; another kind of invalid solution
(define snoc
(lambda (ls i)
    (reverse (cons i (reverse ls)))))

;; intersection takes two sets and returns the intersection of
;; them

; simple solution
(define intersection
(lambda (s0 s1)
    (cond
      [(null? s0) '()]
      [(memq (car s0) s1) (cons (car s0)
                 (intersection (cdr s0) s1))]
      [else (intersection (cdr s0) s1)])))

; iterative solution
(define intersection
(lambda (s0 s1)
    (letrec ([inter-hlp
           (lambda (s0 answ)
         (cond
           [(null? s0) answ]
           [(memq (car s0) s1)
            (inter-hlp (cdr s0) (cons (car s0) answ))]
           [else (inter-hlp (cdr s0) answ)]))])
      (inter-hlp s0 '()))))

;; count-parens takes a deep list and returns the number of parentheses
;; in the printed representation of the list.
(define count-parens
(lambda (ls)
    (cond
      [(null? ls) 2]
      [(pair? ls) (+ (count-parens (car ls)) (count-parens (cdr ls)))]
      [else 0])))

; another solution
(define count-parens
(lambda (ls)
    (cond
      [(null? ls) 2]
      [(list? (car ls)) (+ (count-parens (car ls)) (count-parens (cdr ls)))]
      [else (count-parens (cdr ls))])))

;; sum-of-squares takes a list of numbers and returns the sum of
;; the squares of the numbers
(define sum-of-squares
(lambda (tup)
    (if (null? tup)
    0
    (+ (^2 (car tup)) (sum-of-squares (cdr tup))))))

; iterative version
(define sum-of-squares
(letrec ([sum-hlp
         (lambda (tup sum)
           (if (null? tup)
           sum
           (sum-hlp (cdr tup)
             (+ sum (^2 (car tup))))))])
    (lambda (tup)
      (sum-hlp tup 0))))

; helper procedure
(define ^2
(lambda (n)
    (* n n)))

;; union takes two lists of symbols without duplicates and returns
;; the list with all the symbols in the lists, without duplicates.
(define union
(lambda (s0 s1)
    (cond
      [(null? s0) s1]
      [(memq (car s0) s1) (union (cdr s0) s1)]
      [else (cons (car s0) (union (cdr s0) s1))])))

; iterative solution
(define union
(lambda (s0 s1)
    (letrec ([union-hlp
           (lambda (s0 answ)
         (cond
           [(null? s0) answ]
           [(memq (car s0) s1)
            (union-hlp (cdr s0) answ)]
           [else
             (union-hlp (cdr s0) (cons (car s0) answ))]))])
      (union-hlp s0 s1))))

;; set? takes a list of symbols and returns #t if the list does not
;; contains duplicates
(define set?
(lambda (ls)
    (cond
      [(null? ls) #t]
      [(memq (car ls) (cdr ls)) #f]
      [else (set? (cdr ls))])))

;; depth takes a list ls and returns the depth of ls.
(define depth
(lambda (ls)
    (cond
      [(null? ls) 1]
      [(pair? ls) (max (add1 (depth (car ls)))
            (depth (cdr ls)))]
      [else 0])))

; other solution
(define depth
(lambda (ls)
    (cond
      [(null? ls) 1]
      [(list? (car ls)) (max (add1 (depth (car ls)))
              (depth (cdr ls)))]
      [else (depth (cdr ls))])))

;; div performs integer division doing only sums.
;;
(define div
(lambda (n m)
    (if ( n m)
    0
    (add1 (div (- n m) m)))))

; iterative solution
(define div
(lambda (n m)
    (letrec ([div-hlp
           (lambda (n quotient)
         (if ( n m)
             quotient
             (div-hlp (- n m) (add1 quotient))))])
      (div-hlp n 0))))

;; prefixes takes a list and returns the prefixes of the list
;;
(define prefixes
(letrec ([prefix-hlp
         (lambda (ls current-prefix answ)
           (if (null? ls)
           answ
           (let ([new-prefix (snoc current-prefix (car ls))])
             (prefix-hlp
               (cdr ls)
               new-prefix
               (cons new-prefix answ)))))])
    (lambda (ls)
      (prefix-hlp ls '() '(())))))

;; vector-index takes an atom and a vector and returns the zero-based
;; index of the first occurrence of the atom in the vector.
;; returns -1 if the atom is not in there.
(define vector-index
(lambda (a v)
    (let ([vlen (vector-length v)])
      (letrec ([vindex-hlp
         (lambda (n)
           (cond
             [(= vlen n)    -1]
             [(eq? (vector-ref v n) a)    n]
             [else (vindex-hlp (add1 n))]))])
    (vindex-hlp 0)))))

;; flatten takes a deep list removes all the inner parentheses from
;; its argument
(define flatten
(lambda (ls)
    (cond
      [(null? ls) '()]
      [(list? (car ls)) (append (flatten (car ls)) (flatten (cdr ls)))]
      [else (cons (car ls) (flatten (cdr ls)))])))

; other solution
(define flatten
(lambda (ls)
    (cond
      [(null? ls) '()]
      [(pair? ls) (append (flatten (car ls)) (flatten (cdr ls)))]
      [else        (list ls)])))