Cấu trúc và lập trình đại số

Question

Có thể bất cứ ai cho tôi một ví dụ về cách chúng tôi có thể cải thiện khả năng sử dụng lại mã của chúng tôi bằng cách sử dụng các cấu trúc đại số như nhóm, monoids và nhẫn? (hoặc làm thế nào tôi có thể sử dụng các loại cấu trúc trong lập trình, biết ít nhất là tôi đã không tìm hiểu tất cả các lý thuyết trong highschool cho không có gì).

Tôi nghe điều này là có thể nhưng tôi không thể tìm ra cách áp dụng chúng trong lập trình và áp dụng rộng rãi toán học hardcore trong lập trình.

Answer 1

Nó không thực sự là công cụ toán học giúp như là tư duy toán học. Trừu tượng là chìa khóa trong lập trình. Chuyển đổi các khái niệm thực sự thành số và quan hệ là những gì chúng ta làm mỗi ngày. Đại số là mẹ của tất cả, đại số là tập hợp các quy tắc xác định tính chính xác, nó là mức trừu tượng cao nhất, vì vậy, hiểu đại số có nghĩa là bạn có thể suy nghĩ rõ ràng hơn, nhanh hơn, hiệu quả hơn. Bắt đầu từ lý thuyết tập hợp vào lý thuyết thể loại, lý thuyết tên miền, vv tất cả mọi thứ đến từ những thách thức thực tế, trừu tượng và yêu cầu tổng quát. Trong thực tế phổ biến, bạn sẽ không cần phải thực sự biết những điều này, mặc dù nếu bạn đang nghĩ đến việc phát triển các công cụ như AI Đại lý, ngôn ngữ lập trình, khái niệm cơ bản và các công cụ thì chúng là phải.

Answer 2

Như tôi đã không hề biết công cụ này tồn tại trong thế giới khoa học máy tính, xin vui lòng bỏ qua câu trả lời này;)

---

Tôi không nghĩ rằng hai lĩnh vực (không có ý định chơi chữ) có bất cứ chồng chéo lên nhau. Nhẫn/trường/nhóm đối phó với đối tượng toán học. Hãy xem xét một phần định nghĩa của một trường:

Đối với mỗi F, có một phần tử −a trong F, sao cho + (−a) = 0. Tương tự, đối với bất kỳ F nào khác hơn 0, tồn tại một phần tử^−1 trong F, sao cho a · a^−1 = 1. (Các phần tử a + (−b) và a · b^−1 cũng được biểu thị a - b và a/b, tương ứng.) Nói cách khác, các phép toán trừ và phân chia tồn tại.

Điều này có nghĩa gì về mặt lập trình? Tôi chắc chắn không thể có một nghịch đảo phụ của một đối tượng list trong Python (tốt, tôi chỉ có thể phá hủy các đối tượng, nhưng đó là giống như nhân ngược nghịch đảo.Tôi đoán bạn có thể nhận được một nơi nào đó cố gắng để xác định một vòng Python, nhưng nó sẽ không hoạt động cuối cùng). Thậm chí không nghĩ về chia lists ...

Như cho mã dễ đọc, tôi đã hoàn toàn không biết thế nào điều này thậm chí có thể được áp dụng, vì vậy ứng dụng này là không thích hợp.

Đây là giải thích của tôi, nhưng là một toán học lớn có thể làm cho tôi mù với thuật ngữ khác từ các lĩnh vực khác nhau (bạn biết tôi đang nói về cái nào).

Answer 3

Trong lập trình chức năng, đặc biệt. Haskell, nó phổ biến cho các chương trình cấu trúc biến đổi các trạng thái như là các monads. Làm như vậy có nghĩa là bạn có thể sử dụng lại các thuật toán chung trên monads trong các chương trình rất khác nhau.

Thư viện mẫu chuẩn C++ có khái niệm về monoid. Ý tưởng là một lần nữa các thuật toán chung có thể yêu cầu một hoạt động để đáp ứng các tiên đề của monoids cho tính chính xác của chúng.

Ví dụ: nếu chúng tôi có thể chứng minh loại T chúng tôi đang hoạt động (số, chuỗi, bất kỳ) bị đóng trong hoạt động, chúng tôi biết chúng tôi sẽ không phải kiểm tra các lỗi nhất định; chúng tôi luôn nhận được T hợp lệ. Nếu chúng ta có thể chứng minh rằng hoạt động là liên kết (x * (y * z) = (x * y) * z), thì chúng ta có thể tái sử dụng kiến ​​trúc fork-join; một cách đơn giản nhưng song song được thực hiện trong các thư viện khác nhau.

Answer 4

Khoa học máy tính dường như nhận được rất nhiều mileage trong số category theory những ngày này. Bạn nhận được monads, monoids, functors - một toàn bộ bestiary của các thực thể toán học đang được sử dụng để cải thiện khả năng sử dụng lại mã, khai thác sự trừu tượng của toán học trừu tượng.

Answer 5

Danh sách là các monoids miễn phí với một trình tạo, cây nhị phân là các nhóm. Bạn có biến thể hữu hạn hoặc vô hạn.

điểm Bắt đầu:

• http://en.wikipedia.org/wiki/Algebraic_data_type
• http://en.wikipedia.org/wiki/Initial_algebra
• http://en.wikipedia.org/wiki/F-algebra

Bạn có thể muốn tìm hiểu lý thuyết thể loại, và lý thuyết loại cách tiếp cận cấu trúc đại số: nó là chính xác đường đi ngôn ngữ lập trình chức năng tiếp cận cấu trúc dữ liệu, ít nhất là shapewise.

Ví dụ: các loại cây A là

Tree A =() | Tree A | Tree A * Tree A 

mà đọc như sự tồn tại của một đẳng cấu (*) (tôi đặt G = Tree A)

1 + G + G x G -> G 

mà là giống như một cấu trúc nhóm

phi : 1 + G + G x G -> G 
() € 1   -> e 
x € G   -> x^(-1) 
(x, y) € G x G -> x * y 

Thật vậy, cây nhị phân có thể biểu diễn các biểu thức và chúng tạo thành một cấu trúc đại số ure. Một phần tử của G đọc dưới dạng nhận dạng, một nghịch đảo của một phần tử hoặc sản phẩm của hai phần tử. Cây nhị phân là một lá, một cây duy nhất hoặc một cặp cây. Lưu ý sự giống nhau về hình dạng.

(*) cũng như tài sản chung, nhưng chúng là hai trong số chúng (cây hữu hạn hoặc cây lười vô hạn) vì vậy tôi sẽ không chia sẻ chi tiết.

Answer 6

Monoids có mặt khắp mọi nơi trong lập trình. Trong một số ngôn ngữ lập trình, ví dụ: Haskell, chúng tôi có thể làm cho các monoids rõ ràng http://blog.sigfpe.com/2009/01/haskell-monoids-and-their-uses.html