Как превратить список пар в список int, где результат int - это сумма пары

Этот код работает в PolyML 5.2:

fun sum_pairs (l : (int * int) list) =
    if null l
    then []
    else ((#1 (hd l)) + (#2 (hd l))) :: sum_pairs(tl l)
(* ------------^-------------^ *)

Отличие от вашего тонкое, но существенное: (#1 hd(l)) отличается от (#1 (hd l)); первый не делает то, что вы думаете — он пытается извлечь первое поле кортежа hd, которое является функцией!

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

fun sum_pairs [] = []
  | sum_pairs ((a, b)::rest) = (a + b)::sum_pairs(rest)

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

Как оказалось, применение функции к элементам списка для создания нового списка — невероятно распространенный шаблон. Базовая библиотека предоставляет встроенную функцию под названием map, помогающую мы в этой задаче:

fun sum_pairs l = map (fn (a, b) => a + b) l

Здесь я использую анонимную функцию, чтобы сложить пары вместе. Но мы можем сделать еще лучше! Используя каррирование, мы можем просто определить функцию как:

val sum_pairs = map (fn (a, b) => a + b)

Функция map настроена так, что ее применение к функция возвращает новую функцию, которая принимает список — в данном случае список пар целых чисел.

Но подождите минутку! Похоже, эта анонимная функция просто применяет оператор сложения к своим аргументам! Это действительно так. Избавимся и от этого:

val sum_pairs = map op+

Здесь op+ обозначает встроенную функцию, которая применяет оператор сложения, как это делал наш функциональный литерал (выше).

Изменить: ответы на последующие вопросы:

1. Как насчет типов аргументов. Похоже, вы полностью исключили список аргументов в определении функции (заголовке). Это правда или я что-то пропустил?

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

fun add (a, b) = a + b

Компилятор может легко вывести тип int * int -> int, так как аргументы участвуют в сложении (если вы хотите real, вы должны об этом сказать).

2. Не могли бы вы объяснить, что здесь происходит sum_pairs ((a, b)::rest) = (a + b)::sum_pairs(rest). Извините за может быть фиктивный вопрос, но я просто хочу полностью понять его. Особенно, что означает = в этом контексте и какой порядок оценки этого выражения?

Здесь мы определяем функцию в двух предложениях. Первое предложение, sum_pairs [] = [], соответствует пустому списку и возвращает пустой список. Второй, sum_pairs ((a, b)::rest) = ..., соответствует списку, начинающемуся с пары. Если вы новичок в функциональном программировании, это может показаться магией. Но чтобы проиллюстрировать, что происходит, мы могли бы переписать клаузальное определение, используя case, следующим образом:

fun sum_pairs l =
  case l of
    [] => []
  | ((a, b)::rest) => (a + b)::sum_pairs(rest)

Пункты будут проверяться по порядку, пока не будет найдено совпадение. Если ни одно предложение не соответствует, возникает выражение Match. Например, если вы опустите первое предложение, функция всегда будет завершаться ошибкой, потому что l в конечном итоге будет пустым списком (либо он пуст с самого начала, либо мы рекурсивно прошли весь путь до конца).

Что касается знака равенства, то он означает то же самое, что и в любом другом определении функции. Он отделяет аргументы функции от тела функции. Что касается порядка вычисления, самое важное наблюдение заключается в том, что sum_pairs(rest) должно произойти перед минусами (::), поэтому функция не хвостовая рекурсия.