Определить функцию измерения для оператора в OCaml

Question

Я хотел бы определить оператор l_op : A list * A list -> A list, для реализации которого требуется другой оператор op : A * A -> A. Учитывая a0: A, хотя для всех a1 : A op a0 a1 всегда возвращает результат как A, для некоторых a1 результат имеет больше смысла , чем для других a1.

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

Так что мне нужна мера , означающая .

Одним из возможных вариантов является определение функции measure: A * A * A -> int. Например, measure a0 a1 (op a0 a1) дает int от 1 до 10, что представляет, как op a0 a1 имеет смысл. Затем в реализации l_op al0 al1 для каждого a0 из al0 я могу найти a1 такой, что measure a0 a1 (op a0 a1) >= measure a0 a1' (op a0 a1') for all a1' in al1. Затем я удаляю a0 и a1 из двух списков и сопоставляю остальные два списка ...

Другой вариант, я немного изменяю op на op : A * A -> A * int, где целое число представляет, как операция имеет смысл. Затем в реализации l_op al0 al1 для каждого a0 из al0 я могу найти a1 такой, что for all a1' in al1, m1 >= m1' where (_, m1), (_, m1') = op a0 a1, op a0 a1'.

Преимущество второго варианта в том, что мы можем сохранить некоторый код, потому что мы можем вычислить измерение при выполнении op a0 a1. Недостатком является то, что подпись op : A * A -> A * int выглядит менее привлекательно, чем op : A * A -> A.

Итак, мои вопросы:

1) Для этого вида измерительной функции есть условное слово (которое начинается, вероятно, с h), но я забыл его, кто-нибудь может напомнить?

2) Как вы думаете, int - это хороший тип для измерения? Может быть, мы можем определить тип для этого ... Какой самый обычный способ?

3) Какой выбор, который я упомянул выше, лучше? Или у кого-нибудь есть идея получше?

Answer 1

Существует обычное слово для этого вида измерительной функции (которое, вероятно, начинается с h),

Может быть "эвристический"? Это происходит от древнегреческого «найти, обнаружить» и используется в компьютерной науке для обозначения методов, которые ищут «достаточно хорошие» результаты, часто аппроксимируя идеальное поведение простым, но почти столь же эффективным способом. Здесь это действительно уместно (если только ваше «значение измерения» на самом деле не является эвристическим / приближенным), но начинается с «h».

Я бы предложил просто назвать ваши измерения "счетом" или "весом".

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

В зависит от того, как определено ваше измерение. Какая структура вам нужна для результатов (например, вы могли бы сохранить обоснованность ваших измерений, нуждаясь в более богатой структуре)? Какие операции вы используете при измерении? Если вы используете только сложение и константы, int - это хорошо, если вы используете деление и т. Д., float может потребоваться. Вероятно, вам нужен тип, значения которого можно сравнивать во всех случаях.

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

type measure = int

Таким образом, вы можете использовать measure вместо int в большей части вашего кода, и вам не нужно будет впоследствии заменять все вхождения. Тем не менее, в OCaml мы обычно не пишем много аннотаций типов, благодаря логическому выводу, поэтому на практике я не ожидаю, что детали вашего выбора типа будут распространены в большом количестве кода.

Какой выбор, который я упомянул выше, лучше? Или у кого-нибудь есть идея получше?

Я бы выбрал второй вариант. Я подозреваю, что существует некоторая избыточность между операцией A -> A -> A «вычисления результата» и операцией A -> A -> int «вычисления значения результата». Делая оба в одно и то же время (A -> A -> A * int), вы можете повторно использовать одну и ту же логическую структуру, что делает это соответствие более понятным (и использует меньше кода). Если, напротив, две операции совершенно не связаны, вы можете рассмотреть возможность использования двух отдельных операторов (но я все равно буду использовать A -> A -> int для оценки; если вам нужно получить результат для измерения значения, вы все равно можете вызвать первую операцию внутренне. ).