devolver una lista de elementos de una lista en OCaml

Question

Soy nuevo en OCaml, y ahora estoy tratando de implementar una función que devuelve una lista de elementos de una lista dada x en índices en la lista y.

Por ejemplo, la función que debe realizar el siguiente cálculo: [5,6,7,8], [0, 3] => [5, 8]

No estoy seguro de cómo almacenar variables temporales en ML y no tienen una idea clara de cómo funciona. Sin embargo, sé cómo encontrar un elemento de una lista con un índice especificado.

Cualquier idea será apreciada, pero me gustaría usar funciones recursivas y evitar el módulo List.

Answer 1

No hay necesidad de variables temporales, solo use recursion!

# 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] 

se va formando la lista pasando a través de cada uno de los índices proporcionados y luego CONSING que en la lista devuelta por el siguiente paso.

Esperemos que esto también se optimice en una forma recursiva de la cola, pero no estoy tan seguro de eso. Es posible que desee cambiarlo para que sea recursivo de cola correctamente, pero lo dejo en sus manos.

Answer 2

La respuesta de mange ilustra muy bien el poder de la programación funcional. Permítanme reiterar lo esencial: sin necesidad de variables temporales, solo use la recursión.

Si desea deshacerse de la última llamada a la librería List, usted podría:

1. indices función y el uso de la sarna volver a implementar la función List.nth. Esto no es muy divertido, y es posible que prefiera evitar la nueva exploración sistemática de su lista x para cada elemento de su lista y.

2. Utilice una función recursiva para escanear simultáneamente sus listas x y y. Por ejemplo, es posible que desee:

   • elementos del estallido de la lista x tantas veces como el valor del primer elemento de la lista y.
   • en la lista restante x, reservar el primer elemento, el pop de la cabeza de y, y continuar con los restos de x y y.

Dejaré los detalles, como habitada por el diablo, como es habitual, depende de usted.

Answer 3

Necesita una función de dos listas; la segunda lista proporciona índices para la primera lista. Hay dos posibilidades: la segunda lista está ordenada en orden ascendente, o la segunda lista no está ordenada de ninguna manera. Si la segunda lista está ordenada, su función será mucho más eficiente. Esto es así porque una lista puede atravesarse de manera eficiente de izquierda a derecha, pero el acceso aleatorio a un elemento con un índice dado no es rápido.

En cualquier caso, es posible una solución recursiva de cola.(Tengo la sospecha de que esta es una pregunta tarea ...)

La idea es no utilizar ninguna de las variables temporales, sino para construir el resultado a medida que avanza a través de las listas. Piensa en tu problema en términos de inducción matemática. ¿Cuál es la base de la inducción? La lista vacía de índices da un resultado vacío. ¿Cuál es el paso de la inducción? Tome el siguiente índice dado de la segunda lista, agregando un elemento de la primera lista al resultado, y suponga (por inducción) que todos los demás índices se manejarán correctamente.

Aquí es lo que puede hacer en el caso de la segunda lista está ordenada de forma ascendente, sin elementos repetidos. indices_tr es una función recursiva de cola que tiene cuatro argumentos; result es la lista resultante acumulado previamente, xs es la parte restante de la primera lista, n es el índice de corriente en esa lista, y is es la parte restante de la lista de índices.

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 
;; 

Existe una advertencia de que la lista vacía no se maneja.

El resultado es una lista en orden inverso:

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

No se puede hacer mucho mejor con una solución recursiva de cola pura; por supuesto, podrías aplicar List.rev a eso.

Answer 4

tuve la tentación e implementó la solución de cremallera que le sugerí a @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 

Un ejemplo de uso:

# 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". 

Si la lista de dónde obtener los elementos es grande, puede ser notablemente más rápido que 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 

Por supuesto, esto es todo un ejercicio, ya que en la práctica si el rendimiento es importante, transformará los datos en estructuras de datos que son más eficientes para el acceso aleatorio, como las matrices.