Как получить значение из цикла for в OCaml

Question

Я написал следующий код, чтобы случайным образом выбрать элементы n элементов из списка и поместить выборки в новый список. Код ниже

let random_extract list n =
    let l =  ((List.length list)- 1) 
    and acc = []  in
    for i = 1 to n do 
        (List.nth list (Random.int l) ) :: acc  (* Line 447 *)
    done;
    acc
;;

Когда я загружаю файл, содержащий этот код, я получаюследующая ошибка

File "all_code.ml", line 447, characters 2-40:
Warning 10: this expression should have type unit.
val random_extract : 'a list -> int -> 'b list = <fun>

Два вопроса, Вопрос 1: что означает это предупреждение.

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

Вопрос 2: как получить значение acc из цикла for

Answer 1

Что сказал Джеффри Скофилд, а также:

let random_extract list n =
let l =  ((List.length list)- 1) 
and acc = ref []  in
for i = 1 to n do 
    acc := (List.nth list (Random.int l) ) :: !acc  (* Line 447 *)
done;
!acc

Если вы собираетесь использовать цикл for для чего-то подобного, тогда acc должно быть ссылкой, то есть изменяемым значением. В Ocaml и ML в целом let x = ... определяет неизменное значение . Затем, когда вы написали (List.nth list (Random.int l)) :: acc, это означало «смотри, я могу составить список». Вы нигде не сказали, что вновь созданный список должен быть назначен чему-либо, в частности, он не был назначен на acc (чего он не мог, потому что acc является неизменным). Ocaml выдал предупреждение, потому что увидел, что тело вашего цикла for создает список, но Ocaml знает, что тело цикла for должно создавать единицу ("void" в неверной терминологии C / C ++ / Java ).

Использование такой петли for ужасно. Правильный путь - сделать это так:

let random_extract lst =
  let l = List.length lst - 1 in
  let rec extract = function
   | 0 -> []
   | n -> List.nth lst (Random.int l) :: extract (n - 1)
  in
    extract

Если вы новичок в Ocaml, вам действительно следует потратить время на полное понимание вышеуказанного кода. После этого вам следует изучить следующий код и убедиться, что вы понимаете, почему он эффективнее первой версии (посмотрите «хвостовая рекурсия»):

let random_extract lst =
  let l = List.length lst - 1 in
  let rec extract acc = function
    | 0 -> acc
    | n -> extract (List.nth lst (Random.int l) :: acc) (n - 1)
  in
    extract []

Answer 2

Мне кажется, вы начинаете работать с OCaml и имеете опыт программирования.Вероятно, лучший совет для размышления об OCaml (и функциональном программировании в целом) - начать думать обо всех конструкциях вашей программы как о выражениях, то есть о вещах со значениями.В императивном программировании многие вещи (например, цикл for, цикл while, оператор if) не имеют значений, они просто «делают» вещи.В функциональном программировании все имеет значение.

Поскольку OCaml не является функциональным языком pure , одно значение зарезервировано для представления выражения, которое просто «что-то» делает.Значение записывается так: ().Тип этого значения известен как unit (это единственное значение типа unit).

Поскольку цикл for предназначен для того, чтобы просто «делать» вещи, даже в OCaml,выражение внутри цикла должно иметь тип unit.Но вы написали что-то, что имеет тип списка.Все, что выглядит как x :: y, должно быть списком, потому что конструктор :: создает список.Это то, о чем вас предупреждает компилятор.Внутри вашего цикла должен быть тип unit, но у него есть тип списка.

Ваша вторая проблема заключается в том, что выражение x :: y не не меняет значение y,Это суть функционального программирования.Все, что делает выражение, это вычисляет новое значение (список).Это не меняет ни одно из значений, которые появляются в выражении.Из-за этого acc заканчивается тем же значением, с которого оно начиналось.

Я бы действительно предложил вам решить эту проблему с помощью рекурсии (как это было предложено Бэзилом Старынкевичем), а не пытаться использовать императивные конструкции, такие какцикл for.Это приведет к гораздо более идиоматическому коду OCaml.Если вам действительно необходимо использовать цикл for по какой-либо причине, вам нужно сделать переменную acc изменяемым значением, и вам нужно изменить (изменить) ее в цикле.

Answer 3

Вот как я ответил на этот вопрос.

let rec remove_at_k list i acc =
    match list with 
        [] -> []
      | h::t -> if (i = 1) then acc @ t else remove_at_k t (i-1) (acc@[h])
;;

let random_extract lst n =
    let rec extract lst2 acc = function 
        | 0 -> acc
        | n -> let l = List.length lst2 in let index = (Random.int(l)) in 
               (*  print_list lst2; Printf.printf " with I %d\n" index ; *)
          extract (remove_at_k lst2 (index+1) []) (List.nth lst2 index :: acc) (n-1)
    in 
    extract lst [] n
;;

Я не мог использовать решение, предоставленное выше Андреем Бауэром, так как это решение не гарантирует, что один и тот же элемент не будет выбран дважды. Решение выше делает это.