Ответ на »сообщение 2031« (Geniepro)
___________________________

>>>А вот теперь Вам спасибо за хорошую ссылку! ;о)

Я рад, если эта книга показалась Вам заслуживающей внимания.
Такой момент: литературу по ФП откапываю только в Интернете, в бумажном виде -- ничего.
Точнее, почти ничего, т.к. неожиданно для себя выяснил что в классическом учебнике "Информатика" Бауэра и Гооза 2-я глава ("Основные понятия программирования") посвящена именно ФП (просто там не употребляется это словосочетание; уже потом, в 3-й главе речь заходит о машинно-ориентированных языках программирования).
Например, раздел 2.4 называется "О технике рекурсивного программирования".

>>>Осталось только осилить эти 686 страниц... :о))

Аналогично. :)
К сожалению, времени постоянно не хватает. :(
Поэтому и пытаюсь при случае продвигаться вперед "большими рывками" -- иначе не получается.

Ответ на »сообщение 2030« (AVC)
___________________________

Заинтересовавшись Схемой, откопал в интернете электронную книгу "Concrete Abstractions: An Introduction to Computer Science Using Scheme"

А вот теперь Вам спасибо за хорошую ссылку! ;о)
Осталось только осилить эти 686 страниц... :о))

Заинтересовавшись Схемой (причина, как и в Обероне, -- не надо мучиться с "увесистым" синтаксисом), откопал в интернете электронную книгу "Concrete Abstractions: An Introduction to Computer Science Using Scheme":

http://www.gustavus.edu/+max/concrete-abstractions-pdfs/list.cfm

(нажать кнопку "The entire book in one file").
Возможно, кого-то заинтересует.

Я тут несколько увлекся "публикацией" своего ученического кода на Схеме. :)
Немного поясню, почему я это делаю.
Во-первых, возымели действие призывы "функциональщиков" Jack of Shadows и Geniepro, и я решился-таки заняться ФП хотя бы в небольшом объеме.
Обсуждая код, я надеюсь продвигаться в обучении быстрее.
Во-вторых, в последнее время было много споров между "оберонщиками" и "функциональщиками", иногда исключительно "метафизические".
Мое убеждение, что в спорных вопросах программисты должны иметь возможность общаться на уровне кода. Иначе так и будем препираться без толку (в то время как и причины-то, возможно, нет).
Т.к. присутствующие на форуме функциональщики пишут на ИЯ, а многие оберонщики (за явным исключением Trurl) не пишут на ФЯ, то решил немного "выровнять ситуацию". :)

Ответ на »сообщение 2026« (AVC)
___________________________

А это тест, который я использовал для полученной сортировки:

; генератор случайных чисел (по кн. Рейзера и Вирта)
(define rand
    (let ((z 1))
      (lambda ()
        (define a 16807)
        (define m 2147483647)
        (define q (quotient m a))
        (define r (modulo m a))
        (define g (- (* a (modulo z q)) (* r (quotient z q))))
        (set! z (if (> g 0) g (+ g m)))
        (* z (/ 1.0 m)))
        ))

; генератор псевдослучайной последовательности. Использовал для тестирования sort1
(define (rand-series n)
    (define (rnds lst n)
      (if (= n 0)
          lst
          (rnds (cons (rand) lst) (- n 1))))
    (rnds '() n))

; проверка неубывания ряда
(define (check lst)
    (define (chk lst prev)
      (cond
        ((null? lst) #t)
        ((< (car lst) prev) #f)
        (else (chk (cdr lst) (car lst)))))
    (if (null? lst)
        #t
        (chk (cdr lst) (car lst))))

; собственно тест
> (check (sort1 (rand-series 100000)))
#t

Ответ на »сообщение 2024« (Jack Of Shadows)
___________________________
То же самое на хаскеле:

distil xs@(e : _) = distill xs [] [] []
    where
    distill [] l m r = (l, m, r)
    distill (y : ys) l m r
        | e > y      = distill ys (y:l) m r
        | e == y    = distill ys l (y:m) r
        | otherwise  = distill ys l m (y:r)

dsort [] = []
dsort x = dsort l ++ m ++ dsort r
            where (l,m,r) = distil x

Ответ на »сообщение 2025« (AVC)
___________________________

>>>Конечно, код можно написать гораздо лучше; просто немного тяжко с непривычки.

Возможно, так будет лучше:
(define (sort1 x)
    (define (partition lst value left right)
      (cond
        ((null? lst) (append (sort1 left) (list value) (sort1 right)))
        ((< (car lst) value) (partition (cdr lst) value (cons (car lst) left) right))
        (else (partition (cdr lst) value left (cons (car lst) right)))))
    (if (null? x) '() (partition (cdr x) (car x) () ())))

Ответ на »сообщение 2024« (Jack Of Shadows)
___________________________

>>>Я даже не понял че вы там написали :)) Разбираться надо.

Как говорится, знай наших! :)
Конечно, код можно написать гораздо лучше; просто немного тяжко с непривычки.

Ответ на »сообщение 2023« (AVC)
___________________________
Я даже не понял че вы там написали :)) Разбираться надо.

(defun distil (list)
  (labels ((distill (etalon list left middle right)
            (if list (cond ((equal etalon (car list)) (distill etalon (cdr list) left (cons (car list) middle) right))
                            ((> etalon (car list))    (distill etalon (cdr list) (cons (car list) left) middle right))
                            ((< etalon (car list))    (distill etalon (cdr list) left middle (cons (car list) right))))
              (values left middle right))))
    (distill (car list) list nil nil nil)))


(defun fast-sort (x)
  (if x (multiple-value-bind (left middle right) (distil x)
          (append (fast-sort left) middle (fast-sort right)))
    nil))

Ответ на »сообщение 2022« (Jack Of Shadows)
___________________________

Ответ на »сообщение 2021« (AVC)
___________________________
Заметьте, что мы гоняем один и тот же список три раза (фильтруем left middle right), хотя можно все три части получить за один прогон.
Напишите функцию distill которая принимает эталон и список и возвращает три списка left middle right за один рекурсивный прогон.
А потом уже эту функцию можно использовать в sort
Это покажет вам как в лиспе можно возвращать (и соответственно принимать) сразу несколько значений.

Уф, нелегкая это работа! :)
По первому разу получилось что-то страшненькое:

(define (left x) (car x))
(define (middle x) (cadr x))
(define (right x) (cddr x))
(define (make3 left middle right)
    (cons left (cons middle right)))
(define (build3 x)
    (define (build3-inside m3 x)
      (define z (car (middle m3)))
      (cond
        ((null? x) m3)
        ((< (car x) z) (build3-inside (make3 (append (left m3) (list (car x))) (middle m3) (right m3)) (cdr x)))
        ((= (car x) z) (build3-inside (make3 (left m3) (append (middle m3)(list (car x))) (right m3)) (cdr x)))
        ((> (car x) z) (build3-inside (make3 (left m3) (middle m3) (append (right m3) (list (car x)))) (cdr x)))
      ))
    (if (null? x) (() () ()) (build3-inside (make3 () (list (car x)) ()) (cdr x))))
(define (JoS-sort x)
    (define (sort x)
      (define m3 (build3 x))
      (append (JoS-sort (left m3)) (middle m3) (JoS-sort (right m3))))
    (cond
      ((null? x) ())
      (else (sort x))))

Но -- работает:
> (JoS-sort (list 7 1 10 8 2 3 15 3))
(1 2 3 3 7 8 10 15)