Функціональне програмування на haskell частина 1
Олексій скажений. технічний письменник, незалежний фахівець
імперативне програмування
Найбільш поширені імперативні мови. в яких обчислення зводиться до послідовного виконання інструкцій. Рішення завдання на імперативний мовою зводиться до опису того, що необхідно зробити, щоб отримати результат. Класичні приклади - FORTRAN (1957), ALGOL (1958) і C (1972).
Імперативні мови близькі до архітектури фон Неймана. У них вагому частину коду займають присвоювання значень змінним.
Змінні розглядаються як змінюються в часі осередки пам'яті. Поточні значення змінних в програмі утворюють змінюється стан.
Приклад імперативного коду - процедура для обчислення факторіала на C:
Тут повторення операції множення виражено через цикл. У процесі обчислення змінюються значення змінних x і n.
Функціональні мови відносяться до декларативних - в них програма точно формулює необхідний результат обчислень в термінах залежностей функцій один від одного, а подробиці обчислення (наприклад, як саме значення повинні розміщуватися в пам'яті і пересилатися) лягають на плечі реалізації мови.
Функції та функціональність
У математичному сенсі функція f. X → Y - це правило, що зіставляють елементу x з множини X (області) елемент y = f x з безлічі Y (кообласть).
Малюнок 1. Функція f. X → Y
Важливо, щоб функція була правильно визначена, т. Е. Щодо її значення для кожного аргументу не повинно виникати неоднозначності.
Якщо значення визначено для всіх елементів області, то функція називається усюди певної; в іншому випадку вона називається часткової.
Як і в математиці, в цікавлять нас функціональних мовах не існує осередків, що зберігають різні значення. Змінні є просто іменами значень.
Зазвичай для завдання функції в функціональній мові використовуються рівняння. наприклад,
n - формальний аргумент функції fac. У правій частині після знака = описано, що функція робить зі своїм аргументом. Базові функції для множення і віднімання записані через інфіксне (вказуються між аргументами) оператори * і -.
Тут рівнянь два. При обчисленні функції рівняння проглядаються по порядку. Якщо n = 0, то буде використано перше рівняння. Якщо n ≠ 0, то воно не підійде, і задіюється друге.
Зверніть увагу: аргументи функції перераховуються навпроти її імені через пробіл. Це зручно, тому що застосування функції дуже часто зустрічається в функціональних програмах (таблиця 1).
Далі ми будемо приділяти основну увагу синтаксису і семантиці мови Haskell.
Запис в математиці
Запис в Haskell
Таблиця 1. Запис застосування функції в математиці і в Haskell
Рівняння для fac складають точне визначення функції, а не послідовність дій по обчисленню, як це було в імперативний коді.
Використовується рекурсія, т. Е. Fac визначається через саму себе. Таке визначення працює, тому що fac виражається через більш простий випадок і, в кінцевому рахунку (якщо n ≥ 0), доходить до базового випадку n = 0. Обчислення fac 3 за таким визначенням можна зробити так (на кожному кроці підкреслені спрощує вирази):
Тут ми застосували f до значення 3. При цьому 3 називається фактичним аргументом.
Функціональний підхід зосереджений на обчисленні виразів, а не на виконанні команд. Фактично, функціональна програма - це вираз, і її виконання відповідає обчисленню вираження.
При обчисленні ми переписуємо вираження, підставляючи значення замість змінних і застосовуючи функції, поки не буде отримано остаточний результат.
Зверніть увагу, що для n <0 наше определение будет вычисляться бесконечно, поэтому наша функция является частичной (если ее областью считать все целые числа).
Тепер запишемо функцію, яка обчислює для цілих k і речових r біноміальний коефіцієнт
При k ≥ 0 ми маємо вираз, де в знаменнику стоїть тільки що певний факторіал числа k, а в чисельнику - спадна факторіальна ступінь (falling factorial power)
Запишемо для неї рекурсивне визначення:
У першому рівнянні r не використовується, тому можна використовувати замінник _ і писати ffp _ 0 = 1.
Можна переконатися, що
(перевірте це). Тому рівняння факторіала можна замінити на
Як тільки ми записали рівняння функції ffp. її можна розглядати як абстрактний чорний ящик з двома входами і одним виходом не піклуючись про те, що саме відбувається всередині. Все, що для нас тепер важливо, - це коректне відображення входів в вихід.
Малюнок 2. Чорний ящик, який обчислює спадну факторіальною ступінь
Візьмемо ще один чорний ящик (/) з двома входами x і y і виходом, рівним приватному x / y:
буде обчислювати така схема:
Малюнок 3. Схема з чорних ящиків, що обчислює біноміальний коефіцієнт
Вона відповідає виразу
Визначимо шукану функцію:
binc тепер теж можна вважати абстрактним чорним ящиком і застосовувати у визначенні інших функцій.
Приклад обчислення binc 6 2:
Коли ми з'єднували чорні ящики, ми мали на увазі, що вони, по-перше, завжди дають однаковий результат для одних і тих же входів і, по-друге, не впливають на роботу інших ящиків.
Це призводить до важливого поняття чистоти.
При виклику процедури в імперативний мовою ми часто не тільки передаємо їй аргументи і отримуємо результат, але очікуємо побічний ефект - щось, не пов'язане з переведенням аргументів на яке значення (висновок даних в файл, зміна глобальної змінної, і т.д.). На жаль, побічні ефекти часто виявляються, навіть якщо це не передбачено.
Якщо функція має побічні ефекти, то її обчислення з одними і тими ж аргументами в різному контексті може давати різні результати.
Якщо побічних ефектів багато, то програмування ускладнюється, в коді виникає більше помилок, і його коректність стає важко перевірити як формальними, так і неформальними засобами.
Тут ми не назвали процедуру функцією, тому що при наявності побічних ефектів процедура не схожа на функцію в математичному сенсі (іноді такі функції називають чистими).
Кожен вираз в функціональній мові відповідає своїм значенням; обчислення тільки модифікує вираз, але на значення не впливає.
Програмування без побічних ефектів може повністю розглядатися з боку застосування функцій до аргументів.
Мова без побічних ефектів називається чисто функціональним.
Такі мови, як ML і Scheme, в цілому є функціональними по стилю, проте допускають як привласнення, так і побічні ефекти.
Спочатку може здатися, що чисто функціональна мова непрактичний, але це далеко не так - для успішного програмування потрібно просто ознайомитися з деякими простими і елегантними ідеями (а також забути про старі звички).
Ліниво і нестрогість
При виконанні функції за значенням її аргументи спочатку обчислюються, а потім в тіло функції передаються отримані значення. Коли Ви телефонуєте по необхідності аргументи передаються невичісленнимі і обчислюються в тілі функції, тільки якщо це знадобиться.
Приблизно цьому відповідає те, що в функціональних мовах називається енергійним і ледачим обчисленням. У енергійному випадку обчислюється все, що можна, а в ледачому - все, що потрібно. (Ми відкладемо формальний підхід до цього питання до тих пір, поки не буде з'ясовано, яка модель обчислень лежить в основі функціональних мов.)
Функція називається суворої по одному зі своїх аргументів, якщо завжди вимагає його значення для отримання результату. Якщо значення потрібно не завжди, то функція називається нестрогой з цього аргументу.
Наприклад, наша функція binc завжди буде вимагати значення k. але значення r потрібно, тільки якщо k ≥ 0.
Відповідно до цього, кажуть про мови з суворою семантикою і мовами з нестрогой семантикою. ( «Нестрогие» і «ліниво» - не однакові, але близькі поняття.)
Строгий мову обчислює аргументи, перш ніж застосовувати функцію. Таким чином, якщо обчислення виразу e не закінчується (зациклюється або зупиняється з помилкою), то застосування функції f e також не вирахує.
У нестрогому мовою обчислення проводиться за потребою. Якщо f нестрогая, то обчислення f e може завершитися, навіть якщо обчислення e не закінчується.
позначає список з трьох елементів. Обчислення fac (-1) зациклюється. Значить, обчислення списку також зациклиться.
Нехай тепер функція length повертає довжину списку. вираз
НЕ буде обчислено в строгому мовою, але в нестрогому результатом буде 3. тому що для підрахунку елементів їх значення не потрібні.
Приклади нестрогих мов: Miranda і Haskell. Суворі мови - ML і Scheme.
Питання строгості досить тонкий, і його не можна звести до простого «Що зручніше і ефективніше?»> Передача відкладених обчислень замість значень в ході виклику функції пов'язана з певними витратами. Разом з тим у багатьох ситуаціях ліниво дозволяє економити на обчисленнях або записувати такі вирази, які б не вирахували або обчислювалися б нескінченно в енергійному мовою.
Нестрогість є незалежною характеристикою по відношенню до чистоти, хоча багато в чому допомагає мови утримуватися від побічних ефектів.
коротка історія
Одними з перших мов з функціональним стилем були LISP (1958), APL (1964), ISWIM (1966) і FP (1977).
До кінця 1980-х років уже було багато функціональних мов. Серед тих, які мали значний вплив на Haskell:
- ML (1973) - перша мова з типізацією Хиндли-Мілнера.
- SASL. KRC. Miranda (1972-1985) - одні з перших ледачих мов.
- Hope (1980) - один з перших мов з алгебраїчними типами даних. Haskell розроблявся численною групою дослідників з 1987 р Він названий на честь Хаскелл Каррі.
Малюнок 4. Походження Haskell
Основне завдання, на якій було зосереджено проектування - Haskell повинен був зібрати наявні напрацювання в області нестрогих чисто функціональних мов.
Нововведення Haskell - монади і класи типів. Інші сильні сторони, запозичені з інших мов - каррінг, алгебраїчні типи даних, зіставлення зі зразком. (Тут ми просто наводимо набір ключових слів, і всі ці поняття скоро будуть роз'яснені.)
Останнє зафіксоване опис - Haskell 98, проте мова постійно розвивається і ускладнюється; Зараз планується вихід Haskell '.
Haskell став найпопулярнішим нестрогим чисто функціональним мовою. На Haskell реалізовано багато складних проектів:
- Компілятори та інші засоби розробки.
- Розподілена система управління версіями Darcs.
- Віконний менеджер xmonad.
- Сервер Web-додатків HAppS.
- Інтерпретатор / компілятор Pugs для мови Perl 6.
- Операційна система House.
- Мова опису апаратних засобів Lava.
- Система обробки натурального мови LOLITA.
- Системи доведення теорем Equinox / Paradox і Agda.
Основні джерела інформації по Haskell
У Haskell є широке і доброзичливе співтовариство.
Основне джерело інформації - сервер haskell.org.
На ньому є списки розсилки, в тому числі:
- [email protected] - вільне обговорення.
- [email protected] - більш прості теми для новачків.
Є дуже жвавий IRC-канал #haskell на irc.freenode.net. У ньому можна швидко отримати люб'язний відповідь практично на будь-яке питання.
Редагування і виконання коду
реалізації Haskell
Формально, Haskell не має якоїсь однієї «стандартної» реалізації.
Для інтерактивної роботи підійде легкий інтерпретатор Hugs.
Також є цікавий проект Yhc. компілює вихідні тексти в байткод, і Helium - навчальний варіант Haskell, дружній до новачків (наприклад, видає більш ясні повідомлення про помилки). Однак вони ще знаходяться в процесі розробки.
Де-факто стандартним став компілятор / інтерпретатор GHC. Він є найбільш просунутим, в усьому відповідає стандарту і пропонує ряд експериментальних розширень. Ми сконцентруємося на ньому.
Нас в першу чергу буде цікавити інтерактивна програма ghci, в якій зручно відчувати навчальні приклади.
Отже, після установки GHC ви можете запустити в терміналі ghci:
Тут Prelude - це назва завантаженого модуля. В Prelude містяться основні визначення, і він завжди задіюється за замовчуванням. Вивчаючи або переписуючи самостійно код Prelude, початківці можуть дізнатися багато нового. (Ми з вами теж почасти будемо це робити.)
Символ> означає, що ghci очікує користувача введення. Це можуть бути вирази Haskell, а також команди для інтерпретатора.
Клавішами ← і → можна переміщати курсор по командному рядку ghci. ↑ і ↓ прокрутити історію команд назад і вперед.
Замість Prelude> або інших імен модулів ми далі будемо писати ghci> (якщо хочете зробити так само, виконайте в ghci команду: set prompt "ghci>").
Для початку ghci можна використовувати як просунутий калькулятор:
Оператори збігаються з прийнятими в інших мовах (таблиця 2).
Таблиця 2. Арифметичні оператори з Prelude
Для них використовується інфіксне запис і відповідний пріоритет. Наприклад, 2 * 3 + 4 відповідає (2 * 3) +4. а 2 ^ 3 ^ 4 - 2 ^ (3 ^ 4). Щоб змінити прийнятий пріоритет, можна розставити дужки.
У ghci є спеціальна змінна it. рівна значенню останнього успішно обчисленого виразу.
Редагування вихідного коду
Для коду Haskell використовується розширення файлів .hs.
Якщо ви запишете код на Haskell в файл foo.hs. то визначення завантажуються в ghci командою: load foo. Паралельно файл можна редагувати і при необхідності перезавантажувати визначення за допомогою: reload.
Поточна директорія змінюється командою: cd (наприклад. Cd / home / bob).
Ви можете завантажити додається до статті вихідний код і обчислити вирази:
Ці та інші команди можна скорочувати - замість: load використовувати: l. замість: reload -: r і так далі.
Список команд інтерпретатора виводить: help. Для виходу з ghci потрібно набрати: quit.
В ході нашого викладу часто будуть зустрічатися прості приклади, що складаються з одного-двох рівнянь. Їх можна відразу вводити в ghci за допомогою let:
Якщо рівнянь кілька, то їх потрібно укласти в фігурні дужки і розділити крапкою з комою (в одній з наступних статей ми докладно розглянемо такий запис).