C311 Assignment 1 (Basic Scheme)

;;; 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)])))