Язык функционального программирования Haskell Выполнила: Шатохина Е.В. ПИБ-41. - презентация

1 Язык функционального программирования Haskell Выполнила: Шатохина Е.В. ПИБ-41

2 Haskell (hæskəl) стандартизированный чистый функциональный язык программирования общего назначения. Является одним из самых распространённых языков программирования с поддержкой отложенных вычислений. Поскольку язык функциональный, то основная управляющая структура это функция. Отличительная черта языка серьёзное отношение к типизации; во многом в этой связи язык назван в честь исследователя теории типов и изобретателя комбинаторной логики Хаскелла Карри. Имеются средства взаимодействия с кодом на других языках программирования. Есть встроенная поддержка многозадачного и параллельного программирования, развитый инструментарий (средства автоматического тестирования, отладки и профилирования, в том числе для параллельных программ), существует несколько тысяч библиотек с открытым исходным кодом.

3 История языка Haskell 1960: John McCarthy, LISP – первый функциональный язык программирования 1978: John Backus, FP – система комбинаторного программирования конец 1970-х: Edinburgh univ., ML – meta-language : David Turner, Miranda – функциональный язык с «ленивыми» вычислениями начало 1930-х: Church, формализация функций в λ-исчислении 1990: Ericsson, Erlang – «коммерческий» функциональный язык 1988: Paul Hudak, Haskell – первая версия языка Haskell 1999: Haskell group, Haskell98 – «стандартная» версия языка Haskell Haskell – чисто функциональный язык программирования, названный в честь Хаскелла Карри (Haskell B. Curry – ), известного, главным образом, благодаря работам в области математической логики и комбинаторной логики в конце 1950-х – начале 1960-х годов

4 Характеристики языка. В качестве основных характеристик языка Haskell можно выделить следующие: недопустимость побочных эффектов (чистота языка); возможность писать программы с побочными эффектами без нарушения парадигмы функционального программирования с помощью монад; статическая сильная полная типизация с автоматическим выведением типов, основанная на типизации Хиндли Милнера; функции высшего порядка, в том числе лямбда-абстракции; частичное применение; ленивые вычисления (lazy evaluation); сопоставление с образцом (англ. pattern matching), функциональные образцы, охраняющие выражения (guards); параметрический полиморфизм и его объедение с ad hoc полиморфизмом в единую модель посредством классов типов; алгебраические типы данных, в том числе псевдо бесконечные (за счёт ленивости); генераторы списков (list comprehensions); возможность интеграции с программами, реализованными на императивных языках программирования посредством открытых интерфейсов (стандартное расширение языка Foreign Function Interface (англ.)

5 С момента принятия последнего стандарта языка (Haskell98) прошло много времени, и с тех пор ведущие реализации языка (ghc и hugs) были расширены множеством дополнительных возможностей: Параметрический полиморфизм высших рангов за счёт квантификации переменных типа (вплоть до импредикативного) естественно, исключающая выведение типов. Функциональные зависимости (FD, functional dependencies)

6 Типы данных и базовые конструкции языка Haskell Элементарные типы данных Integer, Int – целые значения (25, -17, ) Float, Double – вещественные значения (3.14, ) Char – символьные значения ( 'A', '*', '3' ) Bool – логические значения ( True, False ) Идентификаторы: fact, fAcToRiAl, fact_1, fact'' Знаки операций: +, -, *, <, == Идентификаторы применяются для обозначения констант – значений разных типов (простых, составных, функций) и типов. Любому идентификатору можно сопоставить тип и значение: school :: Integer school = 366 piHalf :: Double piHalf = / 2

7 Кортежи и функции Значения могут объединяться в более сложные с помощью кортежирования. Например: pair :: (Double, Double) pair = (2.7, 3.14) attributes :: (Char, (Int, Int, Int), Bool) attributes = ('M', (17, 4, 1955), True) Тип функции определяется типами аргументов и результата, например: sin :: Double -> Double -- аргумент и результат типа Double plusInt :: Int -> Int -> Int -- два аргумента типа Int, результат Int divMod :: (Int, Int) -> (Int, Int) -- аргумент и результат - кортежи Выражения составляются из констант применением операций и функций, например: result = sin ( / 4) c10 = 3 + plusInt 3 4 pair = divMod (1458, plusInt ) Операции и функции отличаются только формой записи. Следующие выражения эквивалентны: и (+) `div` 4 и div `plusInt` 11 и plusInt 7 11

8 Определение функций с помощью уравнений Уравнения задают правила, по которым происходит вычисление функции, то есть каким образом результат получается из аргументов функции, например: plusInt :: Int -> Int -> Int plusInt a b = a + b divMod :: (Int, Int) -> (Int, Int) divMod (a, b) = (a `div` b, a `mod` b) Уравнения могут содержать условные выражения и рекурсивные обращения, например: factorial :: Integer -> Integer factorial n = if n == 0 then 1 else n * (factorial (n-1)) sum :: Integer -> Integer sum n = n + if n == 0 then 0 else sum (n-1) factorial1 :: Integer -> Integer factorial1 n | n == 0 = 1 | n > 0 = n * (factorial1 (n-1)) factorial2 :: Integer -> Integer factorial2 0 = 1 factorial2 n = n * (factorial2 (n-1)) Уравнений для одной функции может быть несколько, тогда аргументы последовательно сопоставляются с образцами:

9 Подготовка и запуск программ module Test where factorial :: Integer -> Integer factorial n | n == 0 = 1 | n > 0 = n * (factorial (n-1))

10 Prelude> :l "MyProg.hs" Test> factorial :: Integer Test> Test> Пример запуска программы на исполнение factorial 25 15511210043330985984000000 :: Integer Test> Test> Пример запуска программы на исполнение">

11 Исполнение программ с помощью текстовой подстановки factorial :: Integer -> Integer factorial n | n == 0 = 1 | n > 0 = n * (factorial (n-1)) factorial 3 3 * (factorial (3-1)) 3 * (factorial 2) 3 * (2 * (factorial (2-1))) 3 * (2 * (factorial 1)) 3 * (2 * (1 * (factorial (1-1)))) 3 * (2 * (1 * (factorial 0))) 3 * (2 * (1 * 1)) 6

12 Несколько определений простых арифметических функций -- Вычисление наибольшего общего делителя двух натуральных чисел gcd :: Integer -> Integer -> Integer gcd m n | m < n = gcd n m | n < 0 = error "gcd: Wrong argument" gcd m 0 = m gcd m n = gcd n (m `mod` n) -- Проверка заданного натурального числа на простоту prime :: Integer -> Bool prime' :: Integer -> Integer -> Bool prime p | p <= 0 = error "prime: Non-positive argument" | otherwise = prime' 2 p prime' d p | d * d > p = True | p `mod` d == 0 = False | otherwise = prime' (d+1) p Bool prime' :: Integer -> Integer -> Bool prime p | p <= 0 = error "prime: Non-positive argument" | otherwise = prime' 2 p prime' d p | d * d > p = True | p `mod` d == 0 = False | otherwise = prime' (d+1) p">

13 Эффективность рекурсивных функций. -- Вычисление числа Фибоначчи, заданного порядковым номером fib :: Integer -> Integer fib 1 = 1 fib 2 = 1 fib n = fib (n-1) + fib (n-2) fib 6 fib 5 + fib 4 (fib 4 + fib 3) + fib 4 ((fib 3 + fib 2) + fib 3) + fib 4 (((fib 2 + fib 1) + fib 2) + fib 3) + fib 4 (((1 + 1) + 1) + (fib 2 + fib 1)) + fib 4 (3 + 2) + (fib 3 + fib 2) (3 + 2) + ((fib 2 + fib 1) + 1) (3 + 2) + ((1 + 1) + 1) 8 f 1 = f 2 = 1 f n = f n-1 + f n-2 при n > 2

14 Эффективность рекурсивных функций. Концевая рекурсия. fib :: Integer -> Integer fib' :: Integer -> Integer -> Integer -> Integer -> Integer fib' n k fk fk1 | k == n = fk | k < n = fib' n (k+1) (fk+fk1) fk fib 1 = 1 fib n = fib' n fib 6 fib' fib' fib' fib' fib' factorial :: Integer -> Integer factorial 0 = 1 factorial n = n * factorial (n-1) factorial :: Integer -> Integer factorial' :: Integer -> Integer -> Integer factorial n = factorial' n 1 -- (factorial' n f) == (f * n!) factorial' n f | n == 0 = f | n > 0 = factorial' (n-1) (n*f)

15 Спасибо за внимание