Задание на третью лабораторную работу достаточное простое, сложность может возникнуть только у программистов на хаскелле, где генерация случайных значений немного отличается от привычного 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 не отражаются)
- Написать функцию, которая объединяет два JSON-объекта или JSON-массива
- Написать функцию, которая принимает JSON-объект и возвращает новый, где ключи — значения, а значения — ключи
- Написать функцию, которая принимает список ключей и проверяет, все ли из них есть в JSON
- Составить хеш: значение примитивного типа в JSON, сколько раз оно встречается