cis352f22-10-06.rkt

;; October 6, 2022
;; CIS352, Fall 2022
#lang racket

;; write the following in direct style
;; (i.e., perform recursive call, leave work
;; on the stack)

;; sum all elements in a list
(define (sum-list lst)
  (match lst
    ['() 0]
    [`(,hd . ,tl) (+ hd (sum-list tl))]))


;; multiply all elements in a list
(define (list-product lst)
  (match lst
    ['() 1]
    [`(,hd . ,tl) (* hd (list-product tl))]))

;; select only the elements of lst satisfying f
(define (filter lst f)
  (match lst
    ['() '()]
    [`(,hd . ,tl) (if (f hd)
                      (cons hd (filter tl f))
                      (filter tl f))]))

;; again, using #:when clause
(define (filtera lst f)
  (match lst
    ['() '()]
    [`(,hd . ,tl) #:when (f hd) (cons hd (filtera tl f))]
    [`(,_  . ,tl) (filtera tl f)]))

(define (even? x)
  (= (modulo x 2) 0))

(displayln (sum-list '(1 2 3)))
(displayln (list-product '(1 2 3)))
(displayln (filter '(1 2 3 4 5 6) even?))

;; next challenge: write these functions again
;; but tail recursively
(define (sum-list-tr lst)
  (define (h lst acc)
    (match lst
      ['() acc]
      [`(,hd . ,tl) (h tl (+ acc hd))]))
  (h lst 0))

(define (list-product-tl lst)
  (define (h lst acc)
    (match lst
      [`() acc]
      [`(,hd . ,tl) (h tl (* acc hd))]))
  (h lst 1))

;; fold over a list
;; updater is an "updater" function:
;;  - it takes two arguments:
;;    -> the next element to process
;;    -> the *current* accumulator
;;    -> this updater function returns the *next* accumulator
;;  - initial accumulator
;;  - list to process / walk / iterate over
#;(define (fold updater init lst)
  (match lst
    ['() init]
    [`(,hd . ,tl) (updater hd (fold updater init tl))]))

(define fold foldr)

(define (f next-element cur-accumulator)
  (+ next-element cur-accumulator))

(define (sum-list-using-fold lst)
  (fold (λ (next-element cur-accumulator) (+ next-element cur-accumulator))
        0
        lst))

(define (list-product-using-fold lst)
  (fold (lambda (next-elt acc) (* next-elt acc)) 1 lst))

(define (filter-using-fold lst f)
  (fold (lambda (next-elt acc)
          (if (f next-elt)
              (cons next-elt acc)
              acc))
        '()
        lst))

(define (reverse lst)
  (define (h lst acc)
    (match lst
      ['() acc]
      [`(,hd . ,tl) (h tl (cons hd acc))]))
  (h lst '()))

;; write filter as a tail-recursive funtion
(define (filter-tl lst f)
  (define (h lst acc)
    (match lst
      ['() acc]
      [`(,hd . ,tl) (if (f hd)
                        (h tl (cons hd acc))
                        (h tl acc))]))
  (reverse (h lst '())))