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.
El PO mencionó que él no desee utilizar el módulo 'Lisp' (pero' List.nth' está bien porque ya tiene la función correspondiente), pero aún no podía que esto es simplemente dejar que los índices 'XS is = List.map (List.nth xs) is'. – gasche
Honestamente: este es el primer Ocaml que he escrito y no pude averiguar cómo hacerlo. Probablemente debería haber mencionado eso, pero pensé que el OP podría resolverlo. – mange
De hecho, su solución está bien (y respeta el deseo del OP de tener una implementación real en lugar de un truco stdlib). Es exactamente equivalente a la llamada 'List.map' que sugerí, para obtener información adicional. – gasche