Функциональное программирование с OCAML

Question

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

Я пытаюсь реализовать следующий алгоритм:Записи:- E: непустое множество целых- s: целое число- d: положительное число с плавающей точкой, отличное от 0Выход :- T: набор целых чисел, включенных в Eм <- мин (E)T <- {м}ДЛЯ КАЖДОГО e ∈ sort_ascending (E \ {m}) DOЕСЛИ e> (1 + d) m И e <= s ТОT <- TU {e}м <- еВОЗВРАТ Т </p>

let f = fun (l: int list) (s: int) (d: float) ->
      List.fold_left (fun acc x -> if ... then (list_union acc [x]) else acc) 
   [(list_min l)] (list_sort_ascending l) ;;

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

Заранее спасибо всем, кто уделит мне время и поможет!

Answer 1

Предполагая, что list_min определено, вы должны думать о проблеме методично.Допустим, вы представляете набор со списком.Ваша функция принимает этот набор и некоторые аргументы и возвращает подмножество исходного набора, если элементы удовлетворяют определенным условиям.

Теперь, когда я впервые прочитал это, List.filter автоматически пришло мне в голову.

List.filter : ('a -> bool) -> 'a list -> 'a list

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

Сначала давайте сосредоточимся на вашем предикате:

fun s d m e -> (float e) > (1. +. d)*.(float m) && (e <= s)

Обратите внимание, что +. и *. - это функции плюс и произведение для чисел с плавающей точкой, а float - это функция, которая переводит целое число в число с плавающей точкой.

Скажем, функция predicate - это предикат, который я только что упомянул.

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

Итак, давайте начнем с моего представления о коде:

let m = list_min l;;

Так что это начальныйm

Затем я определю вспомогательную функцию, которая читает m в качестве аргумента, с l в качестве исходного набора, а s, d и m переменные, которые выиспользуется в вашем исходном императивном коде.

let rec f' l s d m =
  match l with
  | [] -> []
  | x :: xs -> if (predicate s d m x) then begin
                 x :: (f' xs s d x)
               end
               else
                 f' xs s d m in
f' l s d m

Затем для каждого элемента вашего набора вы проверяете, удовлетворяет ли он предикату, и если это так, вы вызываете функцию снова, но заменяете значение * 1041.* с x.

Наконец, вы можете просто вызвать f' из функции f:

let f (l: int list) (s: int) (d: float) =
  let m = list_min l in
  f' l s d m

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

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

Answer 2

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

Этот метод будет работать для «модификации» переменной m.Вместо этого следует думать о m как о параметре функции.

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