Функциональные языки программирования: LISP (Scheme/Racket) + Haskell. Использование рекурсии для решения задач
Функциональное программирование — раздел дискретной математики и парадигма программирования, в которой процесс вычисления трактуется как вычисление значений функций в математическом понимании (в отличие от функций как подпрограмм в процедурном программировании). У функции в математике есть аргументы и результат, она не меняет состояние остальной программы (отсутствуют побочные эффекты).
Противопоставляется парадигме императивного программирования, которая описывает процесс вычислений как последовательное изменение состояний (как в теории автоматов).
Функциональное программирование предлагает обходиться вычислением результатов функций от исходных данных и результатов других функций, и не предполагает явного хранения состояния программы. Соответственно, не предполагает оно и изменяемость этого состояния (в отличие от императивного, где одной из базовых концепций является переменная, хранящая своё значение и позволяющая менять его по мере выполнения алгоритма).
Сильная (строгая) и слабая типизация
Слабая типизация - операции приведения типов. Строгая - надо явно приводить тип.
Статическая типизация - все типы известны на этапе компиляции.
Динамическая типизация - переменная может менять тип в процессе выполнения программы, на этапе компиляции типы неизвестны.
Сформулированная Джоном Мак-Карти (1958) концепция символьной обработки информации компьютером восходит к идеям Черча и других математиков, известным как лямбда-исчисление с конца 20-х годов XX века.
Выбирая лямбда-исчисление как теоретическую модель, Мак-Карти предложил рассматривать функции как общее базовое понятие, к которому достаточно естественно могут быть сведены все другие понятия, возникающие при программировании.
Существуют различия в понимании функции в математике и функции в программировании, вследствие чего нельзя отнести Си-подобные языки к функциональным, использующим менее строгое понятие. Функция в математике не может изменить вызывающее её окружение и запомнить результаты своей работы, а только предоставляет результат вычисления функции.
Программирование с использованием математического понятия функции вызывает некоторые трудности, поэтому функциональные языки, в той или иной степени предоставляют и императивные возможности, что ухудшает дизайн программы (например возможность безболезненных дальнейших изменений).
Дополнительное отличие от императивных языков программирования заключается в декларативности описаний функций. Тексты программ на функциональных языках программирования описывают «как решить задачу», но не предписывают последовательность действий для решения.
Первым функциональным языком стал Лисп. Он был предложен Джоном Мак-Карти в качестве средства исследования границ применимости компьютеров, в частности, методом решения задач искусственного интеллекта.
Вариант данного языка широко используется в системе автоматизированного проектирования AutoCAD и называется AutoLISP
Основные преимущества функциональных языков:
Краткость и простота
Программы на функциональных языках обычно намного короче и проще, чем те же самые программы на императивных
языках.
Пример (быстрая сортировка Хоара на абстрактном функциональном языке):
quickSort ([]) = [] quickSort ([h : t]) = quickSort ([n | n ∈ t, n <= h) + [h] + quickSort ([n | n ∈ t, n > h])
Строгая типизация
В функциональных языках большая часть ошибок может быть исправлена на стадии компиляции, поэтому стадия отладки и общее время разработки программ сокращаются. Вдобавок к этому строгая типизация позволяет компилятору генерировать более эффективный код и тем самым ускорять выполнение программ.
Модульность
Механизм модульности позволяет разделять программы на несколько сравнительно независимых частей (модулей) с чётко определёнными связями между ними. Тем самым облегчается процесс проектирования и последующей поддержки больших программных систем. Поддержка модульности не является свойством именно функциональных языков программирования, однако поддерживается большинством таких языков.
Функции — объекты вычисления
В функциональных языках (равно как и вообще в языках программирования и математике) функции могут быть переданы другим функциям в качестве аргумента или возвращены в качестве результата. Функции, принимающие функциональные аргументы, называются функциями высших порядков или функционалами.
Чистота (нет побочных эффектов)
В чистом функциональном программировании оператор присваивания отсутствует, объекты нельзя изменять и уничтожать, можно только создавать новые путем декомпозиции и синтеза существующих. О ненужных объектах позаботится встроенный в язык сборщик мусора. Благодаря этому в чистых функциональных языках все функции свободны от побочных эффектов.
Отложенные (ленивые) вычисления
В императивных языках программирования (например, C++) вызов функции приводит к вычислению всех аргументов. Этот метод вызова функции называется вызов-по-значению. Если какой-либо аргумент не использовался в функции, то результат вычислений пропадает, следовательно, вычисления были произведены впустую. Противоположностью вызова-по-значению является вызов-по-необходимости (ленивые вычисления). В этом случае аргумент вычисляется, только если он нужен для вычисления результата.
LISP
Скачивание и установка
Скачать Racket: http://racket-lang.org
Программы и данные неотличимы друг от друга — всё есть списки.
Программа на языке LISP — список. Первый элемент списка — имя функции которую надо вызвать, остальные — аргументы.
(действие аргумент1 аргумент2 ...)
Сначала вычисляются аргументы.
Функция list конструирует список:
(list 1 2 3)
Условный оператор (больше похож на тернарный)
(if условия если_верно если_нет)
Объявление функции
(define (имя_функции арг1 арг2) (код))
Объявление константы
(define pi 3.14)
Литералы списков:
'()
'(2 3 4)
Конструирование списка из головы и конца:
(cons head tail)
Голова списка
(car L)
Хвост списка
(cdr L)
Разберем и построим снова список L:
(cons (car L) (cdr L))
Арифметические функции: + - * /
null? — пуст ли список?
Вычисление длины списка
(define (length L)
(if (null? L)
0
(+ 1
(length (cdr L))
(
)
)
Получить элемент списка L с номером n
(define (get L n)
(if (= n 0)
(car L)
(get (cdr L) (- n 1))
)
)
Факториал
(define (fact n)
(if (= n 0)
1
(* n (fact (- n 1)))
)
)
Применить одну операцию ко всем элементам списка
(define (map F L)
(if (null? ()
'()
(cons (F (car L) (map F (cdr ())))
)
)
(display ... out) — вывод на экран
(read in) — чтение
(close-output-port out) — закрытие файла (нужно при работе в среде разработки)
Тексты программ на функциональных языках программирования описывают «как решить задачу», но не предписывают последовательность действий для решения.
Первым спроектированным функциональным языком стал Лисп.
Лисп/LISP (LISt Processing language - «язык обработки списков») — семейство ЯП, программы и данные в которых представляются системой вложенных списков.
Лисп является вторым в истории (после Фортрана) используемым по сей день высокоуровневым языком программирования.
http://ru.wikipedia.org/wiki/Лисп
Haskell
Haskell (Хаскель, Хаскелл) - стандартизованный чистый функциональный ЯП общего назначения (один из самых распространённых с поддержкой отложенных/ленивых вычислений). Типизация строгая, статическая, с автоматическим выводом типов.
Концепция языка отражает идею математика Хаскелла Карри, писавшего, что «доказательство — это программа, а доказываемая формула — это тип программы». Именно в честь Х. Карри язык и получил своё название.
Решение задач на LISP
#lang racket ;; Демонстрация стандартных функций LISP ;; display вывод на экран (display "Это LISP :) ") (display "Тут можно складывать сразу много чисел: ") ;; Первый параметр списка - функция, остальные - аргументы (+ 1 2 4 -10) (display " ..и умножать тоже... ") (* 2 3 4) (display ".. вычитаем из первого аргумента все остальные..") (- 10 5 5) (display ".. делим первый аргумент на все остальные..") (/ 1 2 3) (display "Остаток от деления 5 на 3: ") (remainder 5 3) (display "Логические операции: ") (display "Логическое И: ") (and #f #f) (and #f #t) (and #t #f) (and #t #t) (display "Логическое ИЛИ: ") (newline) (or #f #f) (or #f #t) (or #t #f) (or #t #t) (display "Сравнение (операция равно): ") (eq? 2 1) (display "Не равно: ") (not (eq? 2 1))
Наибольший общий делитель
#lang racket ; Открываем входной файл как in (define in (open-input-file "gcd.in")) ; Открываем выходной файл как out, перезаписываем его если он уже есть (define out (open-output-file "gcd.out" #:exists 'replace)) ; Функция gcd, если y равен нулю, то возвращает x, ; иначе вызывает саму себя с параметрами y и остаток от деления x на y (define (gcd x y) (if (zero? y) x (gcd y (remainder x y)))) ; Считываем два числа из входного файла, передаём их на вход функции gcd и выводим в выходной файл ответ (display (gcd (read in) (read in)) out) ; Сбрасываем буфер вывода (flush-output out)
Разворот списка
#lang racket
(define (R L)
(if (null? L) ;; Если список пустой,
L ;; то возвращаем его же
(append (R (cdr L)) ;; переворачиваем конец
(list (car L))
)
)
)
;; Тесты
(R '())
(R '(1))
(R '(1 2)) ;; '(2 1)
(R '(1 2 3))
(R '(234 34 2 3))
Скобки
#lang racket
;; Открывающая скобка
(define (openBracket x)
(or (eq? x #\() (eq? x #\[) (eq? x #\{)))
;; Закрывающая скобка
(define (closeBracket x)
(or (eq? x #\)) (eq? x #\]) (eq? x #\})))
;; Правильная закрывающая скобка
(define (match open close)
(or (and (eq? open #\() (eq? close #\)))
(and (eq? open #\[) (eq? close #\]))
(and (eq? open #\{) (eq? close #\}))
)
)
(define (check L s)
(if (null? L)
(null? s)
(if (openBracket (car L)) ;; Открывающая скобка
(check (cdr L) (cons (car L) s))
(if (closeBracket (car L))
(if (null? s)
#f ;; Пустой стек
(and (match (car s) (car L)) ;; На вершине стека должна быть нужная скобка => продолжаем
(check (cdr L) (cdr s)) ;; И дальше всё в порядке
)
)
#f ;; Неверный символ
)
)
)
)
(define (checkStr s)
(check (string->list s) '()))
;; Тесты
(checkStr "")
(checkStr "()")
(checkStr "(())")
(checkStr "([])")
(checkStr "([{}])")
(checkStr "(]")
(checkStr "(()")
Быстрое возведение в степень
#lang racket
;; a в степени b
(define (pow a b)
(if (eq? b 0)
1 ;; a^0 = 1
(if(eq? (remainder b 2) 0) ;; Если b - чётная
(* (pow a (/ b 2)) ;; то делим степень на 2
(pow a (/ b 2))
)
(* a (pow a (- b 1)))
)
)
)
(pow 2 0)
(pow 2 1)
(pow 2 2)
(pow 2 3)
Обратная польская нотация
#lang racket
; Открываем входной файл как in
(define in(open-input-file"rpn.in"))
; Открываем выходной файл как out, перезаписываем его если он уже есть
(define out(open-output-file"rpn.out"#:exists 'replace))
; Выполнение операции
(define (do f e s operation)
(f
(cdr e)
(cons (operation (car (cdr s)) (car s)) (cdr (cdr s)))))
; Функция f: e - оставшаяся часть выражения, s - стек
(define (f e s)
(if(null? e)
(car s)
(if(eq? (car e) '+) (do f e s +)
(if(eq? (car e) '-) (do f e s -)
(if(eq? (car e) '*) (do f e s *)
(if(eq? (car e) '/) (do f e s /)
(f (cdr e) (cons (car e) s)))
)))))
; Считываем из входного файла, подаём на вход функции f и выводим результат в выходной файл
(display (f (read in) '()) out)
; Сбрасываем буфер вывода
(flush-output out)
#lang racket ; Открываем входной файл как in (define in(open-input-file"rpn.in")) ; Открываем выходной файл как out, перезаписываем его если он уже есть (define out(open-output-file"rpn.out"#:exists 'replace)) ; Выполнение операции (define (do f e s operation) (f (cdr e) (cons (operation (car (cdr s)) (car s)) (cdr (cdr s))))) ; Функция f: e - оставшаяся часть выражения, s - стек (define (f e s) (if(null? e) (car s) (if(eq? (car e) '+) (do f e s +) (if(eq? (car e) '-) (do f e s -) (if(eq? (car e) '*) (do f e s *) (if(eq? (car e) '/) (do f e s /) (f (cdr e) (cons (car e) s))) ))))) ; Считываем из входного файла, подаём на вход функции f и выводим результат в выходной файл (display (f (read in) '()) out) ; Сбрасываем буфер вывода (flush-output out)