Сборник задач по курсу «Функциональное программирование»

Московский государственный технический университет 
имени Н.Э. Баумана 
 
А.В. Дубанов 
 
Сборник задач по курсу 
«Функциональное программирование» 
 
Учебное пособие 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1 

УДК 004.42 
ББК 32.973-018 
Д79
 
Издание доступно в электронном виде на портале ebooks.bmstu.ru 
по адресу: http://ebooks.bmstu.ru/catalog/194/book1139.html 
 
Факультет «Информатика и системы управления» 
Кафедра «Теоретическая информатика и компьютерные технологии» 
 
Рекомендовано 
Редакционно-издательским советом МГТУ им. Н.Э. Баумана 
в качестве учебного пособия
 
Рецензент 
канд. техн. наук, доцент П.Г. Ключарёв 
 
 
Дубанов, А. В.
 
Д79
Сборник задач по курсу «Функциональное программирование» : учебное пособие / А. В. Дубанов. — Москва : Издательство МГТУ им. Н. Э. Баумана, 2015. — 30, [2] с. 
 
 
ISBN 978-5-7038-4092-4  
Издание содержит задачи, охватывающие широкий спектр 
разделов и парадигм программирования. Существенное внимание уделено синтаксическому и лексическому анализу и построению трансляторов. Для решения задач в качестве основного 
выбран язык Haskell. Рассмотрено также программирование на 
языке Scheme. 
Для магистрантов, обучающихся по направлению подготовки «Прикладная математика и информатика» и изучающих дисциплину «Функциональное программирование». 
 
 
          УДК 004.42 
           ББК 32.973-018 
  
 
 
 
 
 
  
 
                                                                                 МГТУ им. Н.Э. Баумана, 2015 
                                                                                 Оформление. Издательство 
ISBN 978-5-7038-4092-4                                           МГТУ им. Н.Э. Баумана, 2015 
2 

ПРЕДИСЛОВИЕ 
В сборнике представлены задачи, предназначенные для магистрантов, обучающихся по направлению подготовки  «Прикладная 
математика и информатика». В курсе «Функциональное программирование» в качестве основного выбран язык Haskell, наиболее 
полно отражающий парадигмы и отличающийся математической 
строгостью. Существенное внимание уделено сильным сторонам 
языка Scheme как представителя языков семейства Lisp. 
Сборник задач по курсу имеет практическую направленность. 
Рассмотрено функциональное программирование, в первую очередь, как средство для быстрого прототипирования приложений. 
Включены задачи, традиционно решаемые в ходе изучения других 
курсов (алгоритмы и структуры данных, методы оптимизации, 
машинная графика, сетевые технологии) в рамках императивной 
парадигмы программирования. Цель введения таких задач — показать, что их решением может быть краткий, выразительный, математически строгий и легко модифицируемый код на функциональном языке программирования. 
Многие задания носят характер учебно-исследовательских работ, некоторые из них предполагают обсуждение возможных решений на семинарах. Ряд заданий связан с построением решения 
путем сочетания слабо связанных модулей, что создает предпосылки для совместной работы группы студентов. Значительное 
внимание уделяется вопросам трансляции программ как подготовке к курсу «Конструирование компиляторов». 
Автор выражает благодарность студентам кафедры «Теоретическая информатика и компьютерные технологии» МГТУ 
им. Н.Э. Баумана, принимавшим активное и творческое участие 
в апробации ряда наиболее сложных задач: А. Выборнову, 
И. Дрогунову,  Р. Левентову, А. Мокрову, Н. Русначенко, Н. Юрченко. 
3 

ТЕМА 1. ОСНОВЫ ЯЗЫКА HASKELL 
Задание 1.1. Вычисления по рекурсивным формулам 
Напишите функцию для нахождения наибольшего общего делителя двух произвольных целых чисел (например, с помощью  
алгоритма Евклида). Сравните результаты работы этой функции с 
результатами встроенной функции gcd. 
Напишите функцию для проверки простого  целого числа методом перебора делителей. По возможности постарайтесь избежать вычисления квадратного корня. 
Напишите функцию наименьшего общего кратного двух целых 
чисел. Сравните результаты работы этой функции с результатами 
встроенной функции lcm. 
Напишите функцию быстрого возведения числа в неотрицательную целую степень n (вычислительная сложность — О(log n)). 
Задание 1.2. Интервальная арифметика 
Реализуйте библиотеку функций для операций с интервальными 
величинами, т. е. c величинами, значения которых известны только 
приближенно и определен конечный интервал, к которому принадлежат эти значения [1]. Подробно ознакомиться с интервальными вычислениями можно, например, в книге [2]. 
Предложите структуру данных для хранения величин, представленных вещественными интервалами [a,  b], где a ≤ b. Реализуйте функции сложения, вычитания, умножения и деления интервальных величин. Обеспечьте возможность работы с величинами, 
заданными в виде x
̄  ± δ%, где x
̄  — среднее; δ — отклонение от 
среднего, %. Для этого определите функции для преобразования 
такой величины к интервалу [a,  b] и обратно. Определите предикат для проверки, содержит ли интервал нуль. В каких случаях 
может потребоваться такая проверка? 
Примените предложенные вами функции для вычисления сопротивления цепи из двух параллельно включенных резисторов с 
помощью эквивалентных формул: 
1
2
1
2
,
R R
R
R
R


 
4