2012-03-21 1 views
7

Sono nuovo in OCaml e sto cercando di implementare una funzione che restituisce un elenco di elementi di un determinato elenco x agli indici nell'elenco .restituisce un elenco di elementi da un elenco in OCaml

Per esempio, che la funzione deve eseguire la seguente calcolo: [5,6,7,8], [0, 3] => [5, 8]

io non sono sicuro di come memorizzare le variabili temporanee in ML e non hanno una chiara idea di come funziona. So come trovare un elemento da un elenco dato indice specificato, però.

Qualsiasi idea sarà apprezzata, ma mi piacerebbe utilizzare le funzioni ricorsive ed evitare il modulo List.

risposta

7

Non c'è bisogno di variabili temporanee, basta usare la ricorsione!

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

Si costruisce l'elenco passando attraverso ognuno degli indici forniti e poi consing che sulla lista restituiti dal passo successivo.

Speriamo che anche questo sia ottimizzato in una forma ricorsiva di coda, ma non ne sono così sicuro. Potresti volerlo cambiare per essere ricorsivo in modo corretto, ma lo lascerò a te.

+0

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

+0

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

+0

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

2

La risposta di mange illustra bene la potenza della programmazione funzionale. Consentitemi di ribadire il suo significato: non c'è bisogno di variabili temporanee, basta usare la ricorsione.

caso si vuole sbarazzarsi dell'ultima chiamata biblioteca List, si potrebbe:

  1. funzione Use di rogna indices e re-implementare la funzione List.nth. Questo non è molto divertente e potresti preferire evitare la scansione sistematica dell'elenco x per ogni elemento dell'elenco .

  2. Utilizzare una funzione ricorsiva per eseguire la scansione di entrambi gli elenchi x e contemporaneamente. Per esempio, si potrebbe desiderare di:

    • elementi pop della lista x tutte le volte che il valore del primo elemento della lista y.
    • nell'elenco rimanente x, riservare il primo elemento, inserire il numero di e continuare con i valori rimanenti di x e .

Lascio i dettagli, come abitata dal diavolo come di solito sono, fino a voi.

+0

come funzionerebbe il secondo approccio se gli indici da ottenere non vengono ordinati? (Ovviamente puoi ordinarli prima o usare una cerniera o la lista a sinistra invece di lasciare cadere gli elementi.) – gasche

+0

@gasche: sì, gli indici devono essere ordinati, e il codice probabilmente si avvicina molto a quello di @ winitzki. Ero un po 'cauto nel fornire una soluzione completa, dato il tag "compiti a casa". Oh, e ottima soluzione per la chiusura lampo! – ftk

1

È necessaria una funzione di due elenchi; il secondo elenco fornisce gli indici per il primo elenco. Ci sono due possibilità: la seconda lista è ordinata in ordine ascendente, o la seconda lista non è ordinata in alcun modo. Se la seconda lista è ordinata, la tua funzione sarà molto più efficiente. Questo perché una lista può essere attraversata in modo efficiente da sinistra a destra, ma l'accesso casuale a un elemento con un dato indice non è rapido.

In ogni caso, è possibile una soluzione ricorsiva in coda.(Ho il sospetto che questa sia una domanda a casa ...)

L'idea non è quella di utilizzare alcuna variabile temporanea, ma di costruire il risultato mentre si passa attraverso gli elenchi. Pensa al tuo problema in termini di induzione matematica. Qual è la base dell'induzione? L'elenco vuoto di indici fornisce risultati vuoti. Qual è il passo dell'induzione? Prendi il prossimo indice dato dalla seconda lista, aggiungendo un elemento dalla prima lista al risultato e assumendo (per induzione) che tutti gli altri indici saranno gestiti correttamente.

Ecco cosa è possibile fare nel caso in cui la seconda lista sia ordinata in ordine ascendente, senza elementi ripetuti. indices_tr è una funzione ricorsiva in coda con quattro argomenti; result è l'elenco risultante accumulato in precedenza, xs è la parte rimanente del primo elenco, n è l'indice corrente in tale elenco e is è la parte rimanente dell'elenco di indici.

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

C'è un avviso che la lista vuota non viene gestita.

Il risultato è un elenco in ordine inverso:

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

Non si può fare molto meglio con una soluzione di pura ricorsiva in coda; ovviamente potresti applicare List.rev a questo.

3

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.

Problemi correlati