Задание на третью лабораторную работу достаточное простое, сложность может возникнуть только у программистов на хаскелле, где генерация случайных значений немного отличается от привычного System.Random, а на семинарах мы рассматриваем только примеры на языке F#.
- Тип данных для представления JSON-объектов (разбирали на семинаре). Будем ещё его называть деревом, так как по сути это оно и есть, и задания больше относятся к работе с деревом, нежели с JSON
- Разбор JSON-строки в объект (разбирали на семинаре)
- Функцию обработки древовидной структуры в соответствии с вариантом задания
- Функцию генерации случайного JSON-объекта
- Сериализацию объекта обратно в строку
Для получения последовательности случайных чисел можно использовать генератор случайных чисел System.Random
Для получения последовательности случайных чисел можно использовать генератор псевдослучайных чисел
типа StdGen и функцию random, или функции получения случайных значений из внешнего мира randomIO, randomRIO
и т.д.
В первом случае сложность может возникнуть в правильной передаче нового состояния вашего генератора
дальнейшим вычислениям. В этом случае удобно обернуть генерирующие функции в монаду State, маленький пример есть в шаблоне.
Во втором случае придётся работать внутри монады IO, что может быть неприятно.
Для многих заданий полезно причислить тип JSON к классу типов Monoid
Нужно будет написать тесты, в которых проверить работу программы на нескольких модельных примерах, показывающих правильность реализованного алгоритма, а также на случайно сгенерированном дереве.
JSON-объекты представлены следующими типами (json.org):
- объект, содержащий пары ключ - значение (другой JSON-объект)
- массив из JSON-объектов
- притивные типы: null, number, string, true, false
Глубиной вершины дерева называется длина пути в эту вершину из корня. Глубиной (высотой) дерева называется максимальная глубина его вершин. Листом или терминальной вершиной дерева называется вершина, не имеющая поддеревьев. Степенью вершины называется число исходящих из неё ветвей. Степенью дерева называется максимальная степень его вершин. Шириной уровня дерева называется число вершин на данной глубине. Шириной дерева называется максимальная ширина по всем уровням. Подобие деревьев отличается от равенства возможным несовпадением значений данных, хранящихся в узлах.
- Найти количество элементов во всех массивах
- Построить список, содержащий все ключи в объектах дерева
- Определить ширину дерева
- Определить максимальную глубину у числовых элементов
- Определить глубину дерева
- Определить степень дерева
- Определить число нетерминальных вершин дерева (объекты и массивы)
- Определить число вершин дерева, степень которых совпадает со степенью дерева
- Определить уровень дерева, на котором находится максимальное число вершин
- Определить значение листа дерева (примитвный тип), имеющего минимальную глубину
- Определить значение нетерминальной вершины дерева с максимальной глубиной
- Проверить, все ли числа в JSON находятся в заданном диапазоне
- Узнать, подобны ли два JSON-объекта
- Проверить монотонность возрастания ширины уровня дерева
- Проверить монотонность возрастания длины массивов в зависимости от уровня их вложенности
- Найти сумму всех чисел в JSON
- Проверить, находятся ли все числа на одном уровне
- Увеличить значения всех чисел в JSON на их уровень
- Увеличить на единицу значения листьев дерева, находящихся на нечётных уровнях
- Добавить произвольный примитивный элемент в дерево
- Найти количество вхождений элемента примитивного типа в дерево
- Удалить элемент примитивного типа из дерева
- Проверить, является ли дерево симметричным (равным своему отражению, объекты в JSON не отражаются)
- Проверить, является ли дерево самоподобным (подобным своему отражению, объекты в JSON не отражаются)
- Написать функцию, которая объединяет два JSON-объекта или JSON-массива
- Написать функцию, которая принимает JSON-объект и возвращает новый, где ключи — значения, а значения — ключи
- Написать функцию, которая принимает список ключей и проверяет, все ли из них есть в JSON
- Составить хеш: значение примитивного типа в JSON, сколько раз оно встречается
Так как задание изначально предполагало работу с примитивным деревом, некоторые варианты могут оказаться непонятными. Как обычно, если у вас появились какие-либо вопросы, обращайтесь на почту, или через issue. Приятно видеть, что многие вопросы вы решаете самостоятельно.