возвращает список элементов из списка в 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] 

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

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

Answer 2

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

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

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

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

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

Я оставлю подробности, так как обитают дьявол, как они, как правило, до вас.

Answer 3

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

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

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

Вот что вы можете сделать, если второй список сортируется в порядке возрастания, без повторных элементов. 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 к этому.

Answer 4

Я был искушен и реализовал решение для молнии, которое я предложил @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 

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