Tại sao functor danh sách đại diện cho một bối cảnh của sự lựa chọn không xác định?

Question

Trích dẫn này có ý nghĩa gì?

the list functor represents a context of nondeterministic choice; 

Trong ngữ cảnh của Functors trong lập trình hàm.

Tôi nghĩ rằng tôi hiểu rằng một Functor là một "container" của một số loại cùng với khả năng áp dụng một chức năng thống nhất cho các thành phần trong container mà không thay đổi cấu trúc. Vì vậy, có thể là một Functor đại diện cho một bối cảnh hoặc container với thất bại có thể, nhưng tại sao danh sách đại diện cho một bối cảnh hoặc container với sự lựa chọn không xác định?

Answer 1

Tốt nhất tôi có thể nói, phép tính là "không xác định" nếu có nhiều câu trả lời có thể. Vâng, một danh sách có thể chứa nhiều câu trả lời có thể. Vì vậy đó là lý do tại sao.

(Là tại sao nó được gọi là không xác định, tôi không có ý tưởng ... Tôi đã có dự kiến ​​không xác định nghĩa ngẫu nhiên, mà là một cái gì đó hoàn toàn khác nhau.)

Answer 2

"cổ điển" tính toán mất 1 đầu vào và cung cấp cho 1 đầu ra. Điều bạn muốn đại diện với các tính toán không xác định này là: Tôi có thể nói gì về đầu ra nếu tôi không chắc về đầu vào?

Hai cách thông thường để đại diện cho sự không chắc chắn là cần cân nhắc:

1. mà đầu vào là một phần tử của một cho thiết
2. rằng các đầu vào được đưa ra bởi một phân bố xác suất gọi

Ví dụ, hãy xem xét hàm (2 *) để tăng gấp đôi đầu vào. Bạn có thể nói gì về đầu ra của hàm đó khi đầu vào là kết quả của cuộn chết?

1. Tôi biết chết có 6 khuôn mặt sao cho kết quả là trong tập {2,4,6,8,10,12}
2. Tôi biết xác suất của mỗi mặt là 1/6 vì vậy tôi biết rằng mỗi số này có xác suất 1/6 xuất hiện

Danh sách functor đại diện cho tính toán không xác định theo nghĩa 1: nó đại diện cho các bộ theo danh sách.

Answer 3

xem xét như sau:

foo = do 
    x <- [1 .. 10] 
    y <- [2, 3, 5, 7] 
    return (x * y) 

là gì foo? Vâng, đó là x * y, trừ trường hợp được lựa chọn không xác định của x là một số từ 1 đến 10, và y là một trong hai 2, 3, 5, hoặc 7. Do đó, foo là [2, 3, 5, 7, 4, 6, 10, 14, etc... ]

Answer 4

Theo truyền thống, trong computability và phức tạp, một mô hình tính toán không xác định đã đề cập đến một mô hình trong trường hợp đó bạn có thể "phân nhánh". Wikipedia giải thích nó như vậy:

Trong lý thuyết độ phức tạp tính toán, thuật toán không xác định là những người mà, tại mỗi bước có thể, có thể cho phép nhiều continuations (tưởng tượng một người đàn ông đi bộ xuống một con đường trong một khu rừng và, mỗi khi ông bước hơn nữa, anh ta phải chọn cái nĩa nào trên con đường mà anh ta muốn dùng).Các thuật toán này không đi đến giải pháp cho mọi đường dẫn tính toán có thể có; tuy nhiên, họ được đảm bảo đến một giải pháp chính xác cho một số con đường (tức là, người đàn ông đi qua khu rừng chỉ có thể tìm thấy cabin của mình nếu anh ta chọn một số kết hợp các đường dẫn "chính xác"). Các lựa chọn có thể được hiểu là dự đoán trong quá trình tìm kiếm.

Trong danh sách đơn lẻ, đây chính xác là những gì bạn đang làm. Ví dụ, hãy xem xét giải pháp này lên phiên bản Quyết định của clique problem, trong danh sách các đơn nguyên:

cliques :: Int -> Graph -> [[Node]] 
cliques 0 _ = [[]] 
cliques minCliqueSize graph = do 
    v <- nodes graph 
    vs <- cliques (minCliqueSize - 1) (deleteNode v graph) 
    mapM_ (\ w -> guard (isAdjacent v w graph)) vs 
    return (v:vs) 

Đây chính là cách bạn muốn chương trình ví dụ một máy Turing không xác định để giải quyết vấn đề clique.

Answer 5

Ngoài việc xem functor làm vùng chứa, bạn cũng có thể xem nó như một loại ngữ cảnh nhất định. Giá trị của bạn nằm trong ngữ cảnh đó và nếu bạn muốn vận hành chúng, bạn sử dụng map để nâng một hàm vào ngữ cảnh. Một cách khác để đặt nó là giá trị của bạn được tăng cường với ngữ cảnh đó.

Để hiểu cách functor danh sách là ngữ cảnh của sự lựa chọn không xác định, có thể hữu ích để xem cách functor khác là một ngữ cảnh: The functor Có thể là ngữ cảnh của một phép tính có thể thất bại. Nếu bạn cố gắng áp dụng một hàm cho một giá trị trong hàm functor có thể, giá trị kết quả sẽ vẫn giữ nguyên ngữ cảnh của việc tính toán không thành công ở vị trí đầu tiên hay không.

Trong cùng một cách, danh sách có thể được xem là kết quả của phép tính không có kết quả xác định, nhưng kết quả có thể được chọn không xác định từ một trong nhiều giá trị. Nếu bạn cố gắng ánh xạ một hàm trên danh sách có 3 phần tử, các phần tử đó sẽ được thay đổi, nhưng ngữ cảnh có thể chọn giữa ba giá trị sẽ vẫn giữ nguyên.

Vay một chút từ Dan Burtons câu trả lời, nhìn vào các ký hiệu monadic cho các danh sách:

foo = do 
    x <- [1 .. 10] 
    y <- [2, 3, 5, 7] 
    return (x * y) 

Có vẻ như lúc đầu hơi lạ, vì các ký hiệu dường như chỉ ra rằng bạn có thể trích xuất một giá trị duy nhất từ mỗi danh sách, nhưng sau đó bạn nhận được kết quả là một danh sách dài 40 phần tử. Nó có ý nghĩa hơn khi bạn nhìn vào các functors (tốt, monads trong trường hợp này) như là một bối cảnh cho một giá trị duy nhất. Trong ví dụ, x và y là những giá trị như vậy, nhưng ngữ cảnh của chúng là chúng không xác định được. Khi bạn nhân hai giá trị như vậy, bạn càng nhận được nhiều điều không xác định, dẫn đến một danh sách dài hơn. Vì vậy, với monads và >>=, bối cảnh có thể được thay đổi, trong khi với functors và map, nó không thể.