Purely Functional Random-Access Lists implemented in Scheme (Racket)

2011-05-02T20:41:00.000+04:00

David Van Horn написал на Scheme (точнее, на Racket) чистый функциональный список с произвольным достпупом (исходники здесь).

Под капотом реализация из Okasaki (FPCA '95): список в виде дерева со всеми вытекющими.

Например:

$ (time (length (make-list (expt 2 100000) 'x)))
cpu time: 5659 real time: 5678 gc time: 1823
...
$ (define ls* (time (list-set ls 8989891824312123128989813 'q)))
cpu time: 1850 real time: 1864 gc time: 291

А если еще вспомнить Guy Steele (... foldl and foldr considered slightly harmful, pdf), то подобная реализация хорошо подходит для алгоритмов распараллеливания.

Easy Introduction to The Lambda Calculus

2011-04-26T00:19:00.003+04:00

Попалась на глаза забавная и поучительная запись [Easy Introduction to] The Lambda Calculus. Может быть даже не easy, а funny introduction.

Там при помощи Scheme "на пальцах" показано, почему lambda, собственно говоря, the ultimate.

К примеру

(define (true a b) a) 
(define (false a b) b) 
(define (if c a b) (c a b))
...
(define (cons a b) (λ (c) (if c a b))) 
(define (car c) (c true)) 
(define (cdr c) (c false))

yuridichesky

Purely Functional Random-Access Lists implemented in Scheme (Racket)

Easy Introduction to The Lambda Calculus