HackerRank in Racket: Part 2¶
这里是使用 Racket 完成 HackerRank 函数式编程题目的第二章,包含数学函数和 Lambda 演算(11 - 21 题
仓库:13m0n4de/HackerRank-FP-Solutions
11-Evaluating e^x¶
函数签名:
factorial : Integer -> Integer
eval-ex : Real -> Real
#lang racket
;; factorial : Integer -> Integer
(define (factorial n)
(let factorial-helper ([acc 1] [n n])
(if (= n 0)
acc
(factorial-helper (* acc n) (- n 1)))))
;; eval-ex : Real -> Real
(define (eval-ex x)
(let eval-ex-helper ([acc 0] [y 0])
(if (= y 10)
acc
(eval-ex-helper
(+ acc (/ (expt x y) (factorial y)))
(+ y 1)))))
(define (read-list)
(let read-list-helper ([acc '()])
(let ([x (read)])
(if (eof-object? x)
(reverse acc)
(read-list-helper (cons x acc))))))
(let* ([input (read-list)]
[lst (cdr input)])
(for-each (lambda (x)
(displayln (eval-ex x)))
lst))
12-Area Under Curves and Volume of Revolving a Curve¶
使用定积分计算曲线下面积和旋转曲线的体积。
函数签名:
polynomial : Real (Listof Real) (Listof Real) -> Real
integrate : Real Real Real (Listof Real) (Listof Real) (Real Real -> Real) -> Real
trapezoidal-area : Real Real Real (Listof Real) (Listof Real) -> Real
disk-method-volume : Real Real Real (Listof Real) (Listof Real) -> Real
计算多项式:
(define (polynomial x coefficients powers)
(for/fold ([acc 0])
([coefficient coefficients]
[power powers])
(+ acc (* coefficient (expt x power)))))
梯形法计算面积:
(define (trapezoidal-area a b delta-x coefficients powers)
(let trapezoidal-area-helper ([current-x a]
[current-y (polynomial a coefficients powers)]
[acc 0])
(let ([next-x (+ current-x delta-x)])
(cond
[(> current-x b) acc]
[(> next-x b) acc]
[else
(let* ([next-y (polynomial next-x coefficients powers)]
[area (* delta-x (/ (+ current-y next-y) 2))])
(trapezoidal-area-helper next-x next-y (+ acc area)))]))))
圆盘法计算体积:
(define (disk-method-volume a b delta-x coefficients powers)
(let disk-method-volume-helper ([current-x a]
[current-y (polynomial a coefficients powers)]
[acc 0])
(let ([next-x (+ current-x delta-x)])
(cond
[(> current-x b) acc]
[(> next-x b) acc]
[else
(let* ([next-y (polynomial next-x coefficients powers)]
[volume (/ (* delta-x pi (+ (sqr current-y) (sqr next-y))) 2)])
(disk-method-volume-helper next-x next-y (+ acc volume)))]))))
这两个函数计算积分的部分是通用的,创建 integrate
函数,该函数接受一个特定的积分计算函数作为参数:
(define (integrate a b delta-x coefficients powers integrand-fn)
(let integrate-helper ([current-x a]
[current-y (polynomial a coefficients powers)]
[acc 0])
(let ([next-x (+ current-x delta-x)])
(cond
[(> current-x b) acc]
[(> next-x b) acc]
[else
(let* ([next-y (polynomial next-x coefficients powers)]
[value (integrand-fn current-y next-y)])
(integrate-helper next-x next-y (+ acc value)))]))))
(define (trapezoidal-area a b delta-x coefficients powers)
(integrate a b delta-x coefficients powers
(lambda (current-y next-y)
(* delta-x (/ (+ current-y next-y) 2)))))
(define (disk-method-volume a b delta-x coefficients powers)
(integrate a b delta-x coefficients powers
(lambda (current-y next-y)
(/ (* delta-x pi (+ (sqr current-y) (sqr next-y))) 2))))
使用 read-line
、string-split
、string->number
解析输入数值:
(define (parse-line line)
(map string->number (string-split line)))
(define (read-input)
(let ([coefficients (parse-line (read-line))]
[powers (parse-line (read-line))]
[range (parse-line (read-line))])
(values coefficients powers (first range) (second range))))
完整代码:
#lang racket
;; polynomial : Real (Listof Real) (Listof Real) -> Real
(define (polynomial x coefficients powers)
(for/fold ([acc 0])
([coefficient coefficients]
[power powers])
(+ acc (* coefficient (expt x power)))))
;; integrate : Real Real Real (Listof Real) (Listof Real) (Real Real -> Real) -> Real
(define (integrate a b delta-x coefficients powers integrand-fn)
(let integrate-helper ([current-x a]
[current-y (polynomial a coefficients powers)]
[acc 0])
(let ([next-x (+ current-x delta-x)])
(cond
[(> current-x b) acc]
[(> next-x b) acc]
[else
(let* ([next-y (polynomial next-x coefficients powers)]
[value (integrand-fn current-y next-y)])
(integrate-helper next-x next-y (+ acc value)))]))))
;; trapezoidal-area : Real Real Real (Listof Real) (Listof Real) -> Real
(define (trapezoidal-area a b delta-x coefficients powers)
(integrate a b delta-x coefficients powers
(lambda (current-y next-y)
(* delta-x (/ (+ current-y next-y) 2)))))
;; disk-method-volume : Real Real Real (Listof Real) (Listof Real) -> Real
(define (disk-method-volume a b delta-x coefficients powers)
(integrate a b delta-x coefficients powers
(lambda (current-y next-y)
(/ (* delta-x pi (+ (sqr current-y) (sqr next-y))) 2))))
(define (parse-line line)
(map string->number (string-split line)))
(define (read-input)
(let ([coefficients (parse-line (read-line))]
[powers (parse-line (read-line))]
[range (parse-line (read-line))])
(values coefficients powers (first range) (second range))))
(define-values (coefficients powers a b) (read-input))
(define delta-x 0.001)
(displayln (trapezoidal-area a b delta-x coefficients powers))
(displayln (disk-method-volume a b delta-x coefficients powers))
13-Lambda Calculus - Reductions #1¶
Lambda 演算表达式简化。
- 将 \((λx.(x y))\) 应用于 \((λz.z)\),使用 \((λz.z)\) 替换 \(x\) 得到 \(((λz.z) y)\);
- 将 \((λz.z)\) 应用于 \(y\),得到 \(y\)。
y
14-Lambda Calculus - Reductions #2¶
- 将 \((λx.((λy.(x y))x))\) 应用于 \((λz.w)\),使用 \((λz.w)\) 替换 \(x\) 得到 \(((λy.((λz.w) y))(λz.w))\);
- 将 \((λy.((λz.w) y))\) 应用于 \((λz.w)\),使用 \((λz.w)\) 替换 \(y\) 得到 \(((λz.w) (λz.w))\);
- 将 \((λz.w)\) 应用于自身,它没有使用参数 \(z\),只是简单返回 \(w\)。
w
15-Lambda Calculus - Reductions #3¶
函数 \((λx.(x x))\) 应用到自身上,根据 β- 规约,将 \(x\) 替换为 \((λx.(x x))\),得到 \(((λx.(x x))(λx.(x x)))\),这个结果恰好又是原表达式的副本。
因此,这个表达式在逻辑上会无限次地重复自己。这种表达式在 λ 演算中被称为不动点组合子。
CAN'T REDUCE
16-Lambda Calculus - Reductions #4¶
- 将 \((λf.((λx.(f (x x)))(λx.(f (x x)))))\) 应用于 \(g\),使用 \(g\) 替换 \(f\) 得到 \(((λx.(g (x x)))(λx.(g (x x))))\);
- \(((λx.(g (x x)))(λx.(g (x x))))\) 是一个不动点组合子;
这个表达式通过自我应用来构造一个不动点组合子,接受一个函数 \(g\) 并返回 \(g\) 的不动点。这个表达式无法通过 β- 规约简化为单一项,因为它始终保持自引用的递归结构。
CAN'T REDUCE
17-Lambda Calculus - Evaluating Expressions #1¶
4
18-Lambda Calculus - Evaluating Expressions #2¶
- 计算 \((λy.y+2)3\) 得到 \(5\)。
- 用 \(5\) 替换 \((λx.x+1)\) 中的 \(x\),得到结果 \(6\)。
6
19-Lambda Calculus - Evaluating Expressions #3¶
邱奇数为使用邱奇编码的自然数表示法,而用以表示自然数 \(n\) 的高阶函数是个任意函数 \(f\) 映射到它自身的 n 重函数复合之函数,简言之,数的“值”即等价于参数被函数包裹的次数。
\(λx.λy.x^{47}y\) 意味着函数将 \(x\) 应用了 \(47\) 次到 \(y\) 上。
47
20-Lambda Calculus - Evaluating Expressions #4¶
自然数 \(2\) 的函数定义为 \(2fx=f(fx)\),Lambda 表达式为 \(λf.λx.f(fx)\)。
2
21-Lambda Calculus - Evaluating Expressions #5¶
自然数 \(0\) 的函数定义为 \(0fx=x\),Lambda 表达式为 \(λf.λx.x\)。
0