scheme - The Way 2 Inner Peace.

欧拉项目第28题.

https://projecteuler.net/problem=28

#lang racket

;give a n 
;output the outermost diagonal numbers of the n x n spiral form
(define (outermost n)
  (if (= n 1)
      (list 1)
      (build-list 4 (λ(x) 
                        (+ (* (sub1 n)(add1 x))
                           (sqr(- n 2)))))))

(define (build-diagonal n)
  (define (iter i r)
    (if (> i n)
        r
        (iter (+ 2 i)
              (append r (outermost i)))))
  (iter 1 '()))

(display (apply + (build-diagonal 1001)))

欧拉项目第12题.

https://projecteuler.net/problem=12

计算一个自然数的因子个数,用到了这里

racket...

#lang racket

(define (triangle x)
  (quotient (* x (add1 x)) 2))

(define (prime-factors n)
  (let loop ([n n] [m 2] [factors (list)])
    (cond [(= n 1) factors]
          [(= 0 (modulo n m)) (loop (/ n m) 2 (cons m factors))]
          [else (loop n (add1 m) factors)]))) 

;;cont n in l
(define (count-n l n)
  (cons n (count (lambda (x) (= n x)) l)))

;;count all n in l
(define (count-all l)
  (let loop ([l l] [visited '()] [r '()])
    (cond
      [(null? l) r]
      [(member (car l) visited) (loop (cdr l) visited r)]
      [else (loop (cdr l) 
                  (cons (car l) visited)
                  (cons (count-n l (car l)) r))])))

;;count all divisors of a number
;more in http://bit.ly/WLfeZN
(define (count-factor n)
  (let loop ([l (count-all(prime-factors n))] [r 1])
    (cond
      [(null? l) (cons r n)]
      [else (loop (cdr l) (* r (add1(cdar l))))])))

(define (tri-count-factor n)
  (count-factor (triangle n)))

(time(car(filter (lambda (x) (< 500 (car x))) 
                 (map tri-count-factor (range 10000 20000)))))

欧拉项目第14题.

https://projecteuler.net/problem=14

racekt.. 大概9秒.

#lang racket
(require racket/trace)
(define (col x)
  (cond
    [(> 0 x)x]
    [(even? x) (/ x 2)]
    [else (add1(* 3 x))]))
(define (gene-col x ht)
  (cond
    [(number? (hash-ref ht x null)) (hash-ref ht x)]
    [(= 1 x) (begin(hash-set! ht x 1)(hash-ref ht x))]
    [else (begin(hash-set! ht x (add1 (gene-col (col x) ht)))
                (hash-ref ht x))]))
;;alop is a list of pairs
(define (find-cdr alop h)
  (if(= h (cdr(car alop)))
     (car alop)
     (find-cdr (cdr alop) h)))
(define ht (make-hash))
(define answers(map (lambda (x) (gene-col x ht))(build-list 1000000 (lambda (x) (add1 x)))))
(find-cdr (hash->list ht) (apply max answers))

又十诫

来自The seasoned schemer

The Next Ten Commandments

The Eleventh Commandment

Use additional arguments when a function needs to know what other arguments to the function have been like so far.

The Twelfth Commandment

Use (letrec ...) to remove arguments that do not change for recursive applications.

The Thirteenth Commandment

Use(letrec ...) to hide and to protect functions.

The Fourteenth Commandment

Use(letcc¹ ...) to return values abruptly and promptly.

The Fifteenth Commandment

Use (let ...) to name the values of repeated expressions in a function definition if they may be evaluated twice for one and t he same use of the function. And use (let...) to name the values of expressions(without set!) that are re-evaluated every time a function is used.

The Sixteenth Commandment

Use (set! ...)only with names defined in (let ...)s.

The Seventeenth Commandment

Use(set! x ...) for (let((x ...)) ...) only if there is at least one (lambda ... between it and the(let ...),or if the new value for x is a function that refers to x .

The Eighteenth Commandment

Use (set! x ...) only when the value that x refers to is no longer needed.

The Nineteenth Commandment

Use (set! ...) to remember valuable things between two distinct uses of a function.

The Twentieth Commandment

When thinking about a value created with (letcc ...),write down the function that is equivalent but does not forget. Then, when you use it, remember to forget.

¹:letcc is call-with-current-continuation or call/cc in scheme

let,let*和letrec

在scheme中.let,let*和letrec的形式均写做:(id val-expr).即：

(let ([id val-expr] ...) body ...+),(let* ([id val-expr] ...) body ...+),(letrec ([id val-expr] ...) body ...+)

三者的不同在于,对id及val-expr的运算顺序不同.由此导致的结果也不同.

在let中.先依此所有的计算val-expr.在依此所有的计算id.

在let*中.先计算一个val-expr,将其赋值给id.在进行下一个(id val-expr)的计算.

在letrec中.id首先均为undefined.然后计算所有的val-expr.

由此:

(define foo 5)
;; foo 現在取值 5
(let ((foo 10))
  ;; foo 現在取值 10
  )
;; foo 現在取值 5

这三者的区别在于，let所绑定的变量仅在它的区块内有效，而let*所绑定的变量可以在以下的绑定中使用，例如，

(let* ((var1 10)
       (var2 (+ var1 5)))
  var1)
;; 返回 15
;; 如果僅使用 let，程式會出錯。

letrec所绑定的变量可以互相引用。因此，letrec通常被用于双重递归：

(letrec ((female (lambda(n)
                   (if (= n 0) 1
                       (- n (male (female (- n 1)))))))
         (male (lambda(n)
                 (if (= n 0) 0
                     (- n (female (male (- n 1))))))))
  (display "i male(i) female(i)")(newline)
  (do ((i 0 (+ i 1)))
      ((> i 8) #f)
    (display i) (display "   ")(display (male i))(display "         ")(display (female i))
    (newline)))

(via wikipedia)

同时剥去语法糖.

(let ((x 1))
(print x))
就是
((lambda (x) (print x)) 1)

(letrec ((fact (lambda (x)
                 (if (= x 1)
                    x
                    (* x (fact (- x 1)))))))
  (fact 5))
是
((lambda (fact x)
   (fact x fact))
(lambda (x fact)
   (if (= x 1)
      x
      (* x (fact (- x 1) fact))))
5)

也可以这样:

(letrec ((f (lambda ...))) ...)

就是

(let ((f <undefined>)) (set! f (lambda ...)) ...)

The Way 2 Inner Peace.