;; Part 2: Recursive Definitions

; You have to provide definitions for the function stubs below. You
; can use auxiliary definitions, if you need them. You have to use the
; design recipe and the design guidelines presented in class.



;number-elements-helper : true-list nat -> Numbered list
(defun number-elements-helper (L i)
  (if (endp L)
    nil ; if list is empty then return empty list
    ;i is the current index of the position of the recursive walk
    ;we are taking over the list
    (cons (list i  (car L));one step
          (number-elements-helper (cdr L) (+ 1 i)))));assume recursive call works

(check= (number-elements-helper '(a b c) 4) (list '(4 a) '(5 b) '(6 c)))
(check= (number-elements-helper '(a b c) 0) (list '(0 a) '(1 b) '(2 c)))


; number-elements: true-list -> NumberedList
; NumberedList is a list of 2-element lists
; Implementation details: recursively define an auxiliary
; function whose second argument is the index.

(defun number-elements (l)
"Usage: Here is an example of how this works. Given the list
 (a b c) number-elements should return ((0 a) (1 b) (2 c)).
 In general, given a list l, number-elements numbers the
 elements of l by returning a 2-element list whose first element
 is the index, say n, and whose second element is the nth
 element of l. Indexing starts from 0."
  (number-elements-helper l 0))

; in: All true-list -> Boolean
(defun in (x l)
"Usage: Searches l for x and returns t if it is found, nil otherwise. "
  (if (endp l);Base case
    nil; got to end of list, not found, return nil
    ;x is either the first element OR its in the rest of the list
    (or (= x (car l))
        (in x (cdr l)))))

(check= (in 3 (list 1 2 3 4)) t)
(check= (in 5 (list 1 2 3 4)) nil)
(check= (in 5 nil) nil)
(check= (in "hello" 65) nil);totality
;you should write more tests

; rem-dups: true-list -> true-list
(defun rem-dups (l)
"Usage: Returns a new list which is l without the duplicate elements"
  (if (endp l);base case
    nil;nothing in the list, return as it is
    ;now check if first element is duplicated in the rest of the list,
    ;if it is then we just skip it, rebuilding a new partial list which
    ;has one less duplicate item.
    (if (in (car l) (cdr l))
      (rem-dups (cdr l));call rem-dups on the rest of list and we know this works
      ;correctly as its being called on a smaller argument.
      ;otherwise we know that first element is not duplicated, so we
      ;we keep it while reconstructing a non-duplicate list
      (cons (car l)
            (rem-dups (cdr l))))));assume rem-dups works on smaller arg.

(check= (rem-dups '(1 5 5 2 3 4 4 3 3 3 2)) '(1 5 4 3 2))
;notice the order, the last duplicate is kept, for an exercise write a function which does the same
;thing but keeps the order of the original elements, that is the first duplicate position intead
;of above i.e write rem-dups such that 
;(rem-dups '(1 5 5 2 3 4 4 3 3 3 2)) '(1 5 4 3 2)) == '(1 5 2 3 4))

; ordered-elementp: true-list -> Boolean
(defun ordered-elementp (l)
"Usage: Returns true if x is ordered with the relation <, nil otherwise."
  (if (endp l);base case 1
    t;an empty list is ordered trivially, because it has no elements to be ordered
    (if (endp (cdr l)) ;base case 2, if the list has only one element, it is trivially
      ;ordered, how to check if list has one element, well just check if rest of list
      ;is empty.
      t
    ;other wise make sure that the first element is ordered with respect to 
    ;second element, and also that the rest of the list is ordered
      (and (< (car l) (cadr l)) ;or you can write (< (first l) (second l))
           (ordered-elementp (cdr l))))))

(check= (ordered-elementp '(1 2 5 99)) t)
(check= (ordered-elementp '(1 22 5 9)) nil)

(check= (ordered-elementp nil) t)
(check= (ordered-elementp (list 555)) t)



; merge-ordered: OrderedList OrderedList -> OrderedList
; OrderedList is a list of elements ordered with the relation <
(defun merge-ordered (l1 l2)
"Usage: Returns a list containing the elements in l1 l2, ordered with the relation <"
  (if (endp l1);recurring on l1, the base case is l1 is empty
    l2
    (if (endp l2);base case 2 (second arg is empty)
      l1 ;this function is more tricky than others, since we need to recur on
      ;both arguments simultaneously, which you havent seen till now.
      ;now if both lists are not empty, then we compare their first
      ;elements and compare them,
      (if (< (car l1) (car l2))
        (cons (car l1)
              (merge-ordered (cdr l1) l2));Recursive call 1.
        (cons (car l2)
              (merge-ordered l1 (cdr l2)))))));recursive call 2
;make a diagram to understand the above, i might explain this in class on monday.

(check= (merge-ordered '(1 4 9) '(3 5 6)) '(1 3 4 5 6 9))