Downloaded 11 times
Recursion and Functional Programming
- 1. Recursion - Secretsauce of Functional Programming
- 2. Imperative to FunctionalImmutability Intermediate state? No Looping constructs Iteration?
- 3. Scheme (dialect ofLisp) atom 42, foo list (foo bar)
- 4. (42 (foo bar))s-expressions – atom or list 42
- 5.
- 6.
- 7.
- 8. ( foo bar baz )
- 9.
- 10.
- 11.
- 12. ( bar baz )
- 13.
- 14.
- 15. cons (cons baz ())
- 16.
- 17.
- 18. ( bar baz )
- 19. (cons foo ( bar baz ) )
- 20. ( foo bar baz )
- 21. Primitive functions null?(null? ( quote () ) is #t
- 22. (null? foo) is #f
- 23. (null? ( foo bar )) is #f atom? (atom? foo ) is #t
- 24. (atom? ( foo bar )) is #f
- 25. (atom? ( quote() ) is #f eq? (eq? foo foo ) is #t
- 26. (eq? foo bar ) is #f
- 27. (member? foo ( quote () )) is #f
- 28. (member? oops ( foo bar baz )) is #f
- 29. (member? baz ( foo bar baz )) is #t foo == baz is #f
- 30. (member? baz (barbaz))
- 31. bar == bazis #f
- 32.
- 33. baz == bazis #t member?
- 34. member? ( define member? ( lambda (a lat) ( cond (( null? lat) #f) (else (or ( eq? ( car lat) a) (member? a ( cdr lat)))) )))
- 35. remove (remove bar(foo bar baz))
- 36. (foo baz) (define remove ( lambda (a lat) ( cond (( null? lat) (quote ())) (( eq? ( car lat) a) ( cdr lat)) (else ( cons ( car lat) (remove a ( cdr lat)))) )))
- 37. insertR (insertR bazbar (foo bar))
- 38. (foo bar baz)( define insertR ( lambda (new old lat) ( cond (( null? lat) (quote ())) (( eq? ( car lat) old) ( cons old ( cons new ( cdr lat)))) (else ( cons ( car lat) (insertR new old ( cdr lat)))) )))
- 39. insertL (insertL bazbar (foo bar))
- 40. (foo baz bar)( define insertL ( lambda (new old lat) ( cond (( null? lat) (quote ())) (( eq? ( car lat) old) ( cons new ( cons old ( cdr lat)))) (else ( cons ( car lat) (insertR new old ( cdr lat)))) )))
- 41. insert ( define insert ( lambda seq ( lambda (new old lat) ( cond (( null? lat) (quote ())) (( eq? ( car lat) old) ( seq new old lat)) (else ( cons ( car lat) (insertR new old ( cdr lat)))) ))))
- 42. insertR, insertL usingHOF ( define seqR ( lambda new old lat ( cons old ( cons new ( cdr lat))) )) ( define seqL ( lambda new old lat ( cons new ( cons old ( cdr lat))) )) ( define insertR (insert seqR)) ( define insertL (insert seqR))
- 43.
- 44.
- 45.
- 46.
- 47.
- 48.
- 49.
- 50. Addition + 5+ 3 = 1 + (5 + 2) = 1 + 1 + (5 + 1) = 1 + 1 + 1 + (5 + 0) = 1 + 1 + 1 + 5 = 1 + 1 + 6 = 1 + 7 = 8
- 51. Addition + (define + ( lambda (n m) ( cond (( zero? m) n) (else ( add1 (+ n (sub1 m)))) ))))
- 52. Multiplication X 5* 3 = 5 + (5 * 2) = 5 + 5 + (5 * 1) = 5 + 5 + 5 + (5 * 0) = 5 + 5 + 5 + 0 = 5 + 5 + 5 = 5 + 10 = 15
- 53. Multiplication X (define x ( lambda (n m) ( cond (( zero? m) 0) (else (+ n (x n (sub1 m)))) ))))
- 54. Exponent ^ 5^ 3 = 5 x (5 ^ 2) = 5 x 5 x (5 ^ 1) = 5 x 5 x 5 x (5 ^ 0) = 5 x 5 x 5 x 1 = 5 x 5 x 5 = 5 x 25 = 125
- 55. Exponent ^ (define ^ ( lambda (n m) ( cond (( zero? m) 1) (else (x n (^ n (sub1 m)))) ))))
- 56. Tuple addition (addtup(1 2 3 4 5)) = 1 + (addtup (2 3 4 5)) = 1 + (2 + (addtup (3 4 5))) = 1 + (2 + (3 + (addtup (4 5)))) = 1 + (2 + (3 + (4 + (addtup (5))))) = 1 + (2 + (3 + (4 + (5 + (addtup ()))))) = 1 + (2 + (3 + (4 + (5 + 0)))) = 1 + (2 + (3 + (4 + 5))) = 1 + (2 + (3 + 9)) = 1 + (2 + 12) = 1 + 14 = 15
- 57. Tuple addition (define addtup ( lambda (tup) ( cond (( null? tup) 0) (else (+ ( car tup) (addtup ( cdr tup)))) ))))
- 58.