Функциональное программирование |
Функциональное программирование всегда привлекало меня в противопоставлении к императивному.
Я очень часто обсуждаю различные аспекты функционального программирования на различных ветках на Базарной площади.
Но хотелось бы собрать всех заинтересованный этой темой в одной ветке.
Я думаю что настало время открыть такую тему. И вот почему.
Исторически функциональное программирование появилось практически вместе с императивным.
Вторым языком после фортрана был лисп.
Но увы, функциональное программирование надолго было уделом исследовательских институтов или специализированных приложений (Искусственный Интеллект)
Конечно не надо считать весь мир дураками из за того что развитие пошло по пути языков Алгол семейства.
Для этого были вполне обьективные причины. Функциональные языки слишком близки к человеку и слишком далеки от машины.
Они сьедают в десятки раз больше рессурсов чем императивные языки.
Вспомните претензии, предявляемые к java - первому императивному языку с виртуальной машиной и сборщиком мусора, толкаемому большими корпорациями в mainstream.
Жутко тормозит, и жрет всю память какая есть. А ведь функциональные языки (далее ФЯ) все без иключения имеют сборщик мусора, виртуальную машину.
Многие из них (семейство лисп) еще и динамические, что только усугубляет положение.
Вполне естественно что появившись более полусотни лет назад они надолго опередилли свое время.
Для широкого распространения ФЯ нужны гигабайты дешевой памяти и гигагерцы дешевых процессоров.
Прошло более 50 лет, прежде чем такие требования к железу стали реальностью.
Это время наступило. СЕЙЧАС.
Добро пожаловать в новую эру программирования.
Jack Of Shadows
Всего в теме 5502 сообщения
Добавить свое сообщение
Отслеживать это обсуждение
- Средства разработки. Языки программирования.
- Delphi 4 or Delphi 5
- Что приобрести в качестве средства разработки?
- Delphi6
- Delphi vs PowerBuilder
- Сравнение компиляторов
- Вот и вышла Delphi 7... Вы рады?
№ 2032 25-02-2007 11:44 | |
Ответ на »сообщение 2031« (Geniepro)
___________________________
>>>А вот теперь Вам спасибо за хорошую ссылку! ;о)
Я рад, если эта книга показалась Вам заслуживающей внимания.
Такой момент: литературу по ФП откапываю только в Интернете, в бумажном виде -- ничего.
Точнее, почти ничего, т.к. неожиданно для себя выяснил что в классическом учебнике "Информатика" Бауэра и Гооза 2-я глава ("Основные понятия программирования") посвящена именно ФП (просто там не употребляется это словосочетание; уже потом, в 3-й главе речь заходит о машинно-ориентированных языках программирования).
Например, раздел 2.4 называется "О технике рекурсивного программирования".
>>>Осталось только осилить эти 686 страниц... :о))
Аналогично. :)
К сожалению, времени постоянно не хватает. :(
Поэтому и пытаюсь при случае продвигаться вперед "большими рывками" -- иначе не получается.
№ 2031 25-02-2007 05:42 | |
№ 2030 25-02-2007 03:24 | |
Заинтересовавшись Схемой (причина, как и в Обероне, -- не надо мучиться с "увесистым" синтаксисом), откопал в интернете электронную книгу "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").
Возможно, кого-то заинтересует.
№ 2029 25-02-2007 02:50 | |
Я тут несколько увлекся "публикацией" своего ученического кода на Схеме. :)
Немного поясню, почему я это делаю.
Во-первых, возымели действие призывы "функциональщиков" Jack of Shadows и Geniepro, и я решился-таки заняться ФП хотя бы в небольшом объеме.
Обсуждая код, я надеюсь продвигаться в обучении быстрее.
Во-вторых, в последнее время было много споров между "оберонщиками" и "функциональщиками", иногда исключительно "метафизические".
Мое убеждение, что в спорных вопросах программисты должны иметь возможность общаться на уровне кода. Иначе так и будем препираться без толку (в то время как и причины-то, возможно, нет).
Т.к. присутствующие на форуме функциональщики пишут на ИЯ, а многие оберонщики (за явным исключением Trurl) не пишут на ФЯ, то решил немного "выровнять ситуацию". :)
№ 2028 24-02-2007 20:50 | |
Ответ на »сообщение 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
№ 2027 24-02-2007 20:27 | |
Ответ на »сообщение 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
№ 2026 24-02-2007 20:12 | |
Ответ на »сообщение 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) () ())))
№ 2025 24-02-2007 17:18 | |
Ответ на »сообщение 2024« (Jack Of Shadows)
___________________________
>>>Я даже не понял че вы там написали :)) Разбираться надо.
Как говорится, знай наших! :)
Конечно, код можно написать гораздо лучше; просто немного тяжко с непривычки.
№ 2024 24-02-2007 16:52 | |
Ответ на »сообщение 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))
№ 2023 24-02-2007 14:09 | |
Ответ на »сообщение 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)
Добавить свое сообщение
Отслеживать это обсуждение
Дополнительная навигация: |
|