HaskellTasks

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

Задание 1 Написать функцию hasPair :: Integer -> Bool, которая проверяет, есть ли в десятичной записи заданного числа две подряд идущие одинаковые цифры. Например, hasPair 1001 => True, а hasPair 1212 => False. [Решение](/Ifmo-code/Haskell/Hw1.hs)
Задания 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. Если чисел в строке нет совсем, то это ошибка аргумента. [Решение](/Ifmo-code/Haskell/Hw2.hs)
Задание 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] - список индексов этих элементов. [Решение](/Ifmo-code/Haskell/Hw4.hs)
Задание 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], которая выдает список всех слов в заданном словаре. [Решение](/Ifmo-code/Haskell/Hw5.hs)
Задание 6 Задание 1 В первой задаче каждого варианта требуется выбрать представление и определить тип данных data Map key value = .. для которого требуется реализовать стандартный набор методов для манипуляций с “отображением”: Все вышеперечисленные функции имеют обычный для операций над отображениями смысл: Не следует сильно заботиться об эффективности представления и скорости работы функций, например, подойдет реализация в виде списка пар. Кроме этого в каждом из вариантов требуется определить дополнительную функцию. Написать функцию 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, которая меняет в куче минимальное значение на заданное первым аргументом новое значение и выдает модифицированную кучу. [Решение](/Ifmo-code/Haskell/Hw6.hs)
Ход конем Написать функцию, находяющую цикл коня, проходящего все поля шахматной доски и возвращающийся на исходную позицию (полный перебор) [Решение](/Ifmo-code/Haskell/KnightsBruteForce.hs)
Задание 7 Строка содержит натуральные числа, разделенные знаками '+', '-', '*', например, "12+23*2". Написать функцию addPars :: String -> String, которая добавляет в строку круглые скобки таким образом, чтобы результат вычисления выражения стал максимальным. Например, для приведенной строки "12+23*2" результатом будет "((12+23)*2)" (с точностью до внешней пары скобок). Порядок выполнения операций в результирующей строке должен определяться только скобками, приоритеты операций не учитываются. Функция должна выдавать результат за приемлемое время для строки, содержащей 10-12 операндов. [Решение](/Ifmo-code/Haskell/Hw7.hs)