Ocaml: сортировка списка по классам эквивалентности

Question

Я недавно начал изучать ocaml, и у меня возникли проблемы с определением проблемы.

Цель:

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

Обновление: я решил попробовать и заставить его работать без функции библиотеки.

Пока это мой код. Компилируется, но не запускается. Любая помощь с синтаксисом будет оценена.

let buckets f lst =
  let rec helpfunction f lst newlist = 
     match lst with
      | [] ->newlist
      | h::t -> match newlist with
             | [] -> helpfunction f lst [h]@newlist
             | [a]::_ -> if f h a 
                  then helpfunction f t [a::h]@newlist
                  else helpfunction f t ([a]::[h]@mylist

ВАЖНО: это домашнее задание, поэтому я не ищу код, вставленный для меня. Я пытаюсь войти через него на моем доме с небольшой помощью в общем мыслительном процессе и синтаксисе. Как только я получу это, я буду работать над тем, чтобы сделать его более эффективным

Answer 1

То, что вы пытаетесь - это взять каждый элемент во входных данных и затем вставить его где-нибудь в список результатов списков. Позвольте мне предложить другой подход.

Вы начинаете с «списка ввода и пустого» списка списка результата, который вы строите.

Если ввод пуст, ваш результат завершен и вы возвращаете его.

В противном случае разбейте входные данные на голову и хвост (сопоставление с образцом уже делает это). Затем разделите входной список на элементы, которые эквивалентны голове и те, которые не являются. Рекурсировать со вторым списком в качестве нового ввода и (первый список :: результат) в качестве нового результата.

Answer 2

Хорошо, давайте попробуем решить задачу, не выполняя ее фактически:)

Грубо говоря, алгоритм выглядит следующим образом:

1. Взять целое число x из исходного списка

2. Если целевой список списков (каждый из которых содержит целые числа одного и того же класса эквивалентности) содержит список соответствующего класса эквивалентности, добавьте x в этот список

3. В противном случае создайте новый список классов эквивалентности, содержащий одно значение ([x]), и добавьте его в целевой список

4. Повтор 1- 3 для других целых чисел в списке целей.

(1), (3) и (4) представляется довольно тривиальным для реализации.

Проблемы как реализовать (2) и как это сделать эффективно:)

«Целевой список содержит список, который ...» можно перефразировать как «существует список lst в целевом списке, например. .. "- это дает нам сильный намек на то, что List.exists можно как-то здесь использовать. Что проверять, также более или менее ясно: каждый член одного и того же списка классов эквивалентности по определению эквивалентен, поэтому мы можем взять только голову и сравнить ее с x, используя p.

Вопрос как добавить целое число в список в другом списке. Списки неизменны, поэтому мы не можем просто удалить их там ... Но мы можем взять список целей и преобразовать или свернуть в другой. Могу поспорить, что вы получили подсказку: List.fold_left - еще одна часть головоломки.

Итак, суммируя все это, мы можем прийти к следующему «более точному» алгоритму

1. Начните с пустого списка целей res

2. Возьмите целое число x из списка источников l

3. Используйте List.exists чтобы проверить, есть ли список lst в res, например, для его головы h p x h = true

4. Если да, используйте List.fold_left для преобразования тока res в новый, где lst заменен на x::lst, а все остальные списки классов эквивалентности скопированы как

5. Если нет, введите новый класс эквивалентности (добавьте [x] до res)

6. Повторите 2-5 для следующего целого числа в списке источников, пока оно не станет пустым.

Реализация, которая (почти) буквально следует этому алгоритму относительно просто. Но это будет не очень эффективно, потому что exists и fold будут повторять один и тот же список дважды, выполняя буквально одну и ту же проверку. С некоторыми изменениями можно было бы сделать это за один проход, но этот неэффективный должен быть достаточно хорошим в качестве отправной точки ...