Sono stato tentato e implementato la soluzione di zipper che ho suggerito 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 esempio di utilizzo:
# 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".
Se la lista da cui ottenere gli elementi è di grandi dimensioni, può essere notevolmente più veloce di 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
Naturalmente, questo è tutto un esercizio, poiché in pratica se le prestazioni sono importanti, trasformerai i tuoi dati in strutture di dati che sono più efficienti per l'accesso casuale, come gli array.
L'OP ha detto che non vuole usare il modulo 'Lisp' (ma' List.nth' è ok perché ha già la funzione corrispondente), ma non si può ancora dire che è semplicemente 'lascia indici xs è = List.map (List.nth xs) is'. – gasche
Onestamente: questo è il primo Ocaml che abbia mai scritto e non ho potuto capire come altro farlo. Probabilmente avrei dovuto dirlo, ma ho pensato che l'OP sarebbe stato in grado di risolverlo. – mange
In effetti, la soluzione è soddisfacente (e rispetta il desiderio dell'OP di avere un'implementazione reale piuttosto che un trucco stdlib). È esattamente equivalente alla chiamata 'List.map' che ho suggerito - per ulteriori informazioni. – gasche