DList là gì?

Question

Tôi đã thử googling cho điều này, nhưng tất cả tôi đã nhận được những câu chuyện về những người nổi tiếng nhỏ. Do thiếu tài liệu, DList là gì?

Answer 1

Đó là một danh sách khác nhau, dọc theo dòng của "Difference List as functions"

scala> val (l1, l2, l3) = (List(1, 2, 3), List(4, 5, 6), List(7, 8, 9)) 
l1: List[Int] = List(1, 2, 3) 
l2: List[Int] = List(4, 5, 6) 
l3: List[Int] = List(7, 8, 9) 

thêm vào trước hiệu quả:

scala> l1 ::: l2 ::: l3 
res8: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9) 

không hiệu quả phụ thêm. Điều này tạo ra một danh sách trung gian (l1 ++ l2), sau đó ((l1 ++ l2) ++ L3)

scala> l1 ++ l2 ++ l3 // inefficient 
res9: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9) 

DList cửa hàng lên gắn thêm, và chỉ cần tạo ra một danh sách đầy đủ, cách gọi một cách hiệu quả:

scala> List(l1, l2, l3) reduceRight (_ ::: _) 
res10: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9) 

Answer 2

Đó là loại dữ liệu trong gói scalaz không kinh điển, hữu ích cho các danh sách được nhập có quyền truy cập liên tục ở cả hai đầu. (Bí quyết là để google cho "scala" VÀ "dlist".)

Answer 3

Từ project page of scalaz:

DList, một kiểu dữ liệu cho đại diện các yếu tố cùng loại với thời gian hoạt động append/thêm vào trước liên tục.

Answer 4

Danh sách khác biệt là cấu trúc dữ liệu giống như danh sách hỗ trợ O (1) chắp thêm hoạt động.

Nối và các hoạt động khác sửa đổi danh sách được thể hiện qua thành phần hàm của các hàm sửa đổi, thay vì sao chép trực tiếp danh sách.

Một ví dụ, từ Haskell's dlist library:

-- Lists as functions 
newtype DList a = DL { unDL :: [a] -> [a] } 

-- The empty list 
empty  = DL id 

-- The append case: composition, a la Hughes 
append xs ys = DL (unDL xs . unDL ys) 

-- Converting to a regular list, linear time. 
toList  = ($[]) . unDL 

Kỹ thuật này quay ngược lại ít nhất đến Hughes 84, Một đại diện tiểu thuyết của danh sách và ứng dụng của nó với chức năng "đảo ngược", R. John Hughes, 1984. , trong đó, ông đề xuất các danh sách đại diện dưới dạng hàm và nối thêm dưới dạng thành phần hàm, ví dụ: ngược lại để chạy trong thời gian tuyến tính. Từ giấy:

---

---