cách lấy danh sách phụ từ danh sách trong ocaml

Question

Tôi đang xem tài liệu Danh sách. Dường như thư viện không cung cấp chức năng sublist.

Tôi đang cố gắng lấy danh sách các phần tử từ i đến j. Bây giờ tôi phải viết nó như:

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

đó là khá ngắn gọn nhưng tôi đặt câu hỏi về hiệu quả của List.nth, bởi vì nếu nó O (n), tôi thà phải viết nó trong một ít ngắn gọn đường.

Tôi đang tự hỏi tại sao họ không cung cấp List.sublist func, nếu List.nth không phải là O (1), bởi vì đó là một hoạt động khá phổ biến như vậy ..

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] 

là Trên đây là nhiều hơn hoặc ít hơn một phiên bản phát quang của dung dịch newacct của. giải pháp newacct phân bổ một danh sách trung gian (drop i list), có thể cho trình biên dịch để tối ưu hóa đi trong Haskell nhưng khó khăn hơn nhiều trong ML. Do đó, phiên bản của anh ấy hoàn toàn phù hợp với chức năng Haskell và nhỏ hơn một chút so với phiên bản ML. Sự khác biệt giữa hai chỉ là một yếu tố không đổi: cả hai đều là O (e). Phiên bản của zrr là O (chiều dài (l)) kể từ List.filteri không biết rằng f chỉ trả lại false sau một thời gian, nó gọi nó cho tất cả các phần tử trong l.

Tôi không vui mừng để cho phép b chuyển sang tiêu cực nhưng phiên bản không phức tạp hơn.

Một tài liệu tham khảo trong khá nhiều cho việc phá rừng nếu bạn quan tâm: http://homepages.inf.ed.ac.uk/wadler/topics/deforestation.html

Answer 2

Đây là khó khăn hơn một chút so với nó phải được với thư viện chuẩn của OCaml --- thư viện chuẩn hơi thưa thớt. Nếu bạn sử dụng một trong các thư viện chuẩn mở rộng, nó sẽ dễ dàng hơn. Với Core, ví dụ: bạn có thể viết:

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

Tôi tưởng tượng điều gì đó tương tự là có thể với extlib/pin.

Answer 3

Hãy thử viết các hàm take (đầu tiên n) và drop (mọi thứ trừ n mục) đầu tiên (như trong Haskell) trước tiên. Sau đó sublist i j lst chỉ take (j-i) (drop i lst)

Answer 4

Trong khi câu trả lời cung cấp bởi Pascal thực hiện một ứng cử viên tốt đẹp cho List.sublist câu trả lời đúng là bạn có lẽ tốt hơn nên sử dụng một mảng của một danh sách . Các mô-đun Array thực hiện chức năng Array.sub mà bạn có thể sử dụng.

Trong khi ở nhiều mệnh lệnh ngôn ngữ như C++ hay Perl có bản chất là có sự khác biệt giữa danh sách và mảng, đây là không giống nhau trong OCaml nơi:

• Danh sách là phù hợp hơn cho phương pháp điều trị đệ quy và truy cập tuần tự , tức là thường là một ứng viên tốt hơn làm mảng làm đối số cho hàm đệ quy và bạn thường muốn xem xét tất cả các phần tử của danh sách.

• Mảng phù hợp hơn để truy cập ngẫu nhiên, thay đổi cấu trúc (chẳng hạn như sắp xếp) hoặc để tính toán số.