Функционално програмиране в Haskell част 1
Алексей Beshenov. технически писател, независим специалист
наложително програмиране
Най-често срещаните императивни езици. в който изчисляването намалява към серийния изпълнение на инструкции. Решение за наложително език се свежда до описание на това какво трябва да се направи, за да получите резултат. Класическите примери - FORTRAN (1957), АЛГОЛ (1958) и С (1972).
Наложителни езици са близки до архитектурата на фон Нойман. Те заемат значителен дял от код зададат стойности на съответните променливи.
Променливи се третират като променливи във времето на паметта. Текущите стойности на променливи в програмата се променя държавата.
Пример наложително код - процедурата за факториел в C:
Тук повторение на умножение изразена по отношение на цикъла. В процеса на изчисляване на промяна на стойности на х и п променливи.
Функционални езици са декларативни - в тяхната програма точно формулира необходима в резултат на изчислението по отношение на зависимостта от функциите на един с друг, и подробности за изчисляване (например как стойността трябва да бъде поставен в паметта и се изпраща) са за сметка на езика на изпълнението.
Характеристики и функционалност
В математическия смисъл на думата, на функцията F. X → Y - обикновено свързва с елемент X от набор X (област), на елемент у = е х от множество Y (codomain).
Фигура 1. F функцията. X → Y
Важно е, че функцията е била правилно определена, т.е.. Д. В сравнение с нейната стойност за всеки аргумент трябва да бъде не двусмислие.
Ако стойностите са определени за всички елементи на терена, а след това на функцията се нарича навсякъде е определено; в противен случай той се нарича частичен.
Както в областта на математиката, ние се интересуваме от функционални езици не съществуват клетки, които притежават различни стойности. Променливите са просто имена на ценности.
Обикновено работните функции в функционален език, използвани уравнение. Например,
п - официална функция аргумент фак. От дясната страна след знака = обяснява, че функцията прави с неговия аргумент. Основни функции за умножение и изваждане са написани през инфикса (както е посочено между аргументите) оператори * и -.
Има две уравнения. При изчисляване на функцията на уравнението се разглеждат в последователност. Ако п = 0, се използва първото уравнение. Ако н ≠ 0, а след това няма да стане, и активира втората.
Забележка: Функцията аргументи са изброени до името му с интервал. Това е удобно, защото използването на функцията е много често при функционални програми (Таблица 1).
След това, ние ще се съсредоточи върху синтаксиса и семантиката на Haskell.
Писане по математика
Писане в Haskell
Таблица 1. Запис функция приложение в областта на математиката и В Haskell
Уравнения за фак е, а не определена функция за поредица от действия върху изчислението, тъй като тя е наложително код.
Тя използва рекурсия, т. Е. Fac определя по себе си. Това определение работи, защото FAC изразена по отношение на опростена случай и в крайна сметка (ако п ≥ 0), достигне базовата случай п = 0. изчисляване на FAC 3 до такова определяне може да бъде направено както следва (за всяка стъпка е опростена изрази са подчертани):
Тук са подали молби за стойността на е 3. Този 3 нарича действителна аргумент.
Функционален подход се фокусира върху оценка изрази, а не изпълнение на команди. В действителност, функционална програма - този израз, и прилагането на съответното изчисление израз.
При изчисляване, ние пренапише израз, заместване на стойностите за променливите и прилагане на функцията до краен резултат.
Имайте предвид, че за п <0 наше определение будет вычисляться бесконечно, поэтому наша функция является частичной (если ее областью считать все целые числа).
Сега пиша функция, която изчислява за к число и недвижими Биномен коефициент R
Ако к ≥ 0, имаме израз, когато знаменателят е, че само определен брой к факториел, а числителят - факториел намаляващото ниво (падане факторен мощност)
Пишем за нея рекурсивно определение:
През първото уравнение, R не се използва, така че можете да използвате заместител _ _ и пишат FFP 0 = 1.
Можем да видим, че
(Вижте го). Поради това уравнение може да се замени с факторен
След като сме записали FFP функция уравнение. то може да се разглежда като абстрактно черна кутия с два входа и един изход не се притеснявате за това, което става вътре. Всичко, което сега е важно за нас - това е правилното представяне на входа на изхода.
Фигура 2. черна кутия, която изчислява степента на намаляване на факториален
Вземете друга черна кутия (/) с два входа х и у и добива на частния X / Y:
ще изчисли такава схема:
Фигура 3. Диаграма на черната кутия, за да изчисли коефициента биномиално
Това съответства на експресията
Определяне на желаната функция:
binc сега също може да се разглежда абстрактно черна кутия и се прилагат при определяне на други функции.
Пример изчисляване binc 06 февруари:
Когато сме свързани черната кутия, имаме предвид, че те са, на първо място, винаги дават един и същ резултат за едни и същи ресурси, а от друга, не се отразява на работата на други кутии.
Това води до важна идеята за чистота.
Когато се обадите на процедура в императив език, ние често не просто да го давате на аргументите и да получите резултата, но ние очакваме страничен ефект - нещо, което не е свързано с прехвърлянето на аргументи в обратната стойност (изходни данни към файл, променете глобална променлива, и т.н.). За съжаление, често се появяват странични ефекти, дори и ако това не е предвидено.
Ако функцията има странични ефекти, нейното изчисляване със същите аргументи в различен контекст може да даде различни резултати.
Ако страничните ефекти са много, по-сложно програмиране код има повече грешки и става трудно да се провери коректността на официалните и неофициални средства.
Тук не се обади процедура функция, тъй като наличието на странични ефекти на процедурата не е подобно на функцията в математическия смисъл на думата (понякога наричан чисти функции като).
Всяка експресия в функционален език съответства на стойността; изчисление променя само израз, но стойността не е засегната.
Програмиране без странични ефекти могат да бъдат изцяло разгледани чрез прилагане на функции за аргументи.
Език без странични ефекти казва, че е чисто функционален.
Езици като ML и схема, обикновено са функционални в стил, но дава възможност както за прехвърляне и странични ефекти.
На пръв поглед може да изглежда, че чисто функционален език не е практично, но това не е така - за успешното програмиране просто трябва да прочетете някои прости и елегантни идеи (както и да забравите за старите навици).
Мързелът и липсата на взискателност
При обаждане своя първи аргумент изчислява от стойността на функция, и след това се прехвърля в стойностите на функцията на тялото получени. Когато се обадите аргументите на необходимост преминали unevaluated и изчислена в тялото на функция, само ако е необходимо.
Приблизително, това съответства на факта, че в функционални езици се нарича един енергичен и мързелив оценка. В случай на силно изчислява всичко, което е възможно, и по-мързеливи - всичко, което е необходимо. (Ние отложи официално подход към този проблем, стига да се обясни това, което е в моделните изчисления въз основа на функционални езици.)
Функцията се нарича строго един от аргументите си, ако стойността му винаги се изисква, за да се получи резултат. Ако не винаги се изисква стойността, функцията се нарича небрежна към този аргумент.
Например, нашата функция binc винаги ще изисква стойност к. но стойността на R се изисква само ако к ≥ 0.
В съответствие с това, говорим за езици със строги семантика и език с не-строги семантика. ( "липса на строгост" и "мързелив" - не са идентични, но подобни концепции.)
Стриктно език оценява аргументите, преди да приложите функцията. Така, ако изчисляването на експресия е не е завършена (или контури се спира с грешка), приложни функции е Е също не изчислява.
В не-строг изчисляване език е необходимо. Ако е толкова строг, след изчисляване на е д може да бъде завършена, дори и ако изчислението не е завършена електронна.
показва списък с три елемента. Изчисляване FAC (-1) вериги. Следователно, при изчисляването на списъка също ще премине.
Сега нека функцията дължина връща дължината на списък. изразяване
Той няма да бъде изчислена в строг език, но резултатът е не-стриктен 3 защото за изчисляване на елементи от техните стойности не са необходими.
Примери за строги езици: Миранда и Haskell. Строги езици - ML и схемата.
Въпрос на взискателност е тънка, и не може да бъде намален до една проста "Това, което е по-удобно и по-ефективно?"> Трансфер на разсрочено изчисление вместо стойностите параметър на функцията е свързано с разходи. Въпреки това, в много ситуации, мързел спестява изчисления или да пишете изрази, които няма да се изчисли или да бъдат изчислени безкрайно в енергични език.
Липса на взискателност е независима функция по отношение на чистота, макар и в много отношения помага език се въздържат от странични ефекти.
Кратка история
Един от първите езици с функционален стил бяха LISP (1958), APL (1964), ISWIM (1966) и FP (1977).
До края на 1980 г., вече има много функционални езици. Сред тези, които са имали значително влияние върху Haskell:
- ML (1973) - първият език с напечатан Хиндли-Милнър.
- SASL. KRC. Миранда (1972-1985) - един от първите мързелив език.
- Надявам (1980) - един от първите език с алгебрични типове данни. Haskell разработен от голяма група от изследователи от 1987 г. Той е кръстен в чест на Haskell Къри.
Фигура 4. Произходът на Haskell
Основната цел на която е фокусирана дизайна - Haskell трябваше да се съберат на съществуващия опит в областта на не-строг чисто функционален език.
Иновации Haskell - класове тип и монади. Други силни страни, привлечени от други езици - на кожи, алгебрични типове данни, модел за съвпадение. (Тук, ние просто да представи набор от ключови думи, всички тези понятия ще бъде обяснено скоро.)
Последен запис на описание - Haskell 98, но езикът непрекъснато се развива и сложни; Вече е насрочен за Haskell-Иш ".
Haskell се превърна в най-популярната не-строг чисто функционален език. На Haskell изпълнява много сложни проекти:
- Съставители и други инструменти за разработка.
- Разпределена система за контрол на версиите Darcs.
- мениджър на прозорци xmonad.
- приложения HAppS уеб-сървър.
- Преводач / Pugs компилатор за Perl 6 език.
- Операционна система House.
- Хардуер описание език Lava.
- система за обработка на естествен език Лолита.
- Система за доказване теореми Equinox / Paradox и Agda.
Основните източници на информация за Haskell
В Haskell има голямо и приятелска общност.
Основният източник на информация - haskell.org сървър.
Тя е пощенски списъци, включително:
- [email protected] - свободна дискусия.
- [email protected] - проста тема за начинаещи.
Налице е много оживен IRC-канал #haskell на irc.freenode.net. Възможно е да получите бързо любезен отговор почти всеки въпрос.
Редактиране и изпълнение на код
Haskell реализации
Формално, Haskell не разполага с единна "стандартен" изпълнение.
За интерактивен подход лек преводачески Прегръдки.
Също така има един интересен проект Yhc. компилира изходния код на байткод, и хелий - обучение на версията Haskell, приятелски настроени към новодошлите (например издаване на ясни съобщения за грешки). Въпреки това, те все още са в процес на развитие.
В де факто стандарт е съставител / GHC интерпретатор. Той е най-напреднала, във всички отговаря и предлага редица експериментални разширения. Ние ще се фокусира върху него.
Ние ще се интересуват предимно от програмата за интерактивна ghci, което е удобно за тестване на примери за обучение.
Така че, след като инсталирате GHC, можете да стартирате в терминал ghci на:
Тук Prelude - е името на зареден модул. Прелюдия съдържа основни дефиниции, и то винаги е активирана по подразбиране. Проучване или пренаписване на собствените си Prelude код, начинаещите могат да научат много. (Ние също така сме част ще го направя.)
В> символ означава, че ghci очаква данни от потребителя. Тя може да бъде израз Haskell, както и инструкции за интерпретатора.
← и → ключове можете да преместите курсора върху ghci на команден ред. ↑ и ↓, за да преминете през историята на командите напред-назад.
Вместо Prelude> или други имена модул, ние ще продължим да се напише ghci> (ако искате да направите същото, стартирайте командата ghci: настройте ред "ghci>").
За да започнете да ghci може да се използва като напреднало калкулатор:
Операторите с еднакви приета на други езици (виж таблица 2).
Таблица 2. Аритметични оператори на Prelude
За тях се използва в х запис и съответния приоритет. Например, 2 * 3 + 4 съответства на (2 х 3) 4. и 2 ^ 3 ^ 4 - 2 ^ (3 ^ 4). За да промените приоритета прие, че е възможно да се поставят скобите.
В ghci има специална го променлива. равна на стойността на последния израз оценена успешно.
Редактиране на изходния код
За Haskell код, използван .hs разширителни файлове.
Ако пишете код в Haskell в foo.hs. файл определенията са заредени в ghci команда: натоварване Foo. Успоредно с това, можете да редактирате файла, и, ако е необходимо, рестартирайте определението използване: презареди.
Сегашната командата промяна директория: CD (например CD / Начало / Боб.).
Можете да изтеглите прикачения статията до изходния код и да се изчисли израза:
Тези и други команди могат да бъдат намалени - вместо: използва натоварване: л. вместо: презареди -: R, и така нататък.
Списък на черупки дисплеи: помощ. За да излезете от ghci трябва да въведете: откажат.
В хода на презентацията ще бъдат често срещани примери за прости, състоящ се от една или две уравнения. Те могат да бъдат незабавно включени в ghci използващи нека:
Ако няколко уравнения, те трябва да бъдат затворени в скоби и разделени с точка и запетая (в бъдеща статия, ние ще обсъдим този пост).