09-14.rkt

#lang racket

;; CIS352 -- Fall 2023
;; Lambdas

;; first order function -- no functions as arguments
;; O(n^2) the way it's written -- an easier implementation
;; is not easy functionally, need a different representation 
(define (reverse lst)
  (if (empty? lst)
      '()
      ;; the rule for primitive recursive functions says that
      ;; my recursive call *has to use* (rest lst)
      (append (reverse (rest lst)) (list (first lst)))))

;; this function is *higher-order* because it is parametric
;; on the input function f : A → Bool (assuming lst : listof A)
(define (filter lst f)
  (cond
    [(empty? lst) '()]
    [(f (first lst)) (cons (first lst) (filter (rest lst) f))]
    [(not (f (first lst))) (filter (rest lst) f)]))

;; call filter on (range 100) with a function that returns every
;; third element. How to do it? Define a function using `define`
;; that returns n % 3 = 0 
(define (n-mod-three-equals-zero? n)
  ;; hint: use modulo
  (equal? (modulo n 3) 0))

;; these two are equivalent
(filter (range 100) n-mod-three-equals-zero?)
(filter (range 100) (lambda (n) (equal? (modulo n 3) 0)))
;; (define f-123 (lambda (n) (equal? (modulo n 3) 0)))
;; (define (f-123 n) (equal? (modulo n 3) 0))
;; (filter (range 100) f-123)

(lambda () 1)

((lambda (x y) (+ x y)) 1 2)

(define f (lambda (x) x))
(define (double g)
  (lambda (x) (g (g x))))

;; Using textual reduction to understand how this would work on an example
;;
;; ((double add1) 5)
;; ((lambda (x) (add1 (add1 x))) 5)
;; (add1 (add1 5))
;; 7

;; Via textual reduction for lambdas, I could compute the reduction
;; sequence for the following example
((double (lambda (x) (* x 2))) 2)
((λ (y) ((lambda (x) (* x 2)) ((lambda (x) (* x 2)) y))) 2)
((lambda (x) (* x 2)) ((lambda (x) (* x 2)) 2))
((lambda (x) (* x 2)) (* 2 2))
((lambda (x) (* x 2)) 4)
(* 4 2)
8

(define (foo f) (λ (x) (f (abs x))))
((foo (λ (x) (* 2 x))) -5)

;; reducing via textual reduction
((λ (y) ((λ (x) (* 2 x)) (abs y))) -5)
((λ (x) (* 2 x)) (abs -5))
((λ (x) (* 2 x)) 5)
(* 2 5)
10

;; ((((lambda (x) x) (lambda (x) x)) 
;;  ((lambda (x) x) (lambda (x) x)))
;;   (+ 1 2))
;; ↦
;;(((lambda (x) x) 
;;  ((lambda (x) x) (lambda (x) x)))
;;  (+ 1 2))
;; ↦
;; (((lambda (x) x) (lambda (x) x)) (+ 1 2))
;; ↦
;; ((lambda (x) x) (+ 1 2))
;; ↦
;; ((lambda (x) x) 3)
;; ↦
;; x [x ↦ 3] =
;; 3

(define (make-counter n)
  (λ () (cons n (make-counter (+ n 1)))))

;; assume that counter was generated by make-counter for some fixed k
;; invoke the counter n times, and return the result (i.e., the car
;; you get from that operation)
(define (get-nth-value counter n)
  (define (h c n)
    (if (= n 0)
        (car (c))
        (h (cdr (c)) (- n 1))))
  (h counter n))

;; Racket returns *closures*, not just lambdas
;; those closures contain code *plus* data
;; in this case, they contain the lambda, plus the
;; the binding for k
(define (constant k)
  (λ (x) k))