Функциональное программирование
на языке Haskell
Конспект лекций
Рыбинск 2010
Введение..................................................................................................................... 3
1 История функционального программирования.................................................... 4
2 Особенности функциональных языков................................................................... 5
2.1 Основные свойства........................................................................................ 5
2.2 Преимущества............................................................................................... 9
2.3 Недостатки................................................................................................... 11
3 Обзор существующих языков............................................................................... 13
4 Базовые принципы языка Haskell......................................................................... 16
4.1 Интерактивная среда.................................................................................. 16
4.2 Структура программы............................................................................... 18
4.3 Типы функций............................................................................................. 22
4.4 Условные вычисления (ветвление).............................................................. 24
4.5 Сопоставление с образцом......................................................................... 27
4.6 Списки......................................................................................................... 29
4.7 Локальные определения............................................................................. 33
4.8 Дополнительные возможности интерактивной среды.............................. 35
4.9 Функции высшего порядка......................................................................... 36
4.10 Бесконечные структуры данных.............................................................. 37
5 Типы данных и модули......................................................................................... 40
5.1 Пользовательские типы и структуры данных........................................... 40
5.2 Модули........................................................................................................ 44
6 Классы и монады................................................................................................... 47
6.1 Классы......................................................................................................... 47
6.2 Ввод-вывод.................................................................................................. 49
7 Примеры................................................................................................................ 53
Заключение.............................................................................................................. 54
Список использованных источников...................................................................... 55
Введение
Перед описанием непосредственно функционального программирования обратимся к истории программирования вообще. В 1940-х годах появились первые цифровые компьютеры, которые программировались переключением различного рода тумблеров, проводков и кнопок . Число таких переключений достигало порядка нескольких сотен и росло с усложнением программ. Потому следующим шагом развития программирования стало создание всевозможных ассемблерных языков с простой мнемоникой.
Но даже ассемблеры не могли стать тем инструментом, которым смогли бы пользоваться многие люди, поскольку мнемокоды всё ещё оставались слишком сложными, а всякий ассемблер был жёстко связан с архитектурой, на которой исполнялся. Следующим шагом после ассемблера стали так называемые императивные языки высокого уровня: Бейсик, Паскаль, Си, Ада и прочие, включая объектно-ориентированные. Императивными («предписывающими») такие языки названы потому, что ориентированы на последовательное исполнение инструкций, работающих с памятью (т. е. присваиваний), и итеративные циклы . Вызовы функций и процедур, даже рекурсивные, не избавляли такие языки от явной императивности.
В парадигме функционального программирования краеугольным камнем является функция. Математические функции выражают связь между исходными данными и итоговым продуктом некоторого процесса. Процесс вычисления также имеет вход и выход, поэтому функция - вполне подходящее и адекватное средство описания вычислений . Именно этот простой принцип положен в основу функциональной парадигмы и функционального стиля программирования. Функциональная программа представляет собой набор определений функций. Функции определяются через другие функции или рекурсивно через самих себя. На функциональном языке программист должен только описать желаемый результат как систему функций.
2 История функционального программирования
Как известно, теоретические основы императивного программирования были заложены ещё в 1930-х годах Аланом Тьюрингом и Джоном фон Нейманом . Теория, положенная в основу функционального подхода, также родилась в 20-х - 30-х годах. В числе разработчиков математических основ функционального программирования можно назвать Моисея Шейнфинкеля и Хаскелла Карри, разработавших комбинаторную логику, а также Алонзо Чёрча, создателя λ-исчисления (лямбда-исчисления).
Теория так и оставалась теорией, пока в начале 1950-х годов Джон Маккарти не разработал язык Лисп (Lisp), который стал первым почти функциональным языком программирования и многие годы оставался единственным таковым. Лисп всё ещё используется, после многих лет эволюции он удовлетворяет современным запросам .
В связи с все возрастающей сложности программного обеспечения всё большую роль начинает играть типизация. В конце 70-х - начале 80-х годов XX века интенсивно разрабатываются модели типизации, подходящие для функциональных языков. Большинство этих моделей включали в себя поддержку таких мощных механизмов как абстракция данных и полиморфизм . Появляется множество типизированных функциональных языков: ML, Scheme, Hope, Miranda, Clean и многие другие. Вдобавок постоянно увеличивается число диалектов. Практически каждая группа, занимающаяся функциональным программированием, использовала собственный язык. Это препятствовало дальнейшему распространению этих языков и порождало многие более мелкие проблемы. Чтобы исправить положение, объединённая группа ведущих исследователей в области функционального программирования решила воссоздать достоинства различных языков в новом универсальном функциональном языке. Первая реализация этого языка, названного Haskell в честь Хаскелла Карри, была создана в начале 90-х годов.
3 Особенности функциональных языков
Как любая группа языков программирования, функциональные языки обладают некоторыми особенностями, которые выделяют их среди остальных языков и делают их именно языками функционального программирования.
3.1 Основные свойства
Среди свойств функциональных языков обычно выделяют следующие:
– краткость и простота;
– строгая типизация;
– функции – это значения;
– чистота (отсутствие побочных эффектов);
– отложенные (ленивые) вычисления;
– модульность.
Рассмотрим каждое из этих свойств подробнее.
Краткость и простота
Программы на функциональных языках обычно короче и проще, чем те же самые программы на императивных языках. Одним из самых распространенных примеров является быстрая сортировка Хоара.
На императивном языке C быстрая сортировка обычно реализуется следующим образом:
void qsort (int a, int l, int r)
int i = l, j = r, x = a[(l + r) / 2];
while (a[i] < x) i++;
while (x < a[j]) j--;
int temp = a[i];
while (i <= j);
if (l < j) qsort (a, l, j);
if (i < r) qsort (a, i, r);
На функциональном языке Haskell эта же сортировка записывается гораздо короче и нагляднее:
qsort (x:xs) = qsort
++ [x] ++ qsort
Этот пример следует читать так: если сортируемый список пуст, то результатом сортировки также будет является пустой список, иначе выделяются голова и хвост списка (первый элемент списка и список из оставшихся элементов, возможно пустой), и результатом будет являться конкатенация (сращивание) отсортированного списка из всех элементов хвоста, которые меньше головы, списка из самой головы и списка из всех элементов хвоста, которые больше либо равны голове.
Код на функциональном языке выигрывает по размеру кода и его наглядности. Кроме того, приведенная реализация на языке C сортирует массив, элементы которого имеют целочисленный тип (int), а реализация на Haskell может сортировать списки элементов любых типов, на которых определена операция сравнения.
Строгая типизация
Большинство языков функционального программирования имеют строгую типизацию. Строгая типизация подразумевает выполнение следующих обязательных условий :
– каждое значение, переменная, аргумент и возвращаемое значение функции на этапе проектирования программы безусловно привязывается к определённому типу данных, который не может быть изменён во время выполнения программы;
– функции могут принимать и возвращать значения, имеющие строго тот же тип данных, что указан при описании функции;
– каждая операция требует аргументов строго определённых типов;
– неявное преобразование типов не допускается (то есть транслятор воспринимает любую попытку использовать значение не того типа, который был описан для переменной, аргумента, функции или операции, как ошибку).
В теории программирования строгая типизация является непременным элементом обеспечения надёжности разрабатываемых программных средств . При правильном применении (подразумевающем, что в программе объявляются и используются отдельные типы данных для логически несовместимых значений) она защищает программиста от простых, но труднообнаруживаемых ошибок, связанных с совместным использованием логически несовместимых значений, возникающих иногда просто из-за элементарной описки. Подобные ошибки выявляются ещё на этапе компиляции программы, тогда как при возможности неявного приведения практически любых типов друг к другу (как, например, в классическом языке Си) эти ошибки выявляются только при тестировании, причём не все и не сразу.
Функции как значения
В функциональных языках программирования функции могут использоваться как любые другие объекты, они могут передаваться другим функциям в качестве аргументов, возвращаться в качестве результата других функций, храниться в списках и других структурах данных. Функции, принимающие в качестве аргументов или возвращающие как результат другие функции называются функциями высших порядков.
Использование функций высших порядков позволяет создавать более гибкие функции, повышая тем самым возможность повторного использования кода. В качестве примера обычно приводится передача функции сравнения элементов в функцию сортировки.
Чистота
Чистота заключается в отсутствии побочных эффектов при вычислении значений функции. Побочный эффект функции - это возможность в процессе вычисления своих вычислений чтения и изменения значений глобальных переменных, осуществления операций ввода/вывода, реагирования на исключительные ситуации, изменение значений входных переменных. Поэтому, если вызвать такую функцию дважды с одним и тем же набором значений входных аргументов, то результаты вычисления могут различаться, а также может измениться состояние некоторых глобальных объектов (например, значения переменных). Такие функции называются недетерминированными функциями с побочными эффектами.
В чистом функциональном программировании одна и та же функция при одних и тех же аргументах возвращает всегда один и тот же результат. Созданные объекты нельзя изменять или уничтожать, можно только создавать новые на основе уже существующих. Благодаря чистоте, программы не только становятся понятнее, но и упрощается организация параллелизма в них, так как функции могут вычисляться независимо друг от друга. Если результат чистой функции не используется, то ее вычисление может опускаться без вреда для других выражений. И если нет никакой зависимости по данным между двумя чистыми функциями, то можно поменять порядок их вычисления или вычислить их параллельно. В таком случае компилятор может использовать любую политику вычисления. Это предоставляет свободу компилятору комбинировать и реорганизовывать вычисление выражений в программе.
Отложенные вычисления
В традиционных языках перед вызовом функции вычисляются значения всех ее аргументов. Этот метод вызова функций называется «вызовом по значению». Если же какие-то из аргументов не используются, то вычисления были произведены впустую. Во многих функциональных языках используется другой метод вызова функций - «вызов по необходимости». При этом каждый аргумент функции вычисляется только в том случае, если его значение необходимо для вычисления результата функции. Например, операция конъюнкции из языка C++ (&&) не требует вычисления значение второго аргумета, если первый имеет ложное значение.
Ленивые вычисления в некоторых случаях позволяют ускорить выполнение программы, а так же позволяют использовать различные бесконечные структуры данных.
Модульность
Механизм модульности позволяет разделять программы на несколько сравнительно независимых частей (или модулей) с четко определенными связями между ними. Тем самым облегчается процесс проектирования и последующей поддержки больших программных систем. Поддержка модульности не является свойством именно функциональных языков программирования, однако поддерживается большинством таких языков.
3.2 Преимущества
Языки функционального программирования обладают рядом преимуществ по сравнению с императивными языками. Использование функциональной парадигмы программирования повышает надежность программ, скорость их написания, удобство модульного тестирования, возможности оптимизации при компиляции и возможности автоматической организации параллелизма.
Надежность программирования
Отсутствие побочных эффектов делает невозможным многие труднообнаруживаемые ошибки, такие как случайное присваивание неверного значения глобальной переменной. Строгая статическая типизация позволяет на этапе компиляции отловить большое количество ошибок, связанных с некорректным использованием некоторых данных.
Интересная особенность функциональных языков в том, что они поддаются математическому анализу. Поскольку функциональный язык – это просто реализация формальной системы, все математические операции, которые могли бы быть сделаны на бумаге, также применимы к программам, написанным на таком языке. Например, компилятор может преобразовывать фрагменты кода в эквивалентные, но более эффективные фрагменты, математически доказав эквивалентность фрагментов. Более того, вы можете использовать эти технологии, чтобы доказать, что определённые участки вашей программы корректны .
Удобство модульного тестирования
Поскольку функция в функциональном программировании не может порождать побочные эффекты, менять объекты нельзя как внутри области видимости, так и снаружи (в отличие от императивных программах, где одна функция может изменить какую-нибудь внешнюю переменную, считываемую второй функцией). Единственным эффектом от вычисления функции является возвращаемый ей результат, и единственный фактор, оказывающий влияние на результат – это значения аргументов.
Таким образом имеется возможность протестировать каждую функцию в программе, просто вычислив её от различных наборов значений аргументов. При этом можно не беспокоиться ни о вызове функций в правильном порядке, ни о правильном формировании внешнего состояния. Если любая функция в программе проходит модульные тесты, то можно быть уверенным в качестве всей программы. В императивных программах проверка возвращаемого значения функции недостаточна: функция может модифицировать внешнее состояние, которое тоже нужно проверять, чего не нужно делать в функциональных программах
Возможности оптимизации
Описание программы в виде набора функций без явного указания порядка их вычисления и чистота функций дают возможность применять к функциональным программам достаточно сложные и эффективные методы автоматической оптимизации.
Ещё одним преимуществом функциональных программ является то, что они предоставляют широчайшие возможности для автоматического распараллеливания вычислений. Поскольку отсутствие побочных эффектов гарантировано, в любом вызове функции всегда допустимо параллельное вычисление двух различных аргументов – порядок их вычисления не может оказать влияния на результат вызова.
Доказательство свойств функций
Так как вычисление функций в функциональном программировании не вызывает побочных эффектов, то к анализу таких функций применимы математические методы (например, метод математической индукции). Это позволяет без тестирования доказать правильность работы функций, либо какие-то другие их свойства.
3.3 Недостатки
Недостатки функционального программирования вытекают из тех же самых его особенностей. Отсутствие присваиваний и замена их на порождение новых данных приводят к необходимости постоянного выделения и автоматического освобождения памяти, поэтому в системе исполнения функциональной программы обязательным компонентом становится высокоэффективный сборщик мусора. Для эффективности сборки мусора необходимо отслеживать ссылки на данные, что также требует затрат времени и памяти. Отсутствие циклов для промышленных программ является довольно серьёзным ограничением, поскольку многие алгоритмы требуют очень длинных или даже формально бесконечных циклов, которые неэффективно или даже невозможно представлять в рекурсивном виде из-за слишком большой требуемой глубины рекурсии. В некоторой мере последний недостаток может быть обойдён путём автоматического преобразования рекурсии в цикл, выполняемого некоторыми трансляторами функциональных языков для специфического случая хвостовой рекурсии, но не все формы рекурсии допускают такое преобразование (впрочем, те из них, которые такому преобразованию не подлежат, не могут быть оформлены в виде простого цикла и в императивных языках).
Для преодоления этих недостатков многие функциональные языки включают в себя средства императивного программирования, позволяющие явно задавать порядок действий, использовать циклы и побочные эффекты (например, операции ввода и вывода).
4 Обзор существующих языков
В настоящее время разработано большое количество функциональных языков программирования. Все они обладают уникальными особенностями, положительными и отрицательными качествами. Самыми распространенными и эффективными на сегодняшний день являются следующие языки или семейства языков:
Рассмотрим особенности каждого из этих языков:
– Lisp . Получил название от английского LISt Processing – обработка списков. Lisp является одним из самых первых языков функционального программирования. Программы и данные в Lisp представляются системами линейных списков символов. Язык Lisp, наряду с языком Ada, прошел процесс фундаментальной стандартизации для использования в военном деле и промышленности, в результате чего появился стандарт Common Lisp. Его реализации существуют для большинства платформ. Первые области применения Лиспа были связаны с символьной обработкой данных и процессами принятия решений . Наиболее популярный сегодня диалект Common Lisp является универсальным языком программирования. Он широко используется в самых разных проектах: Интернет-серверы и службы, серверы приложений и клиенты, взаимодействующие с базами данных , научные расчёты и игровые программы.
– Haskell . Является одним из самых распространённых ленивых языков программирования. Имеет очень развитую систему типизации. В последнее время расширяется набор прикладных библиотек, язык интегрируется в распространённые программные системы, что делает язык всё более и более привлекательным для профессиональных программистов. Основные особенности языка: возможность использования лямбда-абстракции; функции высшего порядка; частичное применение; недопустимость побочных эффектов (чистота языка); ленивые вычисления (lazy evaluation); сопоставление по образцу, функциональные образцы (pattern matching); параметрический полиморфизм и полиморфизм классов типов; статическая типизация; автоматическое выведение типов (основано на модели типизации Хиндли – Милнера); алгебраические типы данных; типы данных с параметрами; рекурсивные типы данных; абстрактные типы данных (инкапсуляция); списочные включения (list comprehensions); охраняющие выражения (guards); возможность писать программы с побочными эффектами без нарушения парадигмы функционального программирования с помощью монад; возможность интеграции с программами, реализованными на императивных языках программирования посредством открытых интерфейсов (стандартное расширение языка Foreign Function Interface).
– ML (Meta Language) – семейство строгих языков функционального программирования с развитой полиморфной системой типов и параметризуемыми модулями. ML преподаётся во многих западных университетах. Сильно типизированный язык со статическим контролем типов и аппликативным выполнением программ. Основные достоинства ML – высокая верифицируемость программ, простота отладки, потенциал для высокой оптимизации, уникальная краткость записи. Основные недостатки – сложность синтаксиса, непривычность принятых соглашений и ограничений, практическая невозможность макротрансформаций.
– Erlang – функциональный язык программирования, позволяющий писать программы для разного рода распределённых систем. Разработан и поддерживается компанией Ericsson. Язык включает в себя средства порождения параллельных процессов и их коммуникации с помощью посылки асинхронных сообщений. Программа транслируется в байт-код, исполняемый виртуальной машиной, что обеспечивает переносимость. Главное в Erlang – его модель легковесных процессов. Перефразируя для Erlang слоган «Everything is an object» («Всё является объектом»), можно сказать «Everything is a process» («Всё является процессом»). Процессы дёшевы, создание процесса занимает не больше ресурсов, чем вызов функции. Единственным способом взаимодействия процессов является асинхронный обмен сообщениями.
Из перечисленных языков Haskell является наиболее ярким представителем языков функционального программирования. Он обладает простым синтаксисом и всеми перечисленными выше свойствами функциональных языков.
5 Базовые принципы языка Haskell
Как было сказано, язык программирования Haskell является функциональным языком, и он обладает всеми вышеперечисленными свойствами
Для начала рассмотрим необходимый инструментарий для работы. Самым распространенным и эффективным на сегодняшний день является компилятор GHC (Glasgow Haskell Compiler). Он распространяется под открытой лицензией, и любой желающий может загрузить его исходные коды или скомпилированную версию для популярных операционных систем с официального сайта http://haskell. org/ghc/ (кроме того, на сайте http://haskell. org/ можно найти много дополнительной информации по языку).
Кроме самого компилятора в GHC входит интерактивная среда GHCi (GHC interactive) - интерпретатор Haskell, позволяющий вычислять любые выражения и интерпретировать написанные программы.
К сожалению, полнофункциональной среды разработки для Haskell еще не разработано (кроме, возможно, Leksah - среды разработки для Haskell, написанной на Haskell, и нескольких плагинов для Visual Studio и Eclipse), но зачастую хватает возможностей лишь расширенного текстового редактора (например, Notepad++, gedit, kate) с подсветкой синтаксиса и некоторыми другими возможностями.
5.1 Интерактивная среда
Интерактивная среда GHCi может вычислять любые выражения на языке Haskell. Рассмотрим основы работы с этой средой. Для ее запуска (после установки GHC или Haskell-Platform) достаточно запустить в консоли программу ghci (либо выбрать соответствующую программу в списке всех программ). После запуска в консоли появится приглашение:
Prelude означает имя текущего модуля, по-умолчанию загружается стандартный модуль Prelude, содержащий все основные функции и типы данных.
Здесь мы можем вычислить любое выражение, например обыкновенное арифметическое выражение:
Как мы видим, интерактивная среда вычислила результат выражения и вывела его в новой строчке. Попробуем вычислить выражение посложнее:
Prelude> 1-2*(4-3^2)
Возведение в степень (^) является стандартным оператором, определенным в стандартном модуле Prelude наравне с операциями сложения и умножения.
Кроме арифметических выражений в интерактивной среде возможно вычислять любые другие функции, определенные в стандартном модуле, либо в любых других, загруженных пользователем.
Для вычисления значения функции записывается ее имя и указываются аргументы, разделенные пробелами. Например, в стандартном модуле определена функция max, выбирающая максимальное значение из двух аргументов. Использовать ее можно так:
Prelude> max 7 100
В данном примере вычисляется максимальное из двух чисел - семи и ста. Как мы видим, результатом вычисления функции является число 100.
В качестве аргументов функции могут выступать любые выражения (но только соответствующего типа; подробнее типы рассматриваются в других разделах), например:
Prelude> max (2^^3)
В этом примере определяется, что два в десятой степени превышает десять в третьей степени. Заметим, что заключение аргументов в скобки является обязательным для того, чтобы выделить какая часть выражения является аргументом. Например, если опустить скобки второго аргумента, то получим немного неожиданный результат:
Prelude> max (2^10) 10^3
Без скобок данное выражение интерпретируется как максимум из двух чисел (1024 и 10), возведенный в третью степень.
Кроме того, интерактивная среда GHCi может автоматически дополнять имена вводимых функций. Если набрать только начальную часть имени функции и нажать на клавиатуре клавишу «Tab», то GHCi попытается дополнить имя функции до имеющегося среди доступных определений (из стандартного модуля, либо подключенных пользователем). Например, если набрать «maxi» и нажать «Tab», то GHCi дополнит имя функции до «maximum». В том случае, если однозначно дополнить невозможно (есть несколько подходящих вариантов), то выводятся все возможные варианты:
max maxBound maximum
Теперь можно уточнить имя функции (дописав несколько букв) и снова нажать клавишу «Tab».
Автодополнение очень полезно при использовании большого количества функций с длинными именами.
5.2 Структура программы
Компиляторы и интерпретаторы языка Haskell работают с файлами с расширением *.hs , содержащими текст программы. Текст программы имеет следующую структуру:
1. в начале программы может быть указано имя текущего модуля и экспортируемые определения;
3. оставшуюся часть программы занимают различные определения - определения функций, типов данных и классов.
Простейшая программа может содержать только определения функций (в таком случае импортируется только стандартный модуль Prelude, содержащий большинство стандартных функций и типов данных; имя модуля задается по-умолчанию как Main).
Простейшая функция может вообще не принимать аргументов, а лишь возвращать некоторое значение. В таком случае определение состоит из имени функции, знака равенства «=», и некоторого выражения, по которому будет вычисляться значение данной функции. В привычных терминах такую функцию можно назвать переменной или константой, однако это не совсем корректно. В функциональном программировании функции без аргументов именуются символами. Рассмотрим пример:
В данном примере объявляется символ с именем five, который имеет значение, равное целому числу 5. Имена в Haskell чувствительны к регистру, то есть Five и five являются различными именами. Кроме того, вводится дополнительное ограничение на первую букву имени - имена функций и их аргументов могут начинаться только со строчной буквы (five, max, min, x, y), а имена типов данных (Bool, Integer, Double), модулей (Main, Test) и классов (Eq, Ord, Num) - только с прописной (заглавной).
Рассмотрим пример посложнее:
three = one + two
Здесь объявляется три символа - one, two, three. Как видно из примера, каждое определение занимает одну строчку и разделяются они только концом строки (пустые строчки будут игнорироваться). Символы one и two определены также, как и символ five в предыдущем примере, а при определении символа three используются уже существующие определения. Как несложно догадаться, символ three будет иметь значение 3.
Порядок определений не важен, то есть следующий пример будет совершенно аналогичен предыдущему:
three = one + two
Загрузим наш пример в интерактивную среду GHCi. Для этого достаточно при запуске ghci в качестве параметра командной строки указать имя файла с текстом программы (например, Test. hs) (в ОС семейства Windows достаточно просто открыть файл, установленный GHC автоматически назначает ghci для открытия файлов *.hs). Если программа не содержит ошибок, то мы увидим уже знакомое приглашение:
Здесь Main - имя текущего модуля (подробнее модули рассматриваются в соответствующей главе). GHCi позволяет вычислять любые функции из текущего модуля. Например, вычислим наш символ three:
Более сложные выражения также возможны:
*Main> (three+two)^2
*Main> max one two
Далее рассмотрим функции с аргументами. В отличие от привычных языков программирования для передачи аргументов не требуется записывать их в скобках и через запятую. Вызов функции происходит в следующем виде: func x1 x2 x3… xN, где func – имя функции, а xi – i-й аргумент. Результатом функции будет являться какой-либо объект, например, число, список, функция, лямбда-выражение либо любая другая структура данных.
Описание функции с аргументами практически не отличается от описания символов в предыдущих примерах. Определение функции располагается на отдельной строчке и имеет следующий вид: func x1 x2 x3… xN = expression, где func - имя новой функции, xi – имя i-го аргумента, expression - выражение.
Например, добавим функцию, складывающую два числа, в существующий файл Test. hs.
Теперь мы можем перезагрузить в интерактивной среде измененный модуль. Для этого достаточно перезапустить ghci, либо воспользоваться стандартной командой «:r»:
Compiling Main (Test. hs, interpreted)
Ok, modules loaded: Main.
После этого новая функция становится доступной из интерактивной среды:
*Main> plus one 8
Еще один пример функции с аргументами:
Каждое определение занимает одну строчку, однако, если для наглядности удобнее разделить определение на несколько строк, то можно использовать следующую особенность: каждая строчка, начинающаяся с отступа большего, чем предыдущая, считается ее продолжением. Например, можем записать функцию plus в две строки таким образом:
Однострочные комментарии в языке Haskell начинаются с двух тире:
plus x y = x+y --функция сложения
Блочный комментарий начинается с “” и заканчивается “”:
эта функция возвращает число на 1 большее
чем полученное в качестве аргумента
5.3 Типы функций
Haskell - строго типизированный язык, любые функции в нем имеют строго определенный тип. Однако, в предыдущих примерах нами тип не указывался, так как в интерпретаторах и компиляторах языка Haskell реализован мощный механизм вывода типов. Тип функций (и их аргументов) в большинстве случаев может быть выведен, исходя из определений этих функций. Некоторые функции могут иметь полиморфные типы (такие функции могут применяться к аргументам различных типов), например, ранее приведенная функция plus может суммировать целые числа и вещественные.
Как было сказано ранее, имена типов начинаются с прописных букв. Перечислим некоторые стандартные типы:
Описание |
|
целое число от - до |
|
длинное целое число, без границ (предусмотрено использование встроенной длинной арифметики) |
|
вещественное число |
|
вещественное число удвоенной точности |
|
список элементов некоторого типа a, например, список целых чисел записывается как |
|
строка (или список символов), эквивалент |
|
логический тип (принимает значения True или False) |
|
кортеж из двух элементов типа a и b (например, (String, Bool)) |
|
кортеж из трех элементов типа a, b и c (например, (String, Bool, Int)) |
Если программист желает сам указать тип функции и ее аргументов, либо автоматический вывод типа этой функции невозможен, то он должен сделать дополнительное определение, используя оператор указания типа “::”. Например, чтобы описать функцию, возвращающую вещественное значение, можно написать следующий код:
Первая строчка означает, что функция pi имеет тип Double, затем идет само определение функции, означающее, что функция pi возвращает приближенное значение числа пи. Если же функция имеет один аргумент, то ее тип описывается следующим образом:
inc:: Integer -> Integer
Данная запись означает, что функция inc преобразует аргумент типа Integer в результат типа Integer.
Если функция имеет два аргумента, то ее описание выглядит так:
power:: Double -> Integer -> Double
Функция power принимает два аргумента – вещественное основание x и целая степень n, результатом же вычисления функции является вещественное число.
В общем виде описание типа функции выглядит так так:
name:: X1 -> X2 -> ... ->XN -> Y
Здесь name – имя функции, Xi – тип i-го аргумента, Y – тип функции.
Как было сказано ранее, указание типов необязательно, но его наличие может обеспечить дополнительный контроль корректности построенных выражений в объявлении функции. Кроме того в некоторых случаях применения полиморфных типов невозможно определить тип функции без явного указания типа.
Перечислим некоторые стандартные функции.
Функции | Описание |
традиционные арифметические операции |
|
деление вещественных чисел |
|
возведение числа в целочисленную положительную степень |
|
возведение числа в вещественную степень |
|
целочисленное деление и остаток от деления целых чисел |
|
asin, acos, atan | обратные тригонометрические функции |
сравнение на равенство и неравенство |
|
>, <, >=, <= | сравнение |
логические операции |
|
первый элемент пары (кортежа из двух элементов) |
|
второй элемент пары |
|
хвост (все элементы кроме первого) списка |
5.4 Условные вычисления (ветвление)
В традиционных языках программирования основными способами организации ветвления являются условный оператор (if then else) и оператор выбора (case или switch). Кроме них в языке Haskell используется сопоставление с образцом в определениях функций и так называемые охраняющие выражения. Рассмотрим подробнее каждый из этих способов.
Конструкция if-then-else
Синтаксическая конструкция «if-then-else» позволяет вычислять различные выражения в зависимости от результатов некоторого условия:
if <условие> then <выражение1> else <выражение2>
Здесь <условие> - некоторое выражение, имеющее тип Bool. В отличие от императивных языков, в языке Haskell конструкция «if-then-else» является выражением, которое обязательно должно иметь какой-либо результат. В связи с этим ветка else является обязательной и типы выражений <выражение1> и <выражение2> должны совпадать.
Рассмотрим в качестве примера функцию вычисления максимального из двух чисел:
max a b = if a>b then a else b
Как уже было сказано, конструкция «if-then-else» является выражением, которое имеет результат. Следовательно, ее можно использовать как часть другого выражения:
*Main> 5 + if False then 1 else 0
*Main> (if True then 1 else 0) + 5
Заметим, что в последнем примере скобки обязательны. Без скобок выражение будет интерпретироваться иначе:
*Main> if True then 1 else 0 + 5
Все, что записано после слова «else» относится к выражению ветки else.
Конструкция case
Рассмотрим в качестве примера функцию вычисления заданного числа Фибоначчи:
fib n = case n of
_ -> fib (n-1) + fib (n-2)
Также как и условное выражение «if-then-else» выражение case имеет результат и, следовательно, может быть частью других выражений.
Рассмотрим case выражение в общем виде:
case <выражение0> of
<образец1> -> <выражение1>
<образец2> -> <выражение2>
<образецN> -> <выражениеN>
Здесь результат вычисления <выражение0> последовательно сопоставляется с образцами. При удачном сопоставлении с i-м образцом, результатом всего case будет являться результат i-го выражения. Подробнее сопоставление с образцом будет рассматриваться в соответствующем разделе, а пока его можно рассматривать как сравнение с заданными константами.
Обратим внимание, что каждый образец должен быть записан на новой строчке с отступом большим, чем отступ у зарезервированного слова case. Также отступы перед образцами должны быть равны между собой.
Кроме того, допустим альтернативный способ записи case-выражений без использования отступов:
fib n = case n of {1->1;2->1;_->fib (n-1) + fib (n-2)}
Такой способ более компактен, но менее нагляден. В общем виде:
case <выражение0> of { <образец1> -> <выражение1> ; <образец2> -> <выражение2> ; ... ; <образецN> -> <выражениеN> }
Определения функций
В языке Haskell одна и та же функция может иметь несколько определений, различаемых по записи ее аргументов. Запись аргумента называется образцом, и при вычислении функции, выполняется сопоставление переданных аргументов с образцами в определениях.
Рассмотрим в качестве примера функцию вычисления числа Фибоначчи.
fib n = fib (n-1) + fib (n-2)
При вычислении значения функции ее единственный аргумент сопоставляется с образцами ее определений сверху вниз. Если аргументом было число 2, то первое сопоставление окажется неудачным, а второе – удачным, и в результате функция примет значение 1. Если же аргумент не сопоставится с образцами в первых двух определениях, то он обязательно сопоставится с именем аргумента n (в данном случае n примет значение переданного аргумента), и будет вычислена сумма двух предыдущих чисел Фибоначчи.
Если же среди определений функции не будет найдено подходящего, то возникнет ошибка и выполнение программы остановится.
Охраняющие выражения
Последним способом выбора альтернатив при вычислении результата функций является так называемые охраняющие выражения . Они (в отличие от if-then-else и case-выражений) могут использоваться только в определениях функций:
<имя функции> <список аргументов функции>
|<условие1> = <выражение1>
|<условие2> = <выражение2>
|<условиеN> = <выражениеN>
Все символы “|” должны начинаться на своей строке и с одного отступа. При вычислении значения функции перебираются сверху вниз все условия, являющиеся выражениями типа Bool. Когда найдется i-е условие, результат которого равен True, вычисляется выражение i, результат которого будет результатом функции.
Например, запишем функцию нахождения числа Фибоначчи:
|otherwise = fib (n-1) + fib (n-2)
Здесь otherwise – это заведомо истинное условие, всегда равное True.
5.5 Сопоставление с образцом
Сопоставление с образцом (pattern matching) - это удобный способ связать различные части некоторого значения с заданными именами (символами) . Сопоставление с образцом используется в определениях и в case выражениях.
При определении функций сопоставление с образцом происходит в аргументах. В простейшем случае, когда аргументы задаются только именами, аргументы целиком связываются с этими именами. Например:
f x = fst x + snd x
Данная функция вычисляет сумму элементов кортежа. Стандартные функции fst и snd получают первый и второй элемент кортежа соответственно.
*Main> f (2,4)
Используя сопоставление с образцом, мы можем выделить содержимое аргумента этой функции более наглядным способом:
При вычислении этой функции от (2,4) элементы этого кортежа будут сопоставлены с указанным в определении функции образцом, то есть символ «a» примет значение 2, а символ «b» примет значение 4.
Так мы можем определить аналоги функций fst и snd:
Обратим внимание, что в определении функции fst1 не используется x, а в определении функции snd1 не используется y. В таких случаях, когда часть образца (или целый аргумент) не используется нет необходимости указывать имя этой части (или аргумента) - вместо имени достаточно указать символ подчеркивания «_». Переопределим эти функции:
Используя такой способ записи, не приходится придумывать имена ненужным частям образцов и при чтении определения функции сразу становится ясно, что эта часть аргумента не используется.
В образцах могут указываться любые конструкторы (в предыдущих примере использовался конструктор кортежа), например, конструкторы списка, кортежа, или любых пользовательских типов данных, а также конкретные значения аргументов (как в примере про числа Фибоначчи). В некоторых случаях сопоставление может оказаться неудачным, тогда происходит попытка использовать следующее сопоставление (из следующего определения или образца case). Рассмотрим пример:
f _ 0 = error "division by zero"
f (a, b) c = (a+b)/c
Здесь при вычислении функции f второй аргумент будет равен 0, то для вычисления функции будет выбрано первое определение, иначе - второе, так как сопоставление с именем всегда удачно. Функция error останавливает выполнение программы с заданным текстом ошибки. Примеры использования описанной функции:
*Main> f (1,2) 3
*Main> f (3,2) 1
*Main> f (5,5) 5
*Main> f (5,5) 0
*** Exception: division by zero
Кроме того, каждый образец может быть поименован для того чтобы к структурированному аргументу был доступ и поэлементно и целиком. Для именования образца используется оператор @. Перед ним идет имя, через которое можно осуществлять доступ к аргументу как к единому целому, а затем сам образец. Например,
func1 p@(a, b) = a + b + func2 p
func2 (a, b) = a*b
5.6 Списки
Список - одна из важнейших структур данных, в состав которой входят элементы одного типа. Список не может содержать разнотипные элементы (в отличие от кортежей). Для описания типа «список» применяются квадратные скобки. Например, является описанием типа списка из элементов логического типа.
Списки создаются с помощью конструктора списка - операции «:». Список может быть либо пустым, либо состоять из головы (первый элемент списка) и хвоста (список из остальных элементов). Пустой список обозначается пустыми квадратными скобками: «», а список, состоящий из головы x и хвоста y записывается с помощью конструктора списка: «x:y».
Существует и более удобный способ записи списков: перечислением элементов в квадратных скобках. Например, список целых чисел от 1 до 3 может быть записан так:
1: = 1:2: = 1:2:3:
Конструктор списка может использоваться при сопоставлении с образцом. При таком сопоставлении передаваемый в качестве аргумента список разделится на голову и хвост, доступ к которым может осуществляться через указанные в образце символы. Если список будет пустым, то сопоставление в данном определении будет неудачным.
Например, можно описать функцию взятия головы списка:
В приведенной выше реализации функции head хвост списка не используется, можно заменить его имя подчеркиванием:
Аналогично можно описать операцию взятия хвоста списка.
Эти две функции (head и tail) вызовут ошибку при передачи им пустого списка, так как сопоставление не будет успешным.
Рассмотрим еще пример функции работы со списками: функция вычисления длины списка:
length (_:t) = 1 + length t
Если входной список пуст, то в результате сопоставления сработает первое определение, иначе – второе.
Строки в языке Haskell являются списками символов. Символы записываются в апострофах (например, "c"), а строки – в кавычках (например, "string"). Любую строку можно представить в стандартной записи списков, например, строка "string" аналогична списку ["s","t","r","i","n","g"]. Работа со строками выполняется точно так же, как со списками.
Доступ к элементам списка осуществляется последовательно путем постепенного отсечения головы и хвоста. Например, чтобы получить n-й элемент списка (начиная с 0), можно написать функцию:
getN (x:_) 0 = x
getN (_:t) n = getN t (n-1)
Взятие n-го элемента списка реализовано в стандартной функции "!!". Она используется так:
Здесь list – список, n – номер искомого элемента. Нумерация элементов начинается с нуля. Если длина списка окажется меньше или рана номеру искомого элемента, вычисление этой функции приведет к ошибке.
Кроме того, возможно задание списков из перечислимых элементов (например, целые числа или символы) следующим образом:
Здесь X1 – начало арифметической прогрессии, а X2 – ее конец. Например, является списком . Таким способом можно задавать только возрастающие списки с шагом равным единице. Если нужно задать последовательность с другим шагом, то можно использовать следующую запись:
В этом варианте X1 – первый элемент последовательности, X2 – второй, X3 – возможный последний. Шаг последовательности выбирается как X2-X1, и последовательность содержит элементы, расположенные только между X1 и X3. Например, является списком .
Также существует способ задания списков на основе уже существующих. В общем виде этот способ можно записать так:
[<выражение> | <образец> <- <список>, <ограничение1>, ..., <ограничениеN>]
Из некоторого списка выбираются элементы, сопоставляемые с образцом и удовлетворяющие всем ограничениям, и формируется список из элементов, вычисляемых выражением, использующим этот образец. Например,
[ x^2 | x <- ,mod x 3 == 0]
Данное выражение конструирует список из квадратов нечетных чисел от одного до 30, которые делятся на 3. Результатом будет:
Кроме того, очень полезной при работе со списками является функция map, определенная в стандартном модуле. Она применяет к заданному списку некоторую функцию и возвращает список, полученный в результате применения этой функции к элементам исходного списка. Функция map может быть реализована следующим образом:
map:: (a -> b) -> [a] -> [b]
map f xs =
То есть, она принимает в качестве первого аргумента функцию, преобразующую объекты типа a в объекты типа b, а в качестве второго аргумента – список из элементов типа a. Результатом функции map является список элементов типа b.
При использовании функции map удобно применять безымянные функции, которые описываются в виде λ-выражений (рассматриваются подробнее в разделе о функциях высшего порядка). Например, список квадратов чисел от 1 до 10 может быть описан следующим образом:
map (\x->x*x)
Результатом данной функции является список:
Так как в языке Haskell есть встроенная операция возведения в степень, то данный список можно получить так:
map (^2)
Также, можно применять и любые другие функции, например:
map inc
Рассмотрим несколько функций, определенных в стандартном модуле, предназначенных для работы со списками.
Имя функции | Описание |
|
голова (первый элемент) списка |
||
хвост (все кроме первого элемента) списка |
||
последний элемент списка |
||
все элементы списка кроме последнего |
||
[a] → Int → a | элемент с заданным номером |
|
вычисление длины списка |
||
Int → [a] → [a] | взять из списка n первых элементов |
|
Int → [a] → [a] | отбросить из списка n первых элементов |
|
разворачивание списка в обратном порядке |
||
(Num a) => [a] → a | сумма элементов списка |
|
(Num a) => [a] → a | произведение элементов списка |
|
[a] → [a] → [a] | конкатенация списков |
5.7 Локальные определения
Haskell является чистым функциональным языком программирования, следовательно в нем не может быть глобальных переменных, более того, в нем вообще нет переменных. Никакой объект не может быть изменен, может быть получен только новый, с использованием старого. Некоторым “заменителем” переменных могут служить параметры функций и локальные функции.
Существует два способа описания локальных функций: с помощью зарезервированного слова where и let . Определение локальных функций с помощью where может использоваться только в определении функции. Определим функцию вычисления среднего арифметического трех чисел:
average3 x y z = s / 3
В общем виде использование where может быть записано так:
<имя функции> <аргументы> = <выражение>
<определение 1>
<определение 2>
<определение N>
Все определения должны находиться на одном и том же отступе, но большем чем строка, содержащее where. При желании можно использовать следующий синтаксис:
<имя функции> <аргументы> = <выражение> where { <определение 1> ; <определение 2> ; ... ; <определение N> }
Второй способ (с использованием let) может быть использован в любом выражении (не только при определении функций). В отличие от where определения локальных функций должны быть записаны до самого выражения Перепишем предыдущий пример:
average3 x y z =
В общем виде этот способ выглядит так:
<определение 1>
<определение 2>
<определение N>
<выражение>
Все определения должны находиться на одном и том же отступе, но большем чем строка, содержащее let. Слово in должно находится на отступе не меньшем чем let. При желании можно использовать следующий синтаксис:
let { <определение 1> ; <определение 2> ; ... ; <определение N> } in <выражение>
В таком случае отступ игнорируется.
5.8 Дополнительные возможности интерактивной среды
В интерактивной среде GHCi кроме вычисления функций или выражений есть множество дополнительных возможностей. Многие из них доступны через команды, начинающиеся с символа «:». Например, написав в строке GHCi команду «:?» можно увидеть список всех остальных команд (по командам также работает автодополнение). Рассмотрим наиболее полезные команды.
:t - получение типа указанного выражения. Например:
*Main> :t reverse (tail "mama")
reverse (tail "mama") ::
:i - получение информации о функции (тип, в каком модуле или классе определена). Например:
*Main> :i reverse
reverse:: [a] -> [a] -- Defined in GHC. List
:l - загрузить указанный модуль и сделать его текущим.
:m - загрузить или выгрузить указанный модуль.
:q - закрыть GHCi.
Еще одной полезной особенностью является возможность задания определений функций прямо в GHCi. Для этого используется упрощенная конструкция let. Например:
*Main> let f x = x+2*x
Полная же конструкция let действует только в пределах своего выражения:
*Main> let z = 10 in z+z
GHCi сообщает, что данное имя не определено в текущей области видимости.
5.9 Функции высшего порядка
В языке Haskell функции могут быть использованы как любые другие объекты - их можно хранить в списках и кортежах, передавать в другие функции, возвращать в качестве результата работы других функций.
Функции, принимающие или возвращающие другие функции называются функциями высшего порядка. Одной из таких функций, например, является функция map, применяющая заданную функцию ко всем элементам списка.
Дописать как следует этот раздел
Рассмотрим функцию сложения двух чисел:
plus x y = x + y
Функцию plus можно описать иначе:
Операция +, будучи заключенной в скобки, является функцией 2х переменных, следовательно, применив к ней два параметра, в результате получим их сумму. Если же к этой функции применить только один аргумент, например число 3, получим функцию одного аргумента, которая задает прибавление к числу 3 этого аргумента:
Такой процесс постепенного разделения функций на функцию, принимающую один параметр, и функцию, возвращающую другую функцию, вычисляющую все остальное, называется каррированием функций.
Еще вариант описания функции plus:
Используя функцию plus (любую вышеприведенную реализацию), можно написать функцию инкрементации:
inc x = plus 1 x
Используя каррирование можно получить другую реализацию этой же функции:
Получается, что функция inc возвращает функцию, прибавляющую 1 к одному своему параметру.
Кроме такого способа записи функций в Haskell"е существует способ задания с помощью λ-исчислений. Например, функция plus может быть реализована следующим образом:
plus = \x y -> x+y
Здесь “\” означает начало λ-выражения, затем перечисляются параметры (x y), и после стрелки (->) идет выражение.
λ-исчисления могут использоваться для задания безымянных функций. Например, можно использовать функцию сложения, не описывая ее отдельно:
Это выражение является функцией. Следовательно, применив к нему параметры, получим результат.
(\x y -> x+y) 3 6
Результатом будет число 9.
Безымянные функции полезны, например, при передаче функций в качестве параметров другим функциям, когда не нужно оформлять функцию соответствующим образом.
Если какой-либо параметр функции не используется при вычислении ее значения, то его имя можно опустить, заменив символом “_”. Например, функция, возвращающая первый параметр из двух, может выглядеть так:
Либо, в обычной записи:
firstoftwo x _ = x
5.10 Бесконечные структуры данных
Haskell относится к нестрогим языкам, то есть в нем используются так называемые отложенные (ленивые) вычисления. Как уже было сказано выше, это означает, что вычисляются только те выражения, которые необходимы для вычисления результата функции. Рассмотрим функцию, определенную через саму себя:
Очевидно, что её значение не может быть вычислено. При попытке это сделать, произойдет зацикливание. Рассмотрим еще одну функцию:
Её значение не зависит от параметра х. Следовательно нет необходимости его вычислять. И вычисление выражения
не приведет к зацикливанию и вернет результат равный 1.
Подобные ленивые вычисления позволяют организовывать бесконечные структуры данных, например, бесконечные списки. Один из самых простых способов задания бесконечных списков – это задание арифметических прогрессий. Для этого не нужно указывать конец интервала. Например, следующие списки являются бесконечными:
Они задаются только первыми двумя элементами, по которым вычисляется шаг прогрессий. Если второй элемент прогрессии не указан (как в первом примере), то шаг принимается равным 1.
Над этими списками возможно выполнение тех же операций и применение тех же функций, что и для обыкновенных списков, которые не требуют для вычисления результата всех элементов списка. К таким функциям относятся взятия головы и хвоста, функции получения i-го элемента списка и так далее.
Бесконечные списки оказываются полезными при решении некоторых задач. Например, вычисление факториала может быть реализовано следующим образом:
fact n = factlist !! n
factlist = fl 1 1
where fl x n = x:(fl (x*n) (n+1))
Функция определения факториала числа n (fact n) возвращает в качестве результата n-й элемент списка factlist, который является бесконечным списком факториалов всех натуральных чисел. Элементы этого списка вычисляются и занимают память только при необходимости получения их значений.
Бесконечными могут быть не только списки, но и любые другие структуры данных, определенные программистом, например деревья.
6 Типы данных и модули
6.1 Пользовательские типы и структуры данных
При описании типов функций могут потребоваться пользовательские синонимы уже существующих типов. Например, при громоздком определении некоторого типа удобно назвать его одним именем. Не очень приятно каждый раз писать что-нибудь наподобие [(Integer,)], удобнее дать этому типу имя, например, MyType1. Такое определение имеет вид:
type MyType1 = [(Integer,)]
Такое определение типа не описывает новую структуру данных, а только дает имя комбинации уже существующих типов.
Для того чтобы определить собственный тип данных используется следующая запись:
data <имя> = <значение1> | <значение2> | ... | <значениеN>
Таким образом, описывается структура данных с именем <имя>, которая может принимать значение 1, значение 2, и так далее до значения N. Этими значениями типа данных являются конструкторы данных. Каждый конструктор должен иметь уникальное имя, начинающееся с прописной буквы. Имя конструктора данных может совпадать с именем типа данных Например, описание типа данных «цвет» может быть представлено так:
data Color = Red | Green | Blue
Кроме того конструктор может принимать некоторые данные как функция. Например, можно дополнить тип данных «цвет», добавив представление цвета в комбинации красного, зеленого и синего цветов:
data Color = Red | Green | Blue | RGB Double Double Double
Такая запись означает, что объекты типа Color могут принимать значения Red, Green, Blue либо RGB r g b, где r g b - вещественные числа. Например, можно определить функцию, возвращающую желтый цвет:
Задание типов данных может быть полиморфным, так же как задание функций. То есть, можно задать такой тип данных, который содержит в себе некоторый другой, но не конкретный тип. Например, стандартный тип Maybe может быть описан следующим образом:
data Maybe a = Nothing | Just a
Это означает, что объект типа (Maybe a) может быть принимать значение Nothing, либо Just x, где x – объект некоторого типа a. Для доступа к таким объектам используется сопоставление с образцом. Например, можно реализовать функцию unJust, которая вернет содержимое контейнерного класса Maybe если оно не равно Nothing.
unJust (Just a) = a
Рассмотрим еще пример:
find:: (Eq a) => a -> [a] -> Maybe Int
find _ = Nothing
| x == a = Just 0
| otherwise = case (find a xs) of
(Just i) -> Just (i+1)
Nothing -> Nothing
Эта функция возвращает индекс первого вхождения объекта, переданного первым параметром, в списке, переданном вторым параметром, или Nothing в случае его отсутствия. В определении функции используется класс Eq, ограничивающий типы параметров функции сравнимыми типами. Классы будут рассмотрены в следующей главе.
С помощью ключевого слова data можно описывать любые структуры данных. Опишем в качестве еще одного примера бинарное дерево:
data Tree a = Nil | Node a (Tree a) (Tree a)
Это определение говорит о том, что дерево с элементами типа a может быть либо пустым деревом, либо состоять из элемента типа a и еще из 2х деревьев, которые определяются аналогично.
Опишем функцию добавления элемента в бинарное дерево поиска.
addtotree Nil x = Node x Nil Nil
addtotree (Node y left right) x
|x |x>y = Node y left (addtotree right x) |otherwise = Node y left right При добавлении в пустое дерево результатом является дерево с единственным узлом, содержащим добавляемый элемент. А в том случае, если дерево не пустое, то в зависимости от отношения добавляемого элемента с элементом в корне дерева, выбирается последующая стратегия вычисления. Если добавляемый элемент меньше, то его необходимо добавить в левое поддерево, следовательно, результатом будет дерево с тем же ключом и правым поддеревом, но с новым левым поддеревом, полученным при добавлении элемента в старое. Если добавляемый элемент больше корневого, то он результатом будет дерево с измененным правым поддеревом. Если же добавляемый элемент совпадает с корневым, то результат совпадет с переданным в качестве аргумента деревом. Организуем вывод дерева на экран в форме с уступами, определив функцию преобразования его (дерева) в строку. showtree tree = showtr tree 0 where showtr (Nil) n = replicate n "\t" ++ "-\n" showtr (Node x left right) n = showtr right (n+1) ++ replicate n "\t" ++ show x ++ "\n" ++ showtr left (n+1) Локальная функция showtr принимает два аргумента - дерево и уровень глубины. Используемая функция show является стандартной функцией для перевода в строковый вид практически любых объектов в Haskell. Теперь в результате вычисления выражения addtotree (addtotree (addtotree (addtotree (addtotree (addtotree (addtotree Nil которое означает последовательное добавление в дерево целых чисел 5, 3, 8, 1, 4, 6, 9, получим некоторый объект типа Tree. Передав его нашей функции showtree, получим строковое представление этого дерева. Существует еще один способ определения пользовательских данных - ключевое слово newtype. Его использование практически аналогично data, за исключением одного: типы данных, описанные с помощью newtype имеют только один конструктор данных ровно с одним полем. Этот способ используется для создания нового типа данных на основе уже имеющегося: newtype MyInt = MyInt Int Кроме того, есть возможность определения таких структур данных, как записи с поименованными полями. Использование обыкновенных кортежей, либо структур данных, при использовании объектов с большим количеством различных свойств не всегда удобно. Приходится запоминать порядок их следования, и ориентироваться только по нему, либо заводить соответствующую функцию для каждого из свойств. Запись с поименованными полями позволяет автоматизировать этот процесс, и предоставляет доступ к своим элементам через имена, что значительно упрощает работу. Их описание производится следующим образом: <имя записи> { <имя поля 1> :: <тип поля 1>, <имя поля 2> :: <тип поля 2>, <имя поля N> :: <тип поля N>} Например: data Human = Human { height:: Double, Для задания объекта данного типа можно записать: mike = Human{name="Mike",height=173.4,weight=81.3} Для изменения такого объекта, точнее для получения нового, но с измененными некоторыми полями, можно писать так: john = mike{name="John"} Haskell поддерживает модульное программирование, то есть программа может быть разделена на модули, и каждый модуль может быть использован в нескольких программах. Каждый модуль должен иметь вид: Если необязательная часть опущена, то данный модуль не сможет быть использован из других модулей. Имя модуля, также как и типы данных, должно начинаться с прописной буквы, а также совпадать с именем файла. Для получения доступа к определениям (функции, типы данных, классы) во внешних модулях, необходимо в самом начале программы описать их следующим образом: import <модуль1> import <модульN> <остальной код> После этого все определения из этих модулей становятся доступными в текущем модуле. Но если в текущем модуле определены функции или типы данных, совпадающие по имени с импортируемыми, либо если в разных подключаемых модулях окажутся одноименные функции или типы данных, то возникнет ошибка. Чтобы этого избежать, необходимо запретить использование таких определений из соответствующих модулей. Это делается следующим образом: import <модуль> hiding (<скрываемые определения>) Кроме того, при описании самого импортируемого модуля есть возможность управлять доступом к определениям. Для этого нужно перечислить доступные определения в скобках после имени модуля: module <Имя>(<определения>) where <код> Из всех описаний для внешних модулей будут доступны только перечисленные в скобках. В качестве примера можно привести программу из 3х модулей: --
Prog
.
hs
module Prog where import Mod2 hiding(modfun) module Mod1(modfun) where modfun = five * 2 module Mod2 where Из модуля Prog доступна функция modfun, определенная в модуле Mod1, но не доступна функция five. В Haskell"е поддерживается объектно-ориентированная парадигма. Но она немного отличается от привычной, принятой в других языках. Экземпляром класса является структура данных. Каждый класс предполагает описание некоторых функций для работы с типами данных, которые являются экземплярами этого класса. Для определения класса используется следующая запись: сlass [(<ограничения>) =>] <имя> <переменная типов> where <функции> Переменная типов именует некий тип, который должен быть экземпляром этого класса. После слова where распологаются описания типов функций, а также выражение некоторых из этих функций через друг друга. С помощью этих выражений интерпретатор сможет сам определить часть функций экземпляра класса, если задана другая часть. Ограничения – это определение того, что экземпляр нашего класса также должен быть экземпляром перечисленных здесь классов. Это, своего рода, наследование. Рассмотрим пример: class Eq a where (==), (/=) :: a -> a -> Bool x == y = not (x/=y) x /= y = not (x==y) Класс Eq является классом сравнимых типов. Для каждого экземпляра этого класса должны быть определены функции равенства и неравенства. Вторая строка означает, что функции (==) и (/=) должны принимать два аргумента типа a и возвращать объект типа Bool, то есть True или False. Следующие строчки в определении класса говорят о том, что если определена функция (/=), то функция (==) определяется через нее соответствующим образом, и наоборот. Благодаря этому программисту достаточно определить только функцию сравнения на равенство (или неравенство), а другую функцию интерпретатор определит сам. Еще пример определения класса, но с наследованием: class Eq a => MyClass a where myFunc:: [a] -> a -> Int Когда класс определен, можно объявить какой-либо тип данных экземпляром этого класса: instance MyClass Double where |x==z = 1 + myFunc xs z |otherwise = myFunc xs z Таким образом мы объявляем стандартный тип Double экземпляром нашего класса MyClass и определяем функцию myFunc как функцию, вычисляющую количество элементов в первом аргументе, равных второму аргументу функции. Определив тип как экземпляр класса, можно применять к объектам этого типа описанные при этом функции. test = myFunc x 2 where Классы часто используются при описании функций с полиморфными параметрами. Например, если нужно описать функцию, использующую операцию сравнения, для многих типов данных, необходимо указать, что ее параметры, которые участвуют в сравнении, должны быть типа класса Eq, который гарантирует реализацию соответствующей функции. Когда программист описывает свою структуру данных, она не принадлежит ни к какому из классов. При необходимости программист должен реализовать соответствующие функции для своей структуры и указать ее принадлежность к классу. Например, ранее описанную структуру данных Tree можно объявить экземпляром класса Show, для того что бы интерпретатор мог выводить ее на экран, не прибегая к ручному вызову функции showtree. Для этого напишем: instance Show a => Show (Tree a) where После этого при получении интерпретатором результата типа Tree он сможет вывести его на экран, а также любая другая функция сможет перевести объект типа Tree в строковый вид с помощью функции show. Кроме того, существует еще один способ объявления принадлежности типа к классу. Он более прост, но не всегда может удовлетворить потребности программиста. Он заключается в перечислении нужных классов сразу при объявлении структуры: data <имя> = <значение1> | <значение2> | ... | <значениеN> deriving (<класс1>,<класс2>,...,<классM>) Здесь необходимые функции будут при возможности выведены автоматически. Так, например, определим наш тип Tree экземплярам класса Eq, для того чтобы деревья можно было сравнивать между собой. data Tree a = Nil | Tree a (Tree a) (Tree a) Теперь возможно сравнение деревьев операцией “==”, и позволяет использовать их в функциях, требующих это. Возможно написать побольше про монады Как было сказано выше, Haskell - чистый функциональный язык программирования, то есть функции в нем не могут иметь побочных эффектов, и порядок вычисления функций не определен. Но в некоторых случаях без этого обойтись нельзя. К таким случаям можно отнести работу с пользователем, с файлами, с базами данных и так далее. В языке Haskell предусмотрено задание таких функций с помощью монад - особых контейнерных классов. В изучении Haskell"а монады считается самой трудной частью, поэтому начнем сразу с примеров. Объяснение некоторых вещей будут опущены, чтобы не запутать читателя. Рассмотрим следующий пример: putStrLn "Hello world!" putStrLn "Good bye world!" В этом примере функция main обладает побочными эффектами - в результате ее вычисления на экране отображается текст, и в ней определен порядок вычисления - сначала на экран выводится первая строка - затем вторая. При использовании нотации do программирование «нечистых» функций с помощью монад сводится практически к привычному императивному программированию. Каждая следующая строчка должна быть функцией специального типа - монадического типа. В случае работы с вводом-выводом это тип (IO a). Для работы с командной строкой используются следующие функции: putChar:: Char -> IOвывод символа putStr:: String -> IOвывод строки putStrLn:: String -> IOвывод строки с переходом на новую строку IO a - это монадический тип ввода-вывода, скрывающий побочные эффекты в себе. Тип IO String означает, что функция вернет результат, содержащий строку, а IO () означает, что функция возвращает результат, ничего не содержащий, смысл ее вызова только в побочных эффектах (например, вывод). Пример: putStrLn "What is you name?" name <- getLine Здесь появилось «присваивание». По аналогии с императивными языками можно сказать, что в строке name <- getLine произошло присваивание переменной name результата функции getLine. Но, как мы знаем, в Haskell"е нет переменных и значит и присваиваний. В данном случае произошло создание некоторого объекта с именем name, значение которого равно результату вычисления функции getLine. То есть, если после этого написать еще раз name <- getLine то создастся новый объект, имя которого перекроет предыдущий. Таким образом выполняется извлечение результатов монадических функций. Для того чтобы задать подобным образом «переменные» значениями обыкновенных функций используется упрощенная нотация let: let name = "John" Ветвление вычислительного процесса осуществляется с помощью тех же if then else и case: putStrLn "What is you name?" name <- getLine "GHC" -> putStrLn "No! I am GHC!" _ -> putStrLn ("Hi, " ++ name ++ "!") Если ветвление должно состоять из нескольких функций, то используется ключевое слово do: putStrLn "What is you name?" name <- getLine putStrLn "No! I am GHC!" _ -> putStrLn ("Hi, " ++ name ++ "!") Циклы осуществляются с помощью рекурсии, как показано выше, или с помощью специальных функций (реализованных также рекурсивно). К таким функциям относится функция mapM_. Принцип ее работы аналогичен функции map для списков - она применяет монадическую функцию ко всем элементам списка и последовательно выполняет их. Пример: writeDigit x = do putStr "Digits:" mapM_ writeDigit Привести различные примеры (деревья поиска, AVL дерево, еще что-нибудь) Заключение 1 http://ru. wikibooks. org/wiki/Основы_функционального_программирования 2 http://www. *****/article/funcprog/fp. xml 3 Душкин программирование на языке Haskell – ДМК Пресс, 2007 – 608 с. 4 http://en. wikibooks. org/wiki/Haskell/Pattern_matching 5 http://www. haskell. org/tutorial/ Привет Habr! Сегодня я достал свои старые конспекты по курсу «Haskell как первый язык программирования» Сергея Михайловича Абрамова и попробую максимально доходчиво и с примерами рассказать об этом замечательном языке тем, кто с ним еще не знаком. Рассказ ориентирован на неподготовленного читателя. Так что, даже если вы впервые услышали слово Haskell… Числа
Числа с плавающей точкой: Логические величины
Символы
Списки
Несколько стандартных операций в примерах: Упорядоченные множества
Но, сердце Haskell и всего функционального программирования - это, конечно, сами функции! Первая строка - это объявление функции: Вторая строка - это определение функции: Функция без параметров есть ничто иное, как константа: Функция с несколькими параметрами: Case … of …
Но, помимо стандартных if и case, в Haskell есть очень красивая и наиболее используемая конструкция ветвления. Так называемые, охранные выражения
. Пример: Ну вот, на сегодня и все. Если будет интерес, в ближайшее время напишу продолжение. «У нас были летающие управляемые снаряды, ракетоплан, обладавший еще большей скоростью, чем реактивный самолет, самонаводящаяся по тепловому излучению зенитная ракета, морская торпеда, способная преследовать корабль, ориентируясь по шуму винтов. Авиаконструктор Липпиш подготовил чертежи реактивного самолета, далеко обогнавшего тогдашний уровень самолетостроения, – летающего крыла. Можно сказать, мы испытывали трудности от обилия проектов и разработок…» - писал в своих мемуарах министр промышленности Третьего Рейха Альберт Шпеер. Герр Шпеер, мы знаем, что у вас были сверхтяжелые танки, высокоавтономные подводные лодки, инфракрасные прицелы, баллистические ракеты, суборбитальный бомбардировщик доктора Зенгера, секретные «дисколеты» и базы в Антарктиде… фашистские мерзавцы даже отправили экспедицию в Тибет и вступили в контакт с внеземной цивилизацией Альфы Центавра.
Макет ядерного реактора B VIII в г. Хайгерлох. Единственная более-менее реалистичная конструкция немецкого реактора. Увы, когда его собрали, то оказалось, что количество урана нужно увеличить на 750 кг, немцы просчитались. На самом деле, нет никаких оснований говорить о техническом превосходстве Третьего Рейха, наоборот, справедливо признать, что под конец войны германская наука серьезно отстала от своих противников. Большинство немецких фантастических проектов «супер- » отражали намерения, а не возможности. В это же время, у союзников появлялись не менее передовые образцы техники, которые, в отличии от немецкого «вундерваффе», были запущены в серийное производство и доказали в бою свою высокую эффективность. В этом легко убедиться на нескольких примерах. Люфтваффе
25 февраля 1945 года. В окрестностях авиабазы Гильберштадт с воем и грохотом падают реактивные Me.262 – американские «Мустанги» подстерегли группу на взлете и в упор расстреляли шесть не успевших набрать скорость, беспомощных «Мессершмиттов»… Снова немецкая техника? Нет, это британский истребитель "Глостер-Метеор" ТТРД Jumo 004 на испытаниях в США Серебряная птица
9 мая 1946 г., авиабаза Берлин-Гатов. Вдоль стройных рядов Ме.262, движется кортеж из лимузинов «Майбах» - сам Герман Геринг будет присутствовать при запуске «Америка-бомбера». В свете прожекторов видна огромная эстакада – сплетение стальных ферм берет начало в восточной части полигона, и стремительно уходя ввысь, упирается в пасмурное небо на Западе. Туда, где за горизонтом раскинулась ненавистная Америка. На эстакаде установлен орбитальный корабль с разгонным блоком. Через мгновение, огнедышащая упряжка из 5 двигателей суммарной тягой 600 тонн сорвут с места космический аппарат, как ураган срывает рекламные щиты, и унесет его в бархатную черноту космоса. С точки зрения инновации, бомбардировщик доктора Зенгера мог стать хорошим сюжетом для научно-фантастического романа. Просто красивая идея-мечта. Аппарат Зенгера не более реалистичен, чем звездолет из романа «Туманность Андромеды» - при кажущейся практичности, не было проведено никаких детальных расчетов. Кригсмарине
30 апреля 1945 года в боевой поход вышла подводная лодка U-2511 под командованием аса А.Шнее (за свою карьеру потопил 21 судно). В районе Фарерских островов лодка встретилась с группой британских крейсеров и эсминцев, но по каким-то причинам отказалась от атаки и вернулась в базу спустя несколько дней после объявления об окончании войны. "Вундервафля" Кригсмарине Примечание. Всего за годы войны Кригсмарине потеряли 768 подводных лодок. 28 000 немецких подводников навсегда канули в пучину океана. Фриц и дочь Рейна
Немцы действительно достигли огромных успехов во всем, что касается ракетной техники (пожалуй это единственная область где они преуспели) Кроме известных «Фау-1» и «Фау-2», в фашистской Германии активно шла разработка противокорабельных ракет и управляемых авиационных бомб «Фриц-Х» и «Хеншель-293», управляемая ракета «воздух-воздух» Х-4, а также 3 типа зенитных ракетных комплексов «Вассерфаль» (нем. водопад), «Шметтерлинг» (нем. бабочка) и «Рейнтохтер» (нем. дочь Рейна). Наибольшего успеха добились управляемые бомбы - их применение стало причиной гибели десятков кораблей и только тотально превосходство союзников в воздухе позволило избежать большого погрома в дни высадки в Нормандии. Железный капут
«Если вы про «Kоролевский Тигр», то я не вижу никаких реальных усовершенствований - более тяжелый, менее надежный, менее маневренный.» - из книги «Тигры в грязи», автор Отто Кариус (один из лучших танковых асов, на его счету более 150 уничтоженных единиц бронетехники). Сверхтяжелый танк Maus массой 188 тонн. Апофеоз маразма. Тяжелый танк ИС-3. Как должно выглядеть супероружие
Результаты расследования
Ограбив десятки стран и народов, арийцы-уберменши, не создали ни одного революционного образца техники, ничего принципиально нового и необычного. Все проекты «супероружия», в лучшем случае, имели сомнительную боевую ценность, а в худшем, представляли собой набор нереалистичных фантазий. На самом деле, в начале войны немцам удалось создать ряд удачных образцов оружия, на порядок превосходивших по эффективности оружие всех их противников. Пикирующий бомбардировщик Юнкерс-87 «Штука», тяжелый танк «Тигр» - несмотря на свою сложность и высокую стоимость это была мощная, хорошо защищенная и маневренная машина. Хорошие самоходные артиллерийские установки на базе средних танков – Штуг III, Штуг IV, Хетцер (на базе чешского танка), Ягдпантера… Выдающимися достижениями немецких конструкторов стало создание единого пулемета MG34 и промежуточного патрона 7,92х33 для первой штурмовой винтовки. Совершенно простое и гениальное оружие «Панцерфауст» стоило жизни тысячам танков. Как вы могли заметить, в этом списке нет никакого «вундерваффе» - самые обычные образцы вооружения, которые при качественном исполнении и грамотном применении превратились в шедевры. 1
/
5 ✪ Вундерваффе. Wunderwaffe. ✪ Фантастическое оружие Третьего рейха (улучшенная версия) ✪ Необычное оружие Третьего рейха. Часть 4 ✪ Wunderwaffe: Schlachtschiff H-45 / Чудо-оружие: Линкор Н-45 ✪ Необычное оружие Третьего рейха. Часть 2 К концу войны немецкие учёные, инженеры и технологи сделали ряд предположений о главных направлениях развития военной техники будущего, в некоторых случаях сумев сделать своеобразный эскиз вооружений и армий конца XX века . Сам термин вундерваффе
изобретён не конструкторами-оружейниками, а пропагандистами Имперского министерства пропаганды Геббельса . Делалось это в большей мере для достижения психологического эффекта, поддержания боевого духа войск и подавления панических настроений среди населения. Признанным на Западе экспертом по изучению вундерваффе
является журналист Игор Витковский
, среди книг которого есть и «Правда о вундерваффе» . Применение нацистами реактивных истребителей в конце войны и в самом деле затруднило действия авиации Союзников. Однако в Германии в 1942-1945 выпущено было небольшое количество этих истребителей (около двух тысяч), для которых к тому же остро не хватало: во-первых пилотов, а во-вторых топлива. Поэтому их применение носило ограниченный характер. Германские реактивные самолеты также страдали от множества технических проблем, которые успешно разрешить толком не удалось. В то же время, реактивные истребители США и Великобритании (такие как Lockheed F-80 Shooting Star и De Havilland DH.100 Vampire , соответственно) в 1945 году уже были запущены в серийное производство и могли эффективно парировать германскую угрозу. Следует отметить, что уже в начале 1945 года немецкие турбореактивные двигатели почти вдвое уступали по мощности британским и американским, что ставило немецкую реактивную авиацию априори в проигрышное положение. Применение ручных гранатомётов нанесло огромные потери бронетанковым войскам антигитлеровской коалиции, особенно при штурме городов. Массированное применение новых ОВ могло дать выигрыш в тактических операциях, а в случае применения таких ОВ в боеголовках баллистических ракет могло бы в случае успеха принести отдельные политические выигрыши. Тем не менее, ввиду низкой вероятности достижения значительного эффекта с помощью этого капризного оружия, а также значительного превосходства Союзников в стратегической авиации, обладавшей широкими возможностями доставки ОВ на территорию Германии, любая мыслимая химическая война была бы невыгодна для Германии: во-первых сколь-либо значительного военного результата это не дало бы, а вот ответные действия Союзников были бы ещё сильнее. Косвенным подтверждением является работа немецких ученых в программе обогащения урана в СССР и разработка ими полного процесса обогащения урана (центрифугированием) . Однако следует заметить, что в Германии эти проекты всерьёз начали рассматривать лишь в середине войны, и во-первых финансировались они крайне скудно, а во-вторых в Германии не было необходимых запасов урана ; к тому же некомпетентная нацистская верхушка «прохлопала» шанс обзавестись ЯО в принципе, не веря в возможность его создания. Шпеер писал, что в связи с введением эмбарго на поставки вольфрама из Португалии летом 1943 года уран использовался в производстве сердечников бронебойных подкалиберных снарядов . Официально проект атомной бомбы был свёрнут осенью 1942 года , но учёные продолжали разработку ядерных корабельных реакторов . В 1945 году немцы вплотную приблизились к созданию реактора (на три года позднее американцев), но немецкая экспериментальная установка так и не заработала. Согласно заявлениям немецкого исследователя ядерных проектов Третьего Рейха Райнера Карльша, весной 1945 года нацисты не только изготовили, но и опробовали своё ядерное оружие, взорвав экспериментальные заряды на балтийском острове Рюген . В интервью «Комсомольской правде » он сказал следующее: Они [нацисты] называли бомбу «Вундерваффе», что значит «чудо-оружие». Её взрыв привел к тотальным разрушениям в радиусе пятисот метров. Погибли многие сотни военнопленных, на которых, собственно, и испытывали бомбу. Данная малоправдоподобная версия была опровергнута немецкими исследователями в 2006 году, которые не обнаружили признаков радиоактивности ни в одном из названных мест. . Существуют предположения, что в конце Второй мировой войны испытывалось подземно-подводное боевое средство Midgard-Schlange («Змей Мидгарда»). Применение «Змея Мидгарда» в проектах представлялось как стратегическое средство для вывода из строя портов Великобритании [
] . Основными причинами поражения Германии в войне прежде всего являются: скептическое отношение к научно-техническому прогрессу, выдавливание за рубеж и истребление в ходе различных репрессий видных специалистов в технике и военном деле, нечеловеческая жестокость в отношении народов на оккупированных территориях, что повлекло за собой яростное партизанское сопротивление, иллюзорные надежды на «молниеносную войну» против СССР и победу в течение нескольких месяцев, вообще недооценка противников по идеологическим причинам и неготовность драться насмерть: тотальная милитаризация экономики Германии была выполнена лишь в середине 1943 года, в то время как СССР успешно завершил её в первой половине 1942-го года. К слову, в самом сериале, главный герой - майор, барон фон Швальцкопф XII - практически в каждой серии опробует очередное секретное оружие кайзера на своих подчинённых.6.2 Модули
7 Классы и монады
7.1 Классы
7.2 Ввод-вывод
8 Примеры
Заключение
Список использованных источников
Базовые типы Haskell
Базовые типы языка Haskell - это:
Числа
Логические величины
Символы
Списки
Упорядоченные множества (tuples)
Функции
Целые:
Integer (-∞,∞)
Int (-2^31, 2^31-1)
В прелюдии (стандартной библиотеке) определенно много полезных функций для целых чисел, в том числе, и преобразование в число с плавающей точкой (fromInt и fromInteger)
Float (7 знаков после запятой)
Double (16 знаков после запятой)
Bool (True | False)
Операции конъюнкции, дизъюнкции и отрицания (&&, ||, not)
Char (’a’)
И функции Char в Int и Int в Char (ord, chr)
Списки могут быть разные:
- список целых чисел
- список символов (строка)
[] - массив
- это список функций
и т. д.
Main> head
1
Main> tail
Main> length
2
Main> reverse
Main> 0:
Main> - строка приглашения в консоли компилятора ghci
«:» - операция присоединения элемента к списку.
Примеры:
(2.4, ”cat”) (Float, )
(’a’, True, 1) (Char, Bool, Int)
(,sqrt) (, Float->Float)
(1, (2, 3)) (Int, (Int, Int))Функции
Функция, в современной математике, это закон соответствия, который сопоставляет каждому элементу x из данного множества A один единственный (или ни одного) элемент y из множества B.
Haskell, по своему назначению, это, прежде всего, язык математиков, поэтому синтаксис тут максимально точно соответствует этому определению.
Пример:
square:: Integer -> Integer
square x = x*x
Как вы, наверное, догадались, это функция возведения числа в квадрат. Разберем её подробно:
Имя_функции:: область_определения - > область _значений
square:: Integer -> Integer
Тут следует сказать, что в Haskell совсем необязательно всегда объявлять функцию. В ряде случаев интерпретатор и так поймет какие у данной функции области определения и значения. Однако, опускать объявления - моветон.
Имя_функции параметры = правило_вычисления
square x = x*x
e:: Float
e = exp 1.0
Спасибо janatem за разъяснения ().
abcFormula:: Float -> Float -> Float ->
abcFormula a b c = [
(-b+sqrt(b*b-4.0*a*c))/(2.0*a),
(-b-sqrt(b*b-4.0*a*c))/(2.0*a)
]
-- находит корни уравнения ax^2+bx+c=0
Определения функций с альтернативами
Как и в любом языке, в Haskell есть конструкции ветвления.
Разберем их на примере функции abs (модуль).
If … then … else …
abs1 x = if x>=0 then x else -x
abs2 x = case x>=0 of
True -> x
False -> -x
abs3 x | x>0 = x
| x<0 = -x
| otherwise = 0
Прямую черту следует читать, как: «при».
Читаем: «Функция abs3, с входным параметром x, при x>0 принимает значение x, при x<0 принимает значение -x, и в любом другом случае принимает значение 0».
Конечно, мы могли записать все с помощью двух охранных выражений, но я записал три, что бы было понятно, что их может быть сколько угодно.
Otherwise в прелюдии определен очень просто:
otherwise:: Bool
otherwise = True
То есть, можно спокойно написать вместо «otherwise» «True», но это, опять же, моветон. Сопоставление с образцом
Один из наиболее распространенных и эффективных приемов в Haskell - это сопоставление с образцом. Вместо параметра мы можем подсунуть функции пример того, как должен выглядеть параметр. Если образец подошел функция выполняется, если нет - переходит к следующему образцу. Например, определение факториала через рекурсию с помощью образцов:
fact:: Integer -> Integer
fact 0 = 1
fact n = n * fact (n-1)
Тоже самое, но, с помощью охранных выражений:
fact:: Integer -> Integer
fact n | n==0 = 1
| n>0 = n*fact (n-1)
Есть очень распространенный образец для списка: (x:xs). X - обозначает первый элемент, XS - остальной список (кроме первого элемента). «:» - операция присоединения элемента к списку. Примеры из прелюдии:
head:: [a] -> a
head (x:_) = x
head = error "Prelude.head: empty list"
tail:: [a] -> [a]
tail (_:xs) = xs
tail = error "Prelude.tail: empty list"
Функция head принимает на вход список чего угодно [a] и возвращает первый элемент этого списка. Функция tail принимает на вход список чего угодно [a] и изымает из этого списка первый элемент.
«_» - означает, что данный элемент нас не интересует.
А еще мы знаем, что среди руин Третьего Рейха не было обнаружено ни одного действующего ядерного реактора. Руководитель немецкого атомного проекта Вернер Гейзенберг (лауреат Нобелевской премии 1933 г.) признавал, что немецкие ученые не имеют понятия о технологии получения оружейного плутония. Зенитные супер-ракеты «Вассерфаль» не сбили ни одного самолета, а немецкие сверхтяжелые танки навсегда остались в мировой , как результат победы техники над здравым смыслом. «Вундервафли», одним словом.
После победы, союзникам по антигитлеровской коалиции достались богатые трофеи. В том числе – фантастические технические новинки, предметы из будущего. Во многих конструкциях начисто игнорировались законы природы, единицы «вундерваффе» успели принять участие в боевых действиях, доказав свою полную несостоятельность перед менее революционной, но хорошо отлаженной и запущенной в серийное производство техникой союзников. Однако, сам факт существования подобных проектов поражал и наводил на мысль, что Третий Рейх был близок к революционному прорыву в технологиях. Миф о великих достижениях фашистов был с жадностью подхвачен прессой, умевшей делать деньги на нездоровых сенсациях. 
Впервые с реактивным немецким истребителем союзники встретились в 25 июля 1944 года: в тот день Me.262 безуспешно атаковал разведывательный «Москито» Королевских ВВС. Примечательно, что через два дня – 27 июля 1944 г., свой первый боевой вылет совершили реактивные «Глостер - Метеор», перехватив над Ла-Маншем крылатую ракету «Фау-1». Британский самолет оказался намного совершеннее своего немецкого аналога, «Метеоры» приняли участие в Корейской войне и эксплуатировались по всему миру до конца 70-х годов. Но публика любит громкие сенсации – вся слава досталась «Мессершмитту». 
Кроме Ме.262, авиапромышленность Германии подготовила множество проектов реактивных самолетов:
- блиц-бомбардировщик Арадо-234
- «народный истребитель» Хеншель-162 «Саламандер»
- бомбардировщик с крылом обратной стреловидности «Юнкерс-287»
- «летающее крыло» братьев Хортен Ho.229
Единственной проблемой было отсутствие надежных и тяговитых реактивных двигателей. В наличии у немцев было только два типа силовых установок: BMW 003 и Jumo 004 – на них держались все проекты «супер-самолетов». Оба были предельно пожароопасны и не обеспечивали требуемых летных характеристик. А без нормальных двигателей все планы становились бессмысленными - и действительно, большинство немецких «супер-самолетов» не вышли за рамки экспериментальных моделей.
За 8 минут «Америка-бомбер» поднялся на высоту 260 километров и на скорости 22 тыс. км/ч взял курс на Нью-Йорк. Через 3500 километров от точки старта суборбитальный бомбардировщик делает первое снижение, и, оттолкнувшись от плотных слоев атмосферы на высоте 40 км, снова поднимается на низкую околоземную орбиту. Через час радисты услышали прерывающийся голос пилота: «Мой фюрер, вашим именем!.. территория США!..пикирую!.. прощайте, умираю с честью!..». Огненный метеорит прочертил небосклон и врезался в небоскребы Манхэттена… 
С первого дня войны руководство Рейха скрежетало зубами в бессильной ярости, пытаясь найти средство для нанесения ударов по Нью-Йорку, Вашингтону, другим крупным городам США, военно-промышленным комплексам Урала и Сибири – недостижимым целям для немецкой авиации. «Оперативно-тактический комплекс «Фау-2», обладая дальностью порядка 300 км, был бесполезен для решения этой задачи. Над созданием межконтинентальной баллистической ракеты по проекту А-9/А-10 Вернер фон Браун работал на протяжении всей войны, увы, технологический уровень немецкой промышленности тех лет не позволял создавать что-либо крупнее «Фау-2», а регулярные бомбардировки научных центров и ракетного полигона Пенемюнде еще более тормозили работу. Не оправдал надежд и четырехмоторный дальний бомбардировщик Та.400 – по всем расчетам он не имел шансов достигнуть побережья Америки.
Последней надеждой фашистского руководства стал суборбитальный бомбардировщик доктора Зенгера. Феерический проект даже сейчас поражает воображение. 
«100 тонн сплошного огня! Самолет забрасывается своим адским двигателем на страшную высоту и падает на сверхзвуке вниз, но не врубается в атмосферу, а рикошетит об нее, как плоский камень от поверхности воды. Ударяется, подскакивает и летит дальше! И так два или три раза! Сильная идея!» - рассказывал о немецком проекте «Silbervogel» конструктор Алексей Исаев, создатель первого отечественного ракетоплана БИ-1. К счастью, полная нереализуемость этого проекта была понятна даже самым упертым шизофреникам из тогдашнего руководства Рейха.
Так закончился первый и последний боевой поход подлодок типа XXI, более известных, как «Электролодка». Несмотря на свое совершенное радиоэлектронное оборудование и аккумуляторные батареи нового типа, позволявшие двигаться много часов в подводном положении со скоростью 15 узлов, «Электролодка» в реальном бою испугалась эсминцев и охотников за подводными лодками. Иногда приводится оправдание, что «Электролодка» U-2511 отказалась от торпедной атаки в связи с благими намерениями – 4 мая 1945 года адмирал Дениц отдал приказ о прекращении боевых действий. Может быть и так… хотя эта история имеет трагикомическое продолжение: десять «Электролодок», пытавшихся прорваться в Норвегию в начале мая 1945 года были обнаружены и потоплены авиацией союзников. Не помогли немцам их новейшие разработки…Проблему мог решить только ядерный реактор на борту лодки, но до его создания немцам требовалось еще несколько лет.
Немецкие подводники добились потрясающих успехов в годы Второй мировой – на их долю пришлось 50% морских побед. Всего подводные убийцы потопили 2759 судов суммарным тоннажем 14 миллионов брутто-регистровых тонн и 123 военных корабля (из которых 60 были нефтеналивными судами, тральщиками и траулерами, формально приписанными к военному флоту).
Здесь возникает интересная ситуация: в первые годы войны немецким подводникам, имевшим всего 50-60 лодок в строю, удавалось топить судов противника общим водоизмещением под 2 миллиона тонн. В 1944 году, имея 500 боеспособных лодок, Кригсмарине с огромным трудом удалось потопить судов общим водоизмещением «всего» на 700 тысяч тонн! При этом в 1940 году немцы потеряли 21 подводную лодку, в 1944 они потеряли за год 243 субмарины! Похоже, полсотни эскортных авианосцев, постоянные воздушные патрули и британский гидролокатор Asdic стали более грозным «супер-оружием», чем все передовые разработки германских кораблестроителей.
Управляемая ракета «воздух-воздух» была запущена в серийное производство и, теоретически, могла быть использована в последние недели войны, хотя об этом оружии нет никаких достоверных упоминаний. 1000 ракет этого типа нашли в подземном хранилище.
Очень интересен проект «Шметтерлинг» - это не зенитная ракета, а целый беспилотный летательный аппарат (БПЛА) с дальностью полета 35 километров. Однако, немцам так и не удалось создать главного – точной и надежной системы управления. Попытки наведения ракет по акустическому шуму винтов и тепловому излучению полностью провалились. В результате немцы остановились на радиолокационном методе наведения при помощи двух наземных РЛС, но для доработки системы уже не хватило времени. Кстати, при испытаниях, проведенных в 1944 году, из 59 пусков «бабочек» 33 оказались аварийными. Закономерный результат – ни один самолет не был сбит немецкой зенитной ракетой.
Действительно, немецкое танкостроение страдало похожей проблемой, что и авиационная промышленность. Немцы могли создать любой проект:
- сверхтяжелый танк «Лев» со 105 мм орудием, масса 76 тонн
- зенитный танк Е-100 «Аллигатор» с двумя спаренными (!) 88 мм орудиями
- тяжелый истребитель танков «Ягдтигр» со 128 мм орудием
Единственная проблема была в отсутствии подходящей трансмиссии и подвески, положение усугублялось неумеренным ростом массы боевых машин – немецкие танкостроитель до конца войны так и не научились создавать компактные конструкции и экономить силы и ресурсы.
Из всего вышеперечисленного «вундерваффе» в мелкосерийное производство была запущена только тяжелая САУ «Ягдтигр» на шасси одноименного танка (выпущено от 70 до 79 машин), ставшая самым тяжелым типом немецкой бронетехники. 75 тонн – такую массу с трудом выдерживало даже мощное шасси «Тигра», машина была явно перегружена и даже колоссальная огневая мощь («Ягдтигр» пробивал танк «Шерман» в лоб с дистанции 2500 м) не могла спасти ситуацию. «Ягдтигр» разваливался прямо на глазах. После короткого марша разбалансировалось орудие, ломалась подвеска, не выдерживала колоссальных нагрузок коробка передач. Забавно, но в каждой машине было изначально предусмотрено 2 заряда взрывчатки для уничтожения неисправной САУ. Немцы правильно догадались, что «Ягдтигр» не выдержит ни один мост, поэтому сразу же оснастили все машины шнорхелем для движения по дну рек. Настоящая «вундервафля».
Война – двигатель прогресса. И немецкая промышленность, в сущности, делала то, что должна была делать. Другой вопрос, что темпы развития военно-промышленных комплексов стран Антигитлеровской Коалиции превышали темпы развития ВПК фашистской Германии. Немцы научились делать сложные, но бесполезные ракеты. Умели производить качественную оптику, гироскопы и радиоэлектронику. Было хорошо развито двигателестроение (реактивные моторы не в счет), на высоком уровне стояла авиационная промышленность, электротехника, химическая промышленность; строилось огромное количество подводных лодок. У немцев была потрясающая организация и работоспособность, все немецкие изделия отличало высокое качество и внимание к мелочам. Но! Здесь нет ничего фантастического - так и должна была работать промышленность высокоразвитой индустриальной страны.Энциклопедичный YouTube
Субтитры
История
Примеры
Реактивные самолеты
Оружие пехоты
Реактивные и динамореактивные противотанковые ручные гранатомёты
Стрелковое оружие
Ручные гранаты, мины и фугасы
Попытка создания ядерного оружия
Прочее
Подземное боевое средство
В массовой культуре
См. также