Cách thành ngữ để recurse thông qua các bộ sưu tập trong Clojure

Question

Tôi đang cố gắng hiểu cách thức thành ngữ trong Clojure để recurse thông qua một cây hoặc danh sách được đại diện bởi một danh sách Clojure (hoặc một loại bộ sưu tập).

tôi có thể viết như sau để đếm các yếu tố trong một bộ sưu tập phẳng (bỏ qua một thực tế rằng nó không phải đuôi-đệ quy):

(defn length 
    ([xs] 
    (if (nil? (seq xs)) 
     0 
     (+ 1 (length (rest xs)))))) 

Bây giờ trong Đề án hoặc CL tất cả các ví dụ duy nhất từng làm điều này qua danh sách , do đó, kiểm tra trường hợp cơ sở thành ngữ trong các ngôn ngữ đó sẽ là (nil? xs). Trong Clojure, chúng tôi muốn chức năng này hoạt động trên tất cả các loại bộ sưu tập, vì vậy là thử nghiệm thành ngữ (nil? (seq xs)) hoặc có thể là (empty? xs) hoặc một thứ hoàn toàn khác?

Trường hợp khác tôi muốn xem xét là duyệt qua cây, tức là duyệt qua danh sách hoặc vectơ đại diện cho một cây, ví dụ: [1 2 [3 4].

Ví dụ, đếm các nút trong một cây:

(defn node-count [tree] 
    (cond (not (coll? tree)) 1 
     (nil? (seq tree)) 0 
     :else (+ (node-count (first tree)) (node-count (rest tree))))) 

Ở đây chúng ta sử dụng (not (coll? tree)) để kiểm tra các nguyên tử, trong khi ở Scheme/CL, chúng tôi muốn sử dụng atom?. Chúng tôi cũng sử dụng (nil? (seq tree)) để kiểm tra bộ sưu tập trống. Và cuối cùng chúng tôi sử dụng first và rest để hủy cấu trúc cây hiện tại sang nhánh trái và phần còn lại của cây.

Vì vậy, để tóm tắt, là những hình thức sau đây thành ngữ trong Clojure:

• (nil? (seq xs)) để kiểm tra bộ sưu tập trống
• (first xs) và (rest xs) để thâm nhập vào các bộ sưu tập
• (not (coll? xs)) để kiểm tra các nguyên tử

Answer 1

Kiểm tra thành ngữ cho một lần hiển thị không trống là (seq coll):

(if (seq coll) 
    ... 
) 

Các nil? là không cần thiết, vì một giá trị phi nil trở về từ seq là đảm bảo được một seq và do đó không phải nil cũng không false và do đó truthy.

Nếu trước tiên bạn muốn xử lý trường hợp nil, bạn có thể thay đổi if thành if-not hoặc seq thành empty?; sau này được thực hiện dưới dạng một thành phần của seq với not (đó là lý do tại sao nó không phải là thành ngữ để viết (not (empty? xs)), xem docstring của empty?).

Đối với first/rest - đó là hữu ích để nhớ về các biến thể nghiêm ngặt của rest, next, việc sử dụng trong số đó là nhiều thành ngữ so với gói rest trong một seq.

Cuối cùng, coll? kiểm tra xem đối số của nó có phải là bộ sưu tập liên tục Clojure hay không (ví dụ: clojure.lang.IPersistentCollection).Cho dù đây là một kiểm tra thích hợp cho "non-nguyên tử" phụ thuộc vào việc mã cần phải xử lý cấu trúc dữ liệu Java như không nguyên tử (thông qua interop): ví dụ: (coll? (java.util.HashSet.)) là false, như là (coll? (into-array [])), nhưng bạn có thể gọi seq trên cả hai. Có một hàm gọi là seqable? trong core.incubator trong contrib mô-đun mới hứa hẹn sẽ xác định xem (seq x) có thành công cho một số x nhất định hay không.

Answer 2

Tôi cá nhân như phương pháp sau đây để recurse thông qua một bộ sưu tập:

(defn length 
    "Calculate the length of a collection or sequence" 
    ([coll] 
    (if-let [[x & xs] (seq coll)] 
     (+ 1 (length xs)) 
     0))) 

Các tính năng:

• (seq coll) là thành ngữ để thử nghiệm liệu một bộ sưu tập trống (như mỗi câu trả lời tuyệt vời Michal của)
• if-let với (seq coll) tự động xử lý cả trường hợp bộ sưu tập trống và trống
• Bạn có thể sử dụng lệnh destruc Turing để đặt tên cho các yếu tố đầu tiên và tiếp theo như bạn thích để sử dụng trong cơ quan chức năng của bạn

Lưu ý rằng nói chung nó là tốt hơn để viết hàm đệ quy sử dụng recur nếu có thể, để bạn có được những lợi ích của đệ quy đuôi và don 't nguy cơ thổi lên ngăn xếp. Vì vậy, với điều này trong tâm trí, tôi thực sự có thể viết chức năng cụ thể này như sau:

(defn length 
    "Calculate the length of a collection or sequence" 
    ([coll] 
    (length coll 0)) 
    ([coll accumulator] 
    (if-let [[x & xs] (seq coll)] 
     (recur xs (inc accumulator)) 
     accumulator))) 

(length (range 1000000)) 
=> 1000000