Danh sách trong Haskell: loại dữ liệu hoặc loại dữ liệu trừu tượng?

Question

Từ những gì tôi hiểu, loại danh sách trong Haskell được thực hiện nội bộ bằng cách sử dụng một danh sách liên kết. Tuy nhiên, người dùng của ngôn ngữ không nhận được để xem chi tiết của việc thực hiện, cũng không có khả năng sửa đổi "liên kết" tạo nên danh sách liên kết để cho phép nó trỏ đến một địa chỉ bộ nhớ khác. Điều này, tôi cho rằng, được thực hiện nội bộ.

Sau đó, loại danh sách có thể đủ điều kiện như trong Haskell không? Đây có phải là "kiểu dữ liệu" hay "kiểu dữ liệu trừu tượng" không? Và loại danh sách được liên kết nào của việc triển khai?

Ngoài ra, do loại danh sách do Prelude cung cấp không phải là loại danh sách được liên kết, các hàm danh sách liên kết cơ bản có thể được triển khai như thế nào?

Lấy ví dụ, đoạn mã này được thiết kế để thêm một yếu tố một lúc chỉ số n của một danh sách:

add [] acc _ _ = reverse acc 
add (x:xs) acc 0 a = add xs (x:a:acc) (-1) a 
add (x:xs) acc n a = add xs (x:acc) (n-1) a 

Sử dụng một "thực" danh sách liên kết, thêm một yếu tố sẽ chỉ bao gồm sửa đổi một con trỏ đến một địa chỉ bộ nhớ. Điều này là không thể trong Haskell (hoặc là nó?), Do đó câu hỏi: là việc thực hiện của tôi thêm một yếu tố vào một danh sách tốt nhất có thể, hoặc tôi thiếu một cái gì đó (việc sử dụng các chức năng reverse là, tôi nghĩ rằng, đặc biệt là xấu xí, nhưng nó có thể làm mà không có?)

Xin vui lòng, đừng ngần ngại sửa tôi nếu bất cứ điều gì tôi đã nói là sai, và cảm ơn bạn đã dành thời gian của bạn.

Answer 1

Bạn đang nhầm lẫn với cấu trúc dữ liệu. Nó là danh sách thích hợp - không phải danh sách bạn được phép sửa đổi. Haskell hoàn toàn là chức năng, nghĩa là giá trị không đổi - bạn không thể thay đổi một mục trong danh sách nhiều hơn bạn có thể biến số 2 thành 3. Thay vào đó, bạn thực hiện các phép tính để tạo các giá trị mới với những thay đổi bạn muốn.

Bạn có thể xác định chức năng mà chỉ đơn giản nhất như sau:

add ls idx el = take idx ls ++ el : drop idx ls 

Danh sách el : drop idx ls reuses đuôi của danh sách ban đầu, vì vậy bạn chỉ cần tạo ra một danh sách mới lên đến idx (đó là những gì các take chức năng nào). Nếu bạn muốn làm điều đó bằng đệ quy rõ ràng, bạn có thể xác định nó như vậy:

add ls 0 el = el : ls 
add (x:xs) idx el 
    | idx < 0 = error "Negative index for add" 
    | otherwise = x : add xs (idx - 1) el 
add [] _ el = [el] 

này reuses đuôi của danh sách trong cùng một cách (đó là el : ls trong trường hợp đầu tiên).

Vì dường như bạn gặp khó khăn khi xem danh sách được liên kết như thế nào, hãy rõ ràng về danh sách được liên kết là gì: Đây là cấu trúc dữ liệu bao gồm ô, trong đó mỗi ô có giá trị và tham chiếu đến mục tiếp theo . Trong C, nó có thể được định nghĩa là:

struct ListCell { 
void *value; /* This is the head */ 
struct ListCell *next; /* This is the tail */ 
} 

trong Lisp, nó được định nghĩa như (head . tail), nơi head là giá trị và tail là tham chiếu đến mục tiếp theo.

Trong Haskell, nó được định nghĩa là data [] a = [] | a : [a], trong đó a là giá trị và [a] là tham chiếu đến mục tiếp theo.

Như bạn thấy, các cấu trúc dữ liệu này đều tương đương nhau. Sự khác biệt duy nhất là trong C và Lisp, không hoàn toàn chức năng, giá trị đầu và đuôi là những thứ bạn có thể thay đổi. Trong Haskell, bạn không thể thay đổi chúng.

Answer 2

Haskell là một ngôn ngữ lập trình hoàn toàn chức năng. Điều này có nghĩa là không có thay đổi nào có thể được thực hiện.

Danh sách không phải là loại trừu tượng, chỉ là danh sách được liên kết.

Bạn có thể nghĩ rằng trong số họ được xác định theo cách này:

data [a] = a : [a] | [] 

mà là giống như cách một danh sách liên kết được định nghĩa - Một yếu tố đầu và (một con trỏ tới) phần còn lại.

Lưu ý rằng điều này không khác nhau trong nội bộ - Nếu bạn muốn có các loại hiệu quả hơn, hãy sử dụng Sequence hoặc Array. (Nhưng vì không có thay đổi nào được cho phép, bạn không cần phải sao chép danh sách để phân biệt giữa các bản sao, có thể là hiệu suất cao hơn so với ngôn ngữ mệnh lệnh)

Answer 3

Mã của bạn có thể hoạt động nhưng chắc chắn không tối ưu. Lấy trường hợp bạn muốn chèn một mục tại index 0. Một ví dụ:

add [200, 300, 400] [] 0 100 

Nếu bạn làm theo các nguồn gốc cho điều này, bạn kết thúc với:

add [200, 300, 400] [] 0 100 
add [300, 400] (200:100:[]) (-1) 100 
add [400] (300:[200, 100]) (-2) 300 
add [] (400:[300, 200, 100]) (-3) 400 
reverse [400, 300, 200, 100] 
[100, 200, 300, 400] 

Nhưng chúng tôi chỉ thêm một mục vào đầu danh sách! Một hoạt động như vậy rất đơn giản! Đó là (:)

add [200, 300, 400] [] 0 100 
100:[200, 300, 400] 
[100, 200, 300, 400] 

Hãy nghĩ xem danh sách thực sự cần được đảo ngược bao nhiêu.

Bạn hỏi liệu thời gian chạy có thay đổi các con trỏ trong danh sách được liên kết hay không. Bởi vì các danh sách trong Haskell là bất biến, không ai (thậm chí không phải là thời gian chạy) sửa đổi các con trỏ trong danh sách liên kết. Đây là lý do tại sao, ví dụ, nó là giá rẻ để gắn thêm một mục vào mặt trước của một danh sách, nhưng đắt tiền để nối thêm một phần tử ở mặt sau của một danh sách. Khi bạn thêm một mục vào trước danh sách, bạn có thể sử dụng lại tất cả danh sách hiện có. Nhưng khi bạn thêm một mục vào cuối, nó phải xây dựng một danh sách liên kết hoàn toàn mới. Tính bất biến của dữ liệu được yêu cầu để các hoạt động ở mặt trước của danh sách có giá rẻ.

Answer 4

Re: thêm một phần tử vào cuối của một danh sách, tôi muốn đề nghị sử dụng (++) điều hành và splitAt chức năng:

add xs a n = beg ++ (a : end) 
    where 
    (beg, end) = splitAt n xs 

Các List là một danh sách liên kết, nhưng nó chỉ đọc. Bạn không thể sửa đổi một mã số List - thay vào đó bạn hãy tạo cấu trúc List mới có các thành phần bạn muốn. Tôi đã không đọc nó, nhưng this book có thể nhận được câu hỏi cơ bản của bạn.

HTH

Answer 5

Trong Haskell, "kiểu dữ liệu" và "loại trừu tượng" là những thuật ngữ của nghệ thuật:

• A "kiểu dữ liệu" (mà không phải là trừu tượng) có nhà xây dựng giá trị hữu hình mà bạn có thể khớp mẫu trên các biểu thức hoặc định nghĩa chức năng ở dạng case.

• "Loại trừu tượng" không có hàm tạo giá trị hiển thị, do đó bạn không thể khớp mẫu trên các giá trị của loại.

Cho một loại a, [a] (danh sách a) là một dữ liệu loại vì bạn có thể mô hình phù hợp trên các nhà thầu khuyết điểm có thể nhìn thấy (bằng văn bản :) và nil (viết []). Một ví dụ về một kiểu trừu tượng sẽ là IO a, mà bạn không thể giải mã bằng kết hợp mẫu.

Answer 6

Trình biên dịch được tự do chọn bất kỳ đại diện nội bộ nào mà nó muốn cho một danh sách. Và trong thực tế nó thực sự khác nhau. Rõ ràng danh sách "[1 ..]" không được triển khai như là một chuỗi các ô đối kháng cổ điển. Trong thực tế, một danh sách lười được lưu trữ như một phần tử đánh giá một ô chứa giá trị tiếp theo và phần tiếp theo (một phần cơ bản là một con trỏ hàm cộng với các đối số cho hàm, được thay thế bằng giá trị thực tế). một khi hàm được gọi). Mặt khác, nếu trình phân tích nghiêm ngặt trong trình biên dịch có thể chứng minh rằng toàn bộ danh sách sẽ luôn được đánh giá thì trình biên dịch chỉ tạo toàn bộ danh sách dưới dạng một chuỗi các ô khuyết điểm.