Стандарт ML: вычисление среднего значения заданного набора

Question

У меня недавно было задание рассчитать среднее значение набора (заданного вводом) в стандартном ML.

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

average = fn : real list -> real 

Мы обсуждали это в учебнике, как хорошо, но я хотел бы знать, если есть какая-то хитрость при создании таких функций в Standard ML.

Заранее благодарен!

Answer 1

Совокупность чисел и разделение по длине. Простой рекурсивный sum, как правило, является одним из первых примеров, которые вы увидите в любом учебнике SML. Вам нужно будет иметь пустой список из списка sum для оценки 0.0, а не 0, чтобы убедиться, что тип возврата real. Как только вы определите функцию sum, вы можете определить average в 1 строке, используя sum и встроенную функцию length. Подложка заключается в том, что SML не позволяет реальному делиться на int. Вы можете использовать функцию преобразования Real.fromInt по длине перед делением суммы на нее. Существует некоторая неэффективность при переходе по одному и тому же списку дважды, один раз, чтобы суммировать его и один раз рассчитать его длину, но нет оснований беспокоиться о таких вещах, когда вы впервые изучаете язык.

На Edit: Так как вы нашли естественное решение и разделяете его в комментариях, здесь более идиоматическая версия, которая вычисляет среднее за один проход по списку:

fun average nums = 
    let 
     fun av (s,n,[]) = s/Real.fromInt(n) 
     | av (s,n,x::xs) = av (s+x,n+1,xs) 
    in 
     av (0.0, 0, nums) 
    end; 

Он работает путем определения вспомогательная функция которая делает тяжелый подъем. Они широко используются в функциональном программировании. В отсутствие изменчивого состояния общий трюк заключается в том, чтобы явно передавать в качестве параметров величины, которые были бы последовательно модифицированы соответствующей петлей на императивном языке. Такие параметры часто называются accumulators, так как они обычно накапливают растущие списки, текущие суммы, текущие продукты и т. Д. Здесь s и n - это аккумуляторы с суммой элементов и n - длина списка. В базовом случае (s,n,[]) больше нечего накапливать, поэтому возвращается окончательный ответ. В случае без основания (s,n,x::xs), s и n соответствующим образом изменяются и передаются вспомогательной функции вместе с хвостом списка. Определение av равно tail-recursive, следовательно, будет работать со скоростью цикла без увеличения стека. Единственное, что нужно сделать общей функции average, - это вызвать вспомогательную функцию с соответствующими начальными значениями. let ... helper def ... in ... helper called with start-up values ...end - распространенная идиома, используемая для предотвращения загромождения верхнего уровня программы вспомогательными функциями.

Answer 2

Поскольку только непустые списки могут иметь средние, альтернатива на ответ Джона Коулмана является:

fun average [] = NONE 
    | average nums = 
    let 
     fun av (s,n,[]) = s/Real.fromInt(n) 
      | av (s,n,x::xs) = av (s+x,n+1,xs) 
    in 
     SOME (av (0.0, 0, nums)) 
    end; 

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