Haskell

HaskellTasks

Домашние задания курса по Хаскелю

Задание 1

Написать функцию hasPair :: Integer -> Bool, которая проверяет, есть ли в десятичной записи заданного числа две подряд идущие одинаковые цифры.

Например, hasPair 1001 => True, а hasPair 1212 => False.

Решение

Задания 2,3

Задание 2

Назовем “производной” элемента числового списка разность между следующим в списке и данным элементом. Производной последнего элемента будем считать 0.
Например, список производных элементов списка [3,1,2,5,7,6] будет список [-2,1,3,2,-1,0].
Написать функцию maxDeriv :: Real a => [a] -> Int, которая в заданном списке числовых элементов находит индекс элемента с максимальной “производной”.
Например, в вышеприведенном списке таким индексом будет 2, поскольку элемент с этим индексом имеет максимальную производную - 3.

Задание 3
В заданной строке символов будем считать числом произвольную последовательность цифр, слева и справа от которой не находится цифра. Написать функцию maxNumber :: String -> Integer, выдающую числовое значение самого большого “числа” в строке.
Например, результатом вызова функции с аргументом "0xFF55 00012 -100 19" должно быть 100. Если чисел в строке нет совсем, то это ошибка аргумента.

Решение

Задание 4

Написать функцию preHigher :: Ord a => [a] -> [Int], которая по заданному списку элементов выдает список индексов тех из них, которые строго меньше следующего.

Например, в числовом списке [1, 2.2, 2.1, 3.14, 2.7, 1.618] числа, меньшие следующего в списке - это 1 и 2.1, поэтому вызов preHigher [1, 2.2, 2.1, 3.14, 2.7, 1.618] должен выдать список [0, 2] - список индексов этих элементов.

Решение

Задание 5

Во задачах всех вариантов используется представление словаря в виде префиксного дерева (Trie, бор) без корневого элемента:

data Trie = Empty | Node Char [Trie]
type Dictionary = [Trie]
Например, словарь, содержащий слова “bit”, “byte”, “bite”, “site” будет представлен следующим образом (с точностью до порядка элементов списков):
[Node 'b' [Node 'i' [Node 't' [Empty,
Node 'e' [Empty]]],
Node 'y' [Node 't' [Node 'e' [Empty]]]],
Node 's' [Node 'i' [Node 't' [Node 'e' [Empty]]]]]

Написать функцию listWords :: Dictionary -> [String], которая выдает список всех слов в заданном словаре.

Решение

Задание 6

Задание 1 В первой задаче каждого варианта требуется выбрать представление и определить тип данных

data Map key value = ..
для которого требуется реализовать стандартный набор методов для манипуляций с “отображением”:

• get :: Eq k => k -> Map k v -> Maybe v
• put :: Eq k => (k, v) -> Map k v -> Map k v
• remove :: Eq k => k -> Map k v -> Map k v
• keys :: Map k v -> [k]
• values :: Map k v -> [v]

Все вышеперечисленные функции имеют обычный для операций над отображениями смысл:

• найти значение по ключу (get)
• добавить или заменить существующую пару <ключ,значение> (put)
• удалить пару с заданным ключом (remove)
• выдать множество (список) всех ключей (keys)
• выдать список всех значений (values)

Не следует сильно заботиться об эффективности представления и скорости работы функций, например, подойдет реализация в виде списка пар.

Кроме этого в каждом из вариантов требуется определить дополнительную функцию.

Написать функцию removeBy :: (k -> Bool) -> Map k v -> Map k v, которая удаляет из заданного отображения те пары, ключи которых удовлетворяют критерию, заданному первым аргументом функции.
Например, вызов removeBy (<0) m удалит из отображения m те пары, ключи которых меньше нуля.

Задание 2

Во второй задаче биномиальная куча определяется как список биномиальных деревьев, упорядоченный по возрастанию степеней.
Как и положено в куче, все потомки каждого элемента больше или равны этому элементу.
type BinHeap e = [BinTree e]
data BinTree e = BinTree e [BinTree e]

Аргументы типа данных BinTree представляют собой компоненты узла биномиальной кучи: содержащееся в узле значение и список поддеревьев.
Написать функцию replace :: Ord e => e -> BinHeap e -> BinHeap e, которая меняет в куче минимальное значение на заданное первым аргументом новое значение и выдает модифицированную кучу.

Решение

Ход конем

Написать функцию, находяющую цикл коня, проходящего все поля шахматной доски и возвращающийся на исходную позицию (полный перебор)

Решение

Задание 7

Строка содержит натуральные числа, разделенные знаками '+', '-', '', например, "12+232".

Написать функцию addPars :: String -> String, которая добавляет в строку круглые скобки таким образом, чтобы результат вычисления выражения стал максимальным.
Например, для приведенной строки "12+23*2" результатом будет "((12+23)*2)" (с точностью до внешней пары скобок).
Порядок выполнения операций в результирующей строке должен определяться только скобками, приоритеты операций не учитываются. Функция должна выдавать результат за приемлемое время для строки, содержащей 10-12 операндов.

Решение