Racket Programming: List Manipulation and Sorting

Posted on Feb 14, 2025 in Architecture

Variable Definitions

These variables are used for testing the functions to ensure they operate as expected.

  • x: '(1 2 3 4 5 6 7 8 9 10) (Used for deep-member? and steamroller functions)
  • y: '(((a) b) (c d (d (f g) h)) i) (Used for deep-member? function)
  • z: '(a f c d f g e g h e g e e) (Used for the splitter function)
  • a: '(1 3 5 7 9) (Used for the merge function)
  • b: '(2 4 6 8 10) (Used for the merge function)
  • x1: '(12 23 2 5 64 23 6756 234 2 42 535) (Used for the mymergesort function)
  • x2: '(how does he do that cool stuff?) (Used for the mymergesort function)
  • x3: '(I can "go" 4 "about" 123 sodas k?) (Used for the mymergesort function)

Steamroller Function

Removes all nested lists inside of a list, flattening it into a single list.

(define steamroller
  (lambda (myList)
    (cond ((null? myList) '())
          ((pair? myList) (append (steamroller (car myList)) (steamroller (cdr myList))))
          (else (list myList)))))

Ndelete Function

Removes elements from a list at intervals of N (1N, 2N, 3N, … positions).

(define ndelete
  (lambda (myList N)
    (cond ((< (length myList) N) myList)
          (else (append (take myList (- N 1)) (ndelete (drop myList N) N))))))

Deep-member? Function

Checks if an atom val is a member of a potentially deeply nested list.

(define deep-member?
  (lambda (val myList)
    (cond ((null? myList) #f)
          ((list? (car myList)) (or (deep-member? val (car myList)) (deep-member? val (cdr myList))))
          ((equal? (car myList) val) #t)
          (else (deep-member? val (cdr myList))))))

MyMergeSort Function

Sorts a list using the merge sort algorithm.

(define mymergesort
  (lambda (alist)
    (if (null? (cdr alist)) alist
        (let ((splits (splitter alist)))
          (merge (mymergesort (car splits)) (mymergesort (cadr splits)))))))

Splitter Function

Splits a list into two sublists. If the list has an odd number of elements, the first sublist gets the extra element.

(define splitter
  (lambda (myList)
    (let-values (((left right) (split-at myList (floor (/ (+ (length myList) 1) 2))))) (list left right))))

Merge Function

Merges two sorted lists into a single sorted list.

(define merge
  (lambda (list1 list2)
    (cond ((null? list1) list2)
          ((null? list2) list1)
          ((isLess? (car list1) (car list2)) (cons (car list1) (merge (cdr list1) list2)))
          (else (cons (car list2) (merge list1 (cdr list2)))))))

isLess? Function

Compares two values, handling mixed types (integers, symbols, strings).

(define isLess?
  (lambda (val1 val2)
    (cond ((and (integer? val1) (integer? val2)) (< val1 val2))
          ((and (symbol? val1) (symbol? val2)) (symbol<? val1 val2))
          ((and (string? val1) (string? val2)) (string<? val1 val2))
          ((integer? val1) #t)
          ((integer? val2) #f)
          ((string? val1) (string<? val1 (~a val2)))
          (else (string<? (~a val1) (~a val2))))))