Try   HackMD

Haskell: ДЗ 1 – Базовые конструкции языка

Первое домашнее задание проверяет понимание базовых конструкций языка: списки, полиморфизм, паттерн-мэтчинг, алгебраические типы данных, классы типов. А также стандартные функции и интерфейсы. Обратите внимание, что задание соответствует материалу, который будет рассказан в темах со 2 по 4ю отсюда, поэтому на момент выполнения Вы можете не знать некоторых конструкций - это нормально. Они будут объяснены на следующих лекцих, что и позволит Вам узнать все необходимое для выполнения.

Задания разделены на блоки. Были предприняты некоторые усилия со стороны преподавателей, чтобы блоки соответстовали независимым частям лекций. Некоторые задания имеют усложнённые версии, которые необходимо выполнять дополнительно к базовой, но они также будут оценены дополнительными баллами.

Блок 1: Простые функции (однострочники)

Задание 1

Упорядочить по возрастанию переданную тройку элементов.



ghci> order3 (5, 2, 10)
(2, 5, 10)

Задание 2

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



ghci> smartReplicate [1,2,3]
[1,2,2,3,3,3]

Задание 3

Напишите функцию, которой передаётся список списков и некоторый элемент. Эта функция должна вернуть список только тех списков, которые содержат переданный элемент.



ghci> contains 3 [[1..5], [2,0], [3,4]]
[[1,2,3,4,5],[3,4]]

Задание 4

Требуется написать функцию, которая принимает строку, состоящую только из чисел, разделённых пробельными символами, и находит сумму всех чисел в этой строке. Тип функции должен быть String -> Int. В данном задании нужно считать, что переданная строка корректная.

ghci> stringSum "1 1"
2
ghci> stringSum "100\n\t-3"
97

Больше тестов ниже:

passTests = [ "1", "1 2 3", " 1", "1 ", "\t1\t", "\t12345\t", "010 020 030"
            , " 123 456 789 ", "-1", "-1 -2 -3", "\t-12345\t", " -123 -456 -789 "
            , "\n1\t\n3   555  -1\n\n\n-5", "123\t\n\t\n\t\n321 -4 -40"
            ]

mustFail  = ["asd", "1-1", "1.2", "--2", "+1", "1+"]

Блок 2: Паттерн-мэтчинг на списках

Задание 1

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

Задание 2

Требуется реализовать сортировку слиянием:

ghci> mergeSort [2, 1, 0, 3, 10, 5]
[0, 1, 2, 3, 5, 10]

Поместите следующий код в начале вашего модуля

import System.Random (newStdGen, randomRs)

randomIntList :: Int -> Int -> Int -> IO [Int]
randomIntList n from to = take n . randomRs (from, to) <$> newStdGen

чтобы тестировать вашу функцию в ghci следующим образом

ghci> example <- randomIntList 5 (-10) 10
ghci> example
[-8,1,-8,-5,-7]
ghci> mergeSort example
[-8,-8,-7,-5,1]

Для этого необходимо в зависимости добавить библиотеку random.

Блок 3: Добро пожаловать в фантастический мир алгебраических типов данных

В этом блоке разрешено использовать автоматический deriving только для Show. Остальные инстансы необходимо реализовывать самостоятельно.

Задание 1: Дни недели

Вы проектируете собственный фантастический мир. Эта задача не из лёгких. Для начала Вы решаете ввести время в ваш собственный мир, используя привычные дни недели.

Определите свой тип данных для Дней недели. Реализуйте следующие функции:

  1. nextDay: возвращает следующий за переданным день недели.
  2. afterDays: возвращает день недели, который наступит после заданного через переданное число дней.
  3. isWeekend: проверяет, является ли день недели выходным.
  4. daysToParty: выводит число дней, оставшихся до пятницы.

Задание 2: Проектирование замков

Основное задание

Преждем чем населить мир обитателями, Вы принимаете решение создать города в Вашем мире, потому что Вам всегда нравилось играть в Civilization. Необходимо определить типы данных для представления города:

  1. В городе может быть замок (а может и не быть).
  2. В городе может быть либо церковь, либо библиотека, а может не быть ничего, но не может быть двух эти зданий одновременно.
  3. В городе может быть несколько жилых домов, но должен быть как минимум один.
  4. В замке может сидеть лорд, а может и не сидеть.
  5. У города могут быть стены, но только тогда, когда в городе есть замок!
  6. В каждом жилом доме может жить от одного до четырёх человек.

Определите тип данных для города таким образом, чтобы в Вашем мире нельзя было в принципе создать города, не удовлетворяющие этому условию. После этого поддержите следующие функции по развитию городов:

  1. Построить замок, но только если в городе нет замка. Должна быть возможность понять, был ли построен новый замок в результате выполнения этой операции.
  2. Построить церковь или библиотеку, но только если в городе нет ничего из этого! Требования аналогично предыдущей функции.
  3. Постройка для новой семьи нового жилого дома, в который они въедут.
  4. Возможность лорду въехать в замок, но только если в городе есть замок, в котором нет лорда. Если лорд не смог въехать в замок, то необходимо сообщить, по какой именно причине он не смог это сделать.
  5. Построить стены в городе. Это очень сложное занятие, поэтому построить стены можно лишь тогда, когда в городе минимум 10 человек и есть лорд.

Задание 3: Натуральные числа

Чтобы экономика в городах могла развиваться, необходимо ввести в мир деньги, назначить цены за товары и услуги.

Базовое задание

Но сначала необходимо ввести некоторые операции по работе с натуральными числами, в которых будут выражаться деньги. Напомню, что натуральным числом является либо 0, либо какое-то натуральное число, увеличенное на 1. Этот тип данных представляется следующим образом:

data Nat = Z | S Nat

Реализуйте следующие операции (которые должны быть реализованы полностью самостоятельно):

  1. Сложение двух натуральных чисел.
  2. Умножение двух натуральных чисел.
  3. Вычитание натуральных чисел.
  4. Превращение целых чисел в натуральные и наоборот.
  5. Проверка натуральных чисел на равенство.
  6. Сравнение натуральных чисел.

Усложнённая версия

Дополнительно требуется реализовать следующие функции:

  1. Проверка натурального числа на чётность.
  2. Целочисленное деление натуральных чисел.
  3. Остаток от деления натурального числа на другое.

Задание 4: Растительность

Чтобы сделать Ваш мир более красочным и живописным, Вы решаете добавить в него растительность. Так как Вы программист, то единственный вид растительности, который Вам известен – двоичные деревья поиска.

Дерево имеет два конструктора:

  1. Лист дерева, не содержит данных.
  2. Узел дерева. Содержит список одинаковых значений и имеет двух детей.

При этом двоичное дерево называется двоичным деревом поиска если оно удовлетворяет следующему условию: значения всех элементов в левом поддереве меньше значения в узле, а значения элементов в правом поддереве больше значения в узле.

Реализуйте следующие операции с двоичным деревом поиска:

  1. Проверка дерева на пустоту.
  2. Подсчёт размера дерева (то есть числа элементов в нём).
  3. Поиск заданного элемента в дереве (используйте тот факт, что дерево является деревом поиска).
  4. Вставка нового элемента в двоичное дерево поиска. Если вставляемый элемент уже находится в дереве, то необходимо добавить его в список того узла, в котором этот элемент находится. Тут следует обратить внимание, что если в узле дерева есть список элементов, то этот список всегда непустой.
  5. Функцию fromList, которая создаёт дерево из списка элементов.
  6. Функцию, которая удаляет заданный элемент из дерева.

Блок 4: Сворачиваемся

Задание 1: Инстансы Foldable

В этом задании обязательно использовать расширение языка -XInstanceSigs и указывать типы функций в инстансах. При этом необходимо реализовать обе функции foldMap и foldr.

Основное задание

Реализуйте вручную инстансы Foldable для следующих типов данных:

  1. data Pair a = Pair a a
  2. data NonEmpty a = a :| [a]

Усложнённое задание

Прошло много времени, как Вы создали собственный мир… В исходном коде вашего мира появилось много типов данных и абстракций. Пришло время порефакторить предыдущий код. Для этого необходимо сделать тип данных Tree инстансом класса типов Foldable. Инстанс должен быть реализован таким образом, чтобы выполнялось свойство: toList . fromList ≡ sort.

Задание 2: Разбиваемся

Базовая версия

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

ghci> splitOn '/' "path/to/file"
["path", "to", "file"]

Стоит обратить внимание, что функция splitOn всегда возвращает непустой список элементов. Это должно быть отражено в типе. Пример приведён для обычного списка, хотя это решение не полностью корректное.

Усложнённая версия

Дополнительно реализуйте функцию (опять же, используя свёртку) joinWith, обратную splitOn. При этом Ваши реализации должны удовлетворять свойству:

joinWith x . splitOn x ≡ id.

ghci> joinWith '/' ["path", "to", "file"]
"path/to/file"

Стоит обратить внимание на то, что функция joinWith принимает непустой список.

Блок 5: Моноиды

Задание 1

Базовая версия

Напишите функцию, принимающую список списков внутри Maybe и возвращающую конкатенацию всех внутренних списков.

ghci> maybeConcat [Just [1,2,3], Nothing, Just [4,5]]
[1,2,3,4,5]

Усложнённая версия

Функция должна принимать произвольный набор Either, где и Left и Right содержат некоторые моноидальные элементы, и необходимо вернуть пару из результатов моноидального объединения отдельно элементов внутри Left и отдельно элементов внутри Right.

ghci> eitherConcat [Left (Sum 3), Right [1,2,3], Left (Sum 5), Right [4,5]]
(Sum {getSum = 8}, [1,2,3,4,5])

Задание 2

Базовая версия

Реализуйте инстансы алгебраических классов типов для следующих структур данных. Ваши инстансы должны удовлетворять законам для этих структур.

  1. Semigroup для data NonEmpty a = a :| [a].
  2. Semigroup для типа данных data ThisOrThat a b = This a | That b | Both a b.

Усложнённая версия

Дополнительно реализуйте следующие инстансы:

  1. Semigroup и Monoid для строк, объединяемых при помощи '.'.
ghci> Name "root" <> Name "server"
Name "root.server"
  1. Semigroup и Monoid для newtype Endo a = Endo { getEndo :: a -> a }.

Задание 3

Имеется следующий тип данных Builder для создания строк:

data Builder = One Char | Many [Builder]

Реализуйте инстансы классов типов Semigroup и Monoid для типа Builder. Реализуйте функцию создания билдера из строки:

fromString :: String -> Builder

Реализуйте функцию построения строки из билдера:

toString :: Builder -> String

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

Last changed by 
 
Илья Пересадин
0
1021
Published on HackMD