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

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

Попалась на глаза забавная и поучительная запись [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))

Бозон Хиггса в отдельно взятой программе

На задаче 136 проекта Эйлер я поймал бозон Хиггса: каждый запуск программы для ее решения дает новый ответ, достаточно близкий к правильному результату. Только при использовании Clisp, в то время как Sbcl и аналогичный варинат на Scheme (Guile) работают правильно. И только при достаточно больших значених аргументов, тестовые прогоны для небольших значений всегда стабильны.

P.S. А на Lispworks (personal edition) вообще не смог дождаться окончания работы программы.

В моих руках Scheme бьет Common Lisp :-)

Начинаю матереть в Scheme: проблему 128 Project Euler на Scheme (Guile) решаю за 40 секунд, а на Common Lisp (SBCL) за 60.

Интересно смотреть на числа

Интересно смотреть на числа.

За два года упражнений Project Euler я написал ровно 19000 строк кода на Scheme и Common Lisp:

[...]$ cat *.scm *.lisp | wc -l
19000

В основном на Scheme, на Common Lisp пару тысяч всего. Если убрать комментари и пустые строки, то будет примерно 8500 строк.

Scheme в использовании: Guile (в основном), Petite Chez Scheme, Chicken.

Common Lisp: SBCL, CLisp.

Доволен.