2010-04-25 44 views
8

我正在查看List文檔。看起來庫不提供sublist函數。如何從ocaml的列表中獲取子列表

我試圖從ij中獲取元素列表。現在,我必須把它寫成:

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

這是相當簡潔,但我質疑的List.nth效率,因爲如果它是爲O(n),我寧願把它寫在一個不太簡明辦法。

我不知道他們爲什麼不提供List.sublist FUNC,如果List.nthO(1),因爲它是這樣一個很常見的操作..

回答

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

以上是或多或少newacct的解決方案的砍伐版本。 newacct的解決方案分配一箇中間列表(drop i list),編譯器可以在Haskell中進行優化,但在ML中更加困難。因此,他的版本對於Haskell函數來說是完全正確的,而對於ML版本而言,它的邊緣次優。兩者之間的差異只是一個常數因素:兩者都是O(e)。 zrr的版本是O(長度(l)),因爲List.filteri不知道f只會在一段時間後返回false,它會將它稱爲l中的所有元素。

我不是很樂意讓b變爲負數,但是它並不複雜的版本。

不少當中的一個參考毀林如果你有興趣:http://homepages.inf.ed.ac.uk/wadler/topics/deforestation.html

+1

實際上,我錯了:由於中間列表,newacct函數的未優化的按值調用評估也是O(length(l))。爲了保持ML中的漸近複雜度O(e),你必須首先'取',然後'取'。 – 2010-04-27 15:48:34

2

這是有點難度比它應該是與OCaml的標準庫---標準庫有點稀疏。如果使用其中一個擴展標準庫,它會變得更容易。以Core爲例,你可以這樣寫:

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

我想象一下類似的可能與extlib /電池。

+2

即使您只是想在列表的開始處顯示某些內容,也會通過整個列表。 – larsr 2012-12-19 19:35:41

5

請先嚐試編寫take(前n項)和drop(除前n項之外的所有項)函數(如Haskell中的函數)。然後sublist i j lst只是take (j-i) (drop i lst)

+0

使用包含Batteries Included或Extlib的擴展庫,它將爲您提供接管和下載。 – 2010-04-28 23:31:15

0

雖然由帕斯卡爾提供的答案實現了一個很好的候選人List.sublist正確的答案是,你應該更好地利用列表的數組。 Array模塊實現您可能使用的Array.sub函數。

雖然在許多必要性語言如C++或Perl有基本上列表和數組之間沒有區別,這並不是OCaml中相同的,其中:

  • 解釋更適合於遞歸處理和順序訪問,通常更適合作爲遞歸函數的參數,因此您通常需要查看列表中的所有元素。

  • 數組更適合隨機訪問,結構變更(如排序)或數值計算。