Функция, преобразующая последовательность в список в OCaml

avatar
maya
8 апреля 2018 в 05:54
967
3
2

Я хочу преобразовать последовательность в список с помощью List.init. Я хочу на каждом этапе получать i-е значение s.

let to_list s = 
  let n = length s in List.init n (fun _i -> match s () with
    |Nil -> assert false
    |Cons(a, sr) -> a)

Это дает мне список, инициализированный только первым элементом s. Возможно ли в OCaml инициализировать список со всеми значениями s, нужна помощь, пожалуйста (извините за вопрос для начинающих-_-)

спасибо

Источник

Ответы (3)

avatar
tbrk
8 апреля 2018 в 08:12
3

Это может помочь изучить определение List.init.

Есть два варианта в зависимости от размера списка: хвостовой рекурсивный, init_tailrec_aux, результат которого находится в обратном порядке, и основной, init_aux. У них идентичные результаты, поэтому нам достаточно посмотреть на init_aux:

.
let rec init_aux i n f =
  if i >= n then []
  else
    let r = f i in
    r :: init_aux (i+1) n f

Эта функция рекурсивно увеличивает счетчик i, пока не достигнет предела n. Для каждого значения счетчика, которое строго меньше предела, он добавляет значение, заданное f i, в начало создаваемого списка.

Вопрос в том, что делает ваша анонимная функция при вызове с разными значениями i?:

let f_anon =
  (fun _i -> match s () with
      |Nil -> assert false
      |Cons(a, sr) -> a)

Независимо от _i, он всегда дает главу списка, произведенного s (), а Если <5862626951263> <58626931263> s () всегда возвращает один и тот же список, то f_anon 0 = f_anon 1 f_anon 2> = f_anon 3 = hd (s ()).

Ответ Джеффри Скофилда описывает метод присвоения разных значений каждому _i, и я согласен с его предположением, что List.init не является лучшим решением этой проблемы.

avatar
maya
8 апреля 2018 в 12:00
0

использование рекурсивной функции увеличит сложность, поэтому я думаю, что прямая инициализация списка (или массива) соответствующей длины будет лучше, но я действительно не знаю, как получить другое значение для каждого _i, как сказал Джеффри Скофилд я не совсем знаком с ocaml, особенно с последовательностями, поэтому у меня есть некоторые трудности с этим :(

tbrk
8 апреля 2018 в 15:03
0

Попробуйте взять описанную ниже функцию init_aux и заменить f своей последовательностью s. Голова s дает r, а его хвост должен быть передан рекурсивному вызову.

Jeffrey Scofield
8 апреля 2018 в 19:57
0

Использование рекурсии не увеличивает сложность. List.init реализована как рекурсивная функция. Рекурсия — это обычный способ решения проблем в OCaml. (Но вам нужно научиться распознавать и использовать хвостовую рекурсию, это я признаю.)

Pandemonium
9 апреля 2018 в 23:33
0

Мягкое напоминание @maya: пожалуйста, опубликуйте это как комментарий вместо ответа, иначе оно может быть помечено для удаления позже.

avatar
Jeffrey Scofield
8 апреля 2018 в 06:15
3

Суть проблемы в том, что вы не сохраняете sr, что позволило бы получить следующий элемент последовательности.

Однако немного более серьезная проблема заключается в том, что List.init передает только int в качестве аргумента функции инициализации. Таким образом, даже если вы отслеживали sr, его невозможно передать вашей функции инициализации.

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

Я бы предложил не использовать List.init. Вы можете написать простую рекурсивную функцию, которая будет делать то, что вы хотите. (Если вам небезразлична хвостовая рекурсия, вы можете написать немного менее простую функцию.)

maya
8 апреля 2018 в 06:27
0

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

Jeffrey Scofield
8 апреля 2018 в 19:55
1

Ну, List.init применим только в тех случаях, когда элементы списка могут быть вычислены на основе их положения в списке (и ни на чем другом). Поскольку ваш случай не такой, нет смысла (ИМХО) выяснять, как использовать для него List.init. Вместо этого попробуйте использовать List.init для преобразования массива в список (скажем).

Pandemonium
9 апреля 2018 в 23:40
0

@maya, если значения, которые вы хотите восстановить, не являются целыми числами индекса в диапазоне 0..n-1, где n является первым аргументом List.init, то, как сказал Джеффри, это довольно обречено на провал.