Алгоритмы, Функциональное программирование Опции

[DEADHUNT]

Предлагаю в этой теме собирать вычислительные алгоритмы реализованные на функциональных языках.
Вычисление числа Пи путём интегрирование функции 1 / sqrt (1 - x^2) в пределах [-1; 1] методом центральных прямоугольников(sqrt вычисляется по алгоритму Ньютона):

(define (sqrt x)
    (define (sqrt_helper x y)
    (if (< (abs (- (square y) x)) 0.000001)
        y
        (sqrt_helper x (/ (+ y (/ x y)) 2))))
    (sqrt_helper x 1.0))
        
(define (pi)
    (define (f x)
        (/ 1.0 (sqrt (- 1.0 (square x)))))
    (define (pi_helper x lim h value)
        (if (> x lim)
            value
            (pi_helper (+ x h) lim h (+ value (* (f (+ x (/ h 2))) h)))))
    (pi_helper (- (- 1.0 0.000001)) (- 1.0 0.000001) 0.000001 0.0)
    )

Вычисление числа Пи путём интегрирование функции 1 / sqrt (1 - x^2) в пределах [-1; 1] методом Cимпсона:

integral f a b = (integral_helper f a a b 0 0) * 0.00001 / 3
            where
                integral_helper f x a b n sum | x == a = integral_helper f (x + 0.00001) a b 4 (f x)
                                | x >= b = sum + f b
                                | otherwise = integral_helper f (x + 0.00001) a b (if n == 2 then 4 else 2) (sum + n * f x)

main = print(integral (\x -> 1 / (sqrt(1 - x * x))) (-1 + 0.00001) (1 - 0.00001))

также принимается критика и усовершенствования этих алгоритмов.

Сообщение отредактировал DEADHUNT - 29.8.2010, 3:03

[Litkevich Yuriy]

DEADHUNT, а на каком языке приведён код?

[DEADHUNT]

DEADHUNT, а на каком языке приведён код?

первый - lisp(scheme)
второй - haskell

где-то на форуме уже видел код на haskell.

[DEADHUNT]

написал алгоритм дифференцирования линейных функций(наподобие как в книге SICP(Structure and Interpretation of Computer Programs))

(define (variable? x)(symbol? x))

(define (same-variable? x y)(and (variable? x) (variable? y) (eq? x y)))

(define (make-sum x y)(list '+ x y))

(define (make-prod x y)(list '* x y))

(define (sum? x)(and (pair? x) (eq? '+ (car x))))

(define (prod? x)(and (pair? x) (eq? '* (car x))))

(define (first-op x)(cadr x))

(define (second-op x)(caddr x))

(define (deriv expr x)
    (cond ((number? expr) 0)
          ((variable? expr)(if (same-variable? expr x) 1 0))
          ((sum? expr)(make-sum (deriv (first-op expr) x) 
                                (deriv (second-op expr) x)))
          ((prod? expr)(make-sum (make-prod (deriv (first-op expr) x)
                                            (second-op expr))
                                 (make-prod (first-op expr)
                                            (deriv (second-op expr) x))))
          (else error "unknown expression")))

примеры использования:
(x + 3)':

> (deriv '(* 3 x) 'x)
> (+ 1 0)

(5x + 3)':

> (deriv '(+ (* 5 x) 3) 'x)
> (+ (+ (* 0 x) (* 5 1)) 0)

ради интереса можно продолжить усовершенствование данной программы.