Điều kiện cho chức năng bản đồ

Question

Các chức năng bản đồ (Seq.map, List.map etc) có điều kiện ngầm định rằng đầu ra có cùng số mục như đầu vào không? Đi xa hơn, nếu chúng ta có một số chức năng Tree.map, có giả định rằng "hình dạng" của các cây đầu vào và đầu ra giống nhau không?

Lý do tôi hỏi là tôi luôn đưa ra giả định (và tôi nghi ngờ rằng rất nhiều mã bản đồ trên chuỗi quá), nhưng sau đó tôi phát hiện ra rằng Set.map có thể trả về một tập nhỏ hơn nếu chức năng ánh xạ tạo ra các bản sao. Vì vậy, hoặc giả định của tôi là không hợp lệ, hoặc Set không nên được coi là một chuỗi cho các mục đích lập bản đồ. Đó là nó?

Answer 1

Nhiều quan điểm khác nhau, đây là của tôi:

Chúng ta có thể nghĩ về tất cả map chức năng/phương pháp như trường hợp cụ thể của Haskell của fmap của Functors. Từ định nghĩa đó, chúng ta có thể giả định rằng cấu trúc sẽ được giữ nguyên (cộng với một số thuộc tính thú vị khác). Tuy nhiên, trong .NET không có Typeclasses để chúng ta có thể định nghĩa map đối với 'Functors bị giới hạn', hậu quả là một số thuộc tính Functor sẽ không được giữ nguyên, nhưng vì không có mã chung sẽ bị ảnh hưởng nên tác động bị giới hạn.

Vì vậy, không có gì ngăn chúng tôi để xác định map qua:

• Sets (hạn chế: các chức năng phải là 'a ->' b khi 'a và' b: so sánh và nên injective)
• Strings (hạn chế: các chức năng nên được char-> char)
• Nullables (hạn chế: các chức năng nên được 'a ->' b nơi 'b không phải là một loại tài liệu tham khảo)

Lưu ý rằng trong s các trường hợp có các hạn chế ở cả hai loại và mức giá trị, ví dụ để đặt giới hạn ở mức loại là cả hai loại 'a và' b nên có so sánh trong khi giới hạn trên giá trị hàm là hàm phải là injective.

Nếu ngôn ngữ có thể thể hiện ràng buộc mức loại, trình biên dịch sẽ phát ra lỗi khi các yêu cầu này không được đáp ứng.

Đối với các giá trị hàm không có giới hạn biên dịch mặc dù chúng tôi có thể tạo các kiểm tra đơn vị nếu chúng tôi muốn đảm bảo chúng đúng. Nhưng điều gì sẽ xảy ra nếu chúng ta không quan tâm đến việc hạn chế các chức năng đó?

Vâng, miễn là chúng tôi hiểu rằng một số thuộc tính Functor sẽ không được tuân thủ thì không có gì sai khi sử dụng bản đồ trên một số bị giới hạn Functor.

Vì vậy, chúng tôi có thể xác định map trên các cấu trúc như danh sách được sắp xếp, tất nhiên chúng tôi không thể giả định rằng map a >> map b sẽ luôn luôn tương đương với map (a >> b) trong những trường hợp này. Hạn chế ở đây là hàm phải là monotonically increasing.

LƯU Ý: Đối với Haskell có một package với một functor hạn chế và một thể hiện cho Bộ

Answer 2

Có, thông thường bạn mong đợi map để giữ hình dạng (và do đó bảo toàn kích thước). Nhưng đối với các bộ, điều này rõ ràng không thể nói chung vì các bộ phải tuân theo một số luật bổ sung (như không có phần tử trùng lặp nào - vì vậy, Set.map (f : X -> bool) sẽ không giữ nguyên kích thước của bộ nếu nó được áp dụng cho bộ có nhiều hơn hai phần tử trong đó) .

Answer 3

Có, tôi mong đợi một hàm map để tôn trọng cấu trúc của đầu vào (mặc dù nhiều triển khai có thể sẽ không có thử nghiệm rõ ràng).

Trong trường hợp của Set.map, người ta có thể tranh luận rằng việc thực hiện nhất định (tham số) map chính nó là đúng, nhưng các chức năng lập luận có được injective cho tổng thể chức năng lập bản đồ là cấu trúc bảo quản. Vì vậy, thực sự, đối với các bộ, nó là một thuộc tính kết hợp của 2 hàm.

Sẽ dễ dàng để bọc Set.map với một số xác thực để kiểm tra tính năng tiêm của hàm đối số khi được áp dụng.

Answer 4

Bộ có một chút phức tạp, bởi vì bạn chỉ có thể tạo tập hợp những thứ mà bạn có thể kiểm tra xem chúng có bình đẳng không. Trên thực tế, các bộ F # thực sự được biểu diễn dưới dạng cây, vì vậy bạn cần có khả năng so sánh chúng.

này cũng có nghĩa là map chức năng cho bộ là không giống như các map chức năng cho các danh sách:

List.map : ('a -> 'b) -> 'a list -> 'b list 
Set.map : ('a -> 'b) -> Set<'a> -> Set<'b>) when 'a : comparison and 'b : comparison 

Thực tế là bạn phải có khả năng để so sánh các 'b giá trị giải thích tại sao map chức năng trên các bộ có thể thực hiện nhiều hơn chức năng map thông thường trên các danh sách và trình tự. Vì vậy, nó không phải là một hoạt động bản đồ bình thường!

(Tất nhiên, có thể có cách khác để phá vỡ điều này trong F # - chức năng map có thể trả về danh sách trống - nhưng sau đó loại kết quả được phỏng đoán sẽ là 'c list do đó cũng sẽ là loại bản đồ khác).

Answer 5

Bản đồ thuật ngữ bắt nguồn từ toán học và chỉ đề cập đến một hàm. Trong chính nó, nó không làm cho một tuyên bố như thế nào kết quả được đại diện. Tôi cho rằng câu trả lời phụ thuộc vào loại nội dung đang được ánh xạ.

Giả sử của tôi không hợp lệ hoặc Set không được coi là chuỗi cho mục đích lập bản đồ. Đó là nó?

Tôi muốn giả định rằng không hợp lệ nói chung, nhưng phải giữ đúng nơi có thể áp dụng hợp lý.Ví dụ, nếu một cây đòi hỏi một cấu trúc phụ thuộc vào các giá trị chứa, và một cây như vậy được ánh xạ tới một giá trị khác, thì không thể tạo ra một kết quả hợp lệ để duy trì cấu trúc của cây.

Tuy nhiên, bạn có thể coi một tập hợp làm chuỗi để lập bản đồ, giống như mọi thứ có thể chuyển đổi thành IEnumerable<>. Chỉ cần sử dụng Seq.map thay vì Set.map.