2013-11-10

級数と再帰

LISP

順列・組み合わせ・重複組み合わせの通りの数は $_nP_r = n\times _{n-1}P_{r-1}, _nC_r = _{n-1}C_{r-1} + _{n-1}C_r,_rH_n = _nH_{r-1} + _{n-1}H_r$ なので

(define perm
 (lambda (n r)
  (cond ((= r 0) 1)
        ((= r 1) n)
        (else (* n (perm (- n 1) (- r 1)))) )))
(define comb
 (lambda (n r)
  (cond ((= r 0) 1)
        ((= r n) 1)
        (else (+ (comb (- n 1) (- r 1)) (comb (- n 1) r))))))
(define rept
 (lambda (n r)
  (cond ((= r 0) 1)
        ((= n 1) 1)
        (else (+ (rept n (- r 1)) (rept (- n 1) r))))))
(define n! (lambda (n) (perm n n)))

> (perm 5 3)
60
> (comb 5 3)
10
> (rept 5 3)
35
> (n! 5)
120

ゼータ関数 $\zeta(k) = \sum_{n=1}^{\infty} \frac{1}{n^k}$

> (define nums (iota 6))
(apply + (map / (map * nums nums)))
(exact->inexact (apply + (map / (map * nums nums))))

1 1769/3600
1.4913888888888889
> (define nums (iota 100))
(apply + (map / (map * nums nums)))

1 617322549698656842522639951844930715540407914547963618106712480098300144925121901/972186144434381030589657976672623144161975583995746241782720354705517986165248000
> (exact->inexact (apply + (map / (map * nums nums))))

1.6349839001848927

$\zeta(2)=\frac{\pi^2}{6},\zeta(4)=\frac{\pi^4}{90},\zeta{6}=\frac{\pi^6}{945}$

> (define nums (iota 100))

(exact->inexact (apply + (map / (map * nums nums))))
(exact->inexact (apply + (map / (map * nums nums nums nums))))
(exact->inexact (apply + (map / (map * nums nums nums nums nums nums))))
(define pi (* 4 (atan 1)))
(/ (** pi 2) 6)
(/ (** pi 4) 90)
(/ (** pi 6) 945)

1.6349839001848927
1.0823229053444732
1.0173430619649442
1.6449340668482264
1.082323233711138
1.017343061984449

交代級数 $1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}=\sum_{i=1}^{\infty}(-1)^{i+1}\times \frac{1}{i}$

(begin
 (define num-x (iota 1000))
 (define parity-of (lambda (p) (if (odd? p) -1 1)))
 (define parity-x (map parity-of num-x))
 (define terms (map / (map * (map - parity-x) num-x)))
 (* 1.0 (apply + terms)))
(log 2)
(define prototype
 (lambda (n k)
  (if (> n k)
   0
   (+ (/ 1.0 (* (** -1 (- n 1)) n))
    (prototype (++ n) k)) )))

0.6926474305598204
0.6931471805599453

> (prototype 1 1000)
0.6926474305598203

$\sum$ 記号処理が表す総和とは

(define sum
 (lambda (initial final body)
  (if (> initial final)
   0
   (+ (body initial)
      (sum (++ initial) final body) ))))
(define log2
 (lambda (n) ( / (** -1 (- n 1)) n)))
(* 1.0 (sum 1 1000 log2))
(exact->inexact (sum 1 1000 log2))
(log 2)

$\sum_{i=0}^{\infty} \frac{(-1)^n}{2n+1}=\frac{\pi}{4}$

(define leibniz
 (lambda (n) (/ (** -1 n) (+ (* 2 n) 1) )))
(sum 0 1000 leibniz)
(exact->inexact (sum 0 1000 leibniz))
(/ pi 4)

115942754151379749817711499381045829538776769987994283426499174405197859288323135015330300912135070917816946458268092800852360239620177277413429787387349551255003615589569573379800196665329506848656083889369709177405427782467224427236659450935894659229706538420713135430149967239530040710861446951911777821474393129612397845507403965163361525407992992632094863429705101531309515395981444782245447089519458224628701225883500761695065661112790727759938282092270127334705631552774809895098881487984328201218643687326889146827085154438452729289541791425462272951568049058813743132462586534037658186884976579734076397974087562265189907855568091436223915148765419793957077042562861450986938251183985051264149570092106286182764399032728528708672749045573389234562924779885205262978316936978847078635153915075455692080484634049862051993120512957807952166632232781452985693/147575971560004214167515926110910959154039364114823574124246000461914527658542221342892735221356393498040967787373958507841987262911496051590667501531330247838135978840974443799253538292640926269840668436150204200349824875106342825692216080195797882561278687544853408492239067897668276741020722024722920647043361291050258670152054452602340630932745172382890465777119545919256355735334085680330696670323581795898987569556701349947230648600924724829339703465619153667400785835767829015255912124437120483654244048802954353182627323647253464533187610294513012889059213560214079942586690820627448621251921400116373405117084193399206770968054536747884759653724084204389207798419572074824626227112973906822764943279686533643894351344307463662830610651081788025023698731546719066865315845423963070220368816149003349877146224784348331677667520210577535211126744546685023125
0.7856479135848857
0.7853981633974483

ゼータ関数 $\frac{i=1}^{\infty} \frac{1}{i^k}$

(define zeta2
 (lambda (n) (/ (** n 2))))
(exact->inexact (sum 1 1000 zeta2))
(define zeta-k
 (lambda (k) (lambda (n) (/ (** n k)))))
(exact->inexact (sum 1 1000 (zeta-k 2)))
(exact->inexact (sum 1 1000 (zeta-k 6)))

が表す乗積を
- それを使って $\prod_{i=1}^{\infty} \frac{2i}{2i+1}\frac{2i+2}{2i+2}=\frac{\pi}{4}$

(define product
 (lambda (initial final body)
  (if (> initial final)
   1
   (* (body initial)
      (product (++ initial) final body) ))))
(define pi/4
 (lambda (n)
  (* (/ (* 2 n) (+ (* 2 n) 1)) (/ (+ (* 2 n) 2) (+ (* 2 n) 1)))))
(* 4.0 (product 1 1000 pi/4))

- 階乗 $n!$

(define fact
 (lambda (i) (if (= i 0) 1 i)))
(product 0 10 fact)

累積処理として統一化する

(define accumulate
 (lambda (op ini seqs)
  (if (null? seqs)
   ini
   (op (car seqs)
       (accumulate op ini (cdr seqs))))))
(define sum
 (lambda (ini fin body)
  (accumulate + 0 (map body (iota ini fin)))))
(define product
 (lambda (ini fin body)
  (accumulate * 1 (map body (iota ini fin)))))
(define num (lambda (i) i))
(sum 0 100 num)
(product 1 10 num)

ネイピア数 $e=\sum_{i=0}^{\infty} \frac{1}{i!}$ は

(define napier
 (lambda (n)
  (/ (product 0 n fact))))
(exact->inexact (sum 0 10 napier))
(exp 1)

十分近いことをもって正しいと判断して抜き出す

(define pow2?
 (lambda (x)
  (let ((y (inexact->exact (round (** x 1/2)))))
   (if (= x (** y 2)) #t #f) )))
(pow2? 121)

(define pow3?
 (lambda (x)
  (let ((y (inexact->exact (round (** x 1/3)))))
   (if (= x (** y 3)) #t #f))))
(filter pow3? (iota 1000))

2013-11-10

データ構造

LISP

Last In First Out (LIFO)

(define stack '())
(define set-stack
 (lambda ()
  (set! stack '())
  'done))
(define push
 (lambda (x)
  (cond ((null? stack) (set! stack (list x)))
        (else (set! stack (cons x stack))))
   stack))
(define pop
 (lambda ()
  (let ((tmp '()))
   (cond ((null? stack) '())
         (else (set! tmp (car stack))
               (set! stack (cdr stack))
               tmp) ))))

(set-stack)
(push 'a)
(push 'b)
(push 'c)
(pop)
(pop)
(pop)
(pop)
done
(a)
(b a)
(c b a)
c
b
a
()

First In First Out (FIFO)

(define queue '())
(define tail '())
(define set-queue
 (lambda ()
  (set! queue '())
  (set! tail '())
  'done))
(define enqueue
 (lambda (x)
  (cond ((null? queue)
          (set! queue (list x))
          (set! tail queue))
        (else (set-cdr! tail (list x))
              (set! tail (cdr tail))))
  queue))
(define dequeue
 (lambda ()
  (let ((tmp '()))
   (cond ((null? queue) '())
         (else (set! tmp (car queue))
               (set! queue (cdr queue))
               tmp) ))))

> (set-queue)
done
> (enqueue 'a)
(a)
> (enqueue 'b)
(a b)
> (enqueue 'c)
(a b c)
> (dequeue)
a
> (dequeue)
b
> (dequeue)
c
> (dequeue)
()

(define dfs-w (lambda (tree)
 (define chk (lambda (tree)
  (cond ((null? tree) (reverse stack))
        ((nonpair? tree) (push tree))
        (else (chk (car tree))
              (chk (cdr tree))))))
 (set-stack) (chk tree)))
(define data '((a1 (b1)(b2)) (a2 (b3))))
(dfs-w data)

ひたすら探して、あったら登録、なければスキップ

(define fail '())
(call/cc (lambda (f-cc)
 (set! fail
  (lambda () (if (null? stack)
                 (f-cc 'empty)
                 ( ((pop)) ))))))
(define choose
 (lambda x
  (if (null? x)
      (fail)
      (call/cc (lambda (c-cc)
       (push (lambda () (c-cc (apply choose (cdr x)))))
       (car x))) )))
(set-stack)
(choose)
(choose 'test)

(define odd-killer
 (lambda ()
  (let ((x (choose 1 2)))
   (if (odd? x)
    (fail)
    x) )))
(define two-nums
 (lambda ()
  (list (choose 2 3)
        (choose 5 7) )))

(two-nums)
(fail)
(fail)
(fail)
(fail)

(2 5)
(2 7)
(3 5)
(3 7)
empty

2013-11-10

函数型言語とは

LISP

繰り返し処理を定義する

(define zero (lambda (s) (lambda (z) z)))
(define one  (lambda (s) (lambda (z) (s z))))
(define two  (lambda (s) (lambda (z) (s(s z)))))
(define three (lambda (s) (lambda (z) (s(s(s z))))))

0にadd1を２回適用する

((two add1) 0)

繰り返し処理の別定義

(define compose
 (lambda (f g)
  (lambda (x) (f (g x)))))
(define repeated
 (lambda (f n)
  (if (zero? n)
   (lambda (x) x)
   (compose f (repeated f (-- n))) )))
((repeated add1 7) 3)

自然数を０から作る。「１段階上げる」という操作だけでそうする

(define Succ
 (lambda (v) (lambda (s) (lambda (z)
  (s ((v s) z)) ))))

> ((two add1) 0)
2
> (((Succ two) add1) 0)
3
> (((Succ one) add1) 0)
2
> (((Succ zero) add1) 0)
1
> (((Succ (Succ zero)) add1) 0)
2

add1という処理を「２回やる」と「３回やる」との加算

(define Plus
 (lambda (u v) (lambda (s) (lambda (z)
  ((u s) ((v s) z)) ))))

> (((Plus two three) add1) 0)
5