cómo obtener una lista secundaria de una lista en ocaml

Question

Estoy viendo la documentación de la Lista. Parece que la biblioteca no proporciona una función sublist.

Estoy tratando de obtener la lista de elementos de i a j . Ahora tengo que escribir como:

let rec sublist list i j = 
    if i > j then 
    [] 
    else 
    (List.nth list i) :: (sublist list (i+1) j) 

que es bastante conciso, pero yo estoy cuestionando la eficacia de List.nth, porque si es O (n), yo preferiría tener que escribir de una manera menos concisa camino.

Me pregunto por qué no nos proporcionaron List.sublist func, si no es List.nthO (1), porque es una operación bastante común ..

Answer 1

let rec sublist b e l = 
    match l with 
    [] -> failwith "sublist" 
    | h :: t -> 
    let tail = if e=0 then [] else sublist (b-1) (e-1) t in 
    if b>0 then tail else h :: tail 
;; 

sublist 3 5 [1;2;3;4;5;6;7;8;9] ;; 
- : int list = [4; 5; 6] 

Lo anterior es más o menos una versión de la solución de deforestada newacct. La solución de newacct asigna una lista intermedia (drop i list), que es posible para el compilador optimizar en Haskell pero mucho más difícil en ML. Por lo tanto, su versión está perfectamente bien para una función Haskell y marginalmente subóptima para una ML. La diferencia entre los dos es solo un factor constante: ambos son O (e). La versión de zrr es O (longitud (l)) ya que List.filteri no sabe que f solo devuelve false después de un tiempo, lo llama para todos los elementos en l.

No estoy muy contento de que b sea negativo, pero la versión en la que no es más complicada.

Una referencia entre un buen número de la deforestación si está interesado: http://homepages.inf.ed.ac.uk/wadler/topics/deforestation.html

Answer 2

Esto es un poco más difícil de lo que debería ser con la biblioteca estándar de OCaml --- la biblioteca estándar es un poco escasa. Si usa una de las bibliotecas estándar extendidas, se vuelve más fácil. Con Core, por ejemplo, podría escribir:

let sublist list low high = 
    List.filteri l ~f:(fun i _ -> i >= low && pos < high) 

me imagino algo similar es posible con extlib/baterías.

Answer 3

Intente escribir primero las funciones take (primeros n elementos) y drop (todo menos los primeros n elementos) (como en Haskell). Entonces sublist i j lst es sólo take (j-i) (drop i lst)

Answer 4

Mientras que la respuesta proporcionada por Pascal implementa un buen candidato para List.sublist la respuesta correcta es que probablemente mejor en caso de utilizar una matriz de una lista . Los módulos Array implementan la función Array.sub que puede usar.

Mientras que en muchos lenguajes imperativos como C++ o Perl esencialmente no hay diferencia entre las listas y matrices, esto no es la misma en OCaml donde:

• Las listas son más adecuados para tratamientos recursivas y de acceso secuencial , es decir, suele ser un mejor candidato como una matriz como argumento para una función recursiva, y normalmente desea ver todos los elementos de la lista.

• Las matrices son más adecuadas para el acceso aleatorio, la alteración de la estructura (como la clasificación) o para cálculos numéricos.