如何從ocaml的列表中獲取子列表

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

我試圖從i到j中獲取元素列表。現在，我必須把它寫成：

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.nth不O（1），因爲它是這樣一個很常見的操作..

來源

2010-04-25 romerun

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

來源

2010-04-26 23:57:30

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

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

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

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

來源

2010-04-26 02:54:38 zrr

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

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

來源

2010-04-26 05:30:32 newacct

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

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

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

解釋更適合於遞歸處理和順序訪問，即通常更適合作爲遞歸函數的參數，因此您通常需要查看列表中的所有元素。
數組更適合隨機訪問，結構變更（如排序）或數值計算。

來源

2016-03-11 18:21:10

如何從ocaml的列表中獲取子列表

回答

相關問題