вернуть список элементов из списка в OCaml

Question

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

Например, эта функцияЯ должен выполнить следующие вычисления: [5,6,7,8], [0, 3] => [5, 8]

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

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

Answer 1

Нет необходимости во временных переменных, просто используйте рекурсию!

# let rec indices xs = function
    | i :: is -> (List.nth xs i) :: indices xs is
    | [] -> []
  ;;
val indices : 'a list -> int list -> 'a list = <fun>

# indices [5;6;7;8] [0;3] ;;
- int list = [5; 8]

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

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

Answer 2

Я испытал искушение и реализовал решение на молнии, которое я предложил @ ftk.

(* A 'zipper' on the data structure "foo" is a derived data structure
   that represents a position in the data structure "foo", that can be
   filled with an element. You can think of this as a "cursor" on some
   element in the structure, that can moved in various directions to
   point to other elements of the structure. If the structure "foo"
   does not have random access, keeping a zipper allows to access the
   pointed element quickly (instead of having to look at it from the
   top of the structure again each time); its neighbors can be
   acccessed as well by moving the zipper.

   A cursor on a list has this form:

        cursor
          v
   [a; b; c; d; e; f]

   It can be represented as a value of type
     'a list * 'a * 'a list

   where the first list denotes the element before the cursor, and the
   second the elements after it. To be able to access the left
   neighbor of the cursor in constant time, we store the left elements
   in reverse order (rightmost first), so the zipper actually is

   ([b; a], c, [d; e; f])

   Zippers can be adapted to lot of data structures, including in
   particular trees. There are neat ways to define them as the
   "derivative" (in a calculus-like sense) of datatypes. See
   http://en.wikipedia.org/wiki/Zipper_(data_structure) for more
   information.
*)
let move_right = function
  | (left, x, x' :: right) -> (x :: left, x', right)
  | (_, _, []) -> raise Not_found

let move_left = function
  | (x' :: left, x, right) -> (left, x', x :: right)
  | ([], _, _) -> raise Not_found

let elem (left, e, right) = e

(* zipper of a list *)
let zipper = function
  | [] -> raise Not_found
  | x :: xs -> ([], x, xs)

let rec iterate f x = function
  | 0 -> x
  | n -> iterate f (f x) (n - 1)

let get_all data indices =
  let get_next index (pos, zip, acc) =
    let zip' =
      let move = if index < pos then move_left else move_right in
      try iterate move zip (abs (index - pos))
      with Not_found -> invalid_arg ("invalid index " ^ string_of_int index) in
    (index, zip', elem zip' :: acc) in
  let (_pos, _zip, result) =
    List.fold_right get_next indices (0, zipper data, []) in
  result

Пример использования:

# get_all [0;2;4;6;8;10] [2;0;1;4];;
- : int list = [4; 0; 2; 8]
# get_all [0;2;4;6;8;10] [2;0;1;6;4];;
Exception: Invalid_argument "invalid index 6".

Если список, откуда взять элементыбольшой, он может быть заметно быстрее, чем List.map (List.nth data):

let slow_get_all data indices = List.map (List.nth data) indices

let init n = Array.to_list (Array.init n (fun i -> i))
let data = init 100_000
let indices = List.map (( * ) 100) (init 1000)

(* some seconds *)
let _ = slow_get_all data indices

(* immediate *)
let _ = get_all data indices

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

Answer 3

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

Если вы хотите избавиться от последнего List библиотечного вызова, вы можете:

1. Использовать функцию indices mange и повторно реализовать List.nthфункция.Это не очень весело, и вы можете избежать систематического повторного сканирования списка x для каждого элемента списка y.

2. Используйте рекурсивную функцию для сканированияоба списка x и y одновременно.Например, вы можете:

   • выдавать элементы списка x столько раз, сколько значение первого элемента списка y.
   • воставшийся список x, зарезервируйте первый элемент, вставьте заголовок y и продолжите с остатками x и y.

I 'Я оставлю детали, как они населены дьяволом, как обычно, до вас.

Answer 4

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

В любом случае возможно хвостовое рекурсивное решение.(У меня есть подозрение, что это домашнее задание ...)

Идея состоит не в том, чтобы использовать какие-либо временные переменные, а в том, чтобы получить результат при просмотре списков.Подумайте о своей проблеме с точки зрения математической индукции.Что является основой индукции?Пустой список индексов дает пустой результат.Какой шаг индукции?Возьмите следующий заданный индекс из второго списка, добавив один элемент из первого списка к результату, и предположите (по индукции), что все остальные индексы будут обработаны правильно.

Вот что вы можете сделать в случаевторой список отсортирован в порядке возрастания, без повторяющихся элементов.indices_tr - это хвостовая рекурсивная функция, имеющая четыре аргумента;result - это ранее накопленный результирующий список, xs - оставшаяся часть первого списка, n - текущий индекс в этом списке, а is - оставшаяся часть списка индексов.

let indices xs is = 
 let rec indices_tr result (x::xs) n = function
   | [] -> result
   | i::is when i==n -> indices_tr (x::result) xs (n+1) is
   | is -> indices_tr result xs (n+1) is
 in
 indices_tr [] xs 0 is
;;

Существует предупреждение о том, что пустой список не обрабатывается.

Результатом является список в обратном порядке:

 # indices [1;3;5;7] [0;1;2];;
 - : int list = [5; 3; 1]

Вы не можете добиться большего успеха с чистымхвостово-рекурсивное решение;Вы можете, конечно, применить List.rev к этому.