Thuật toán nào khó thực hiện trong các ngôn ngữ chức năng?

Question

Tôi đang học các ngôn ngữ chức năng và tôi đã tìm thấy một số thuật toán (đặc biệt là các thuật toán sử dụng lập trình động) khó viết hơn và đôi khi kém hiệu quả trong trường hợp xấu nhất. Có một lớp thuật toán nào kém hiệu quả hơn trong các ngôn ngữ chức năng với các biến không thay đổi và do đó có tác dụng phụ không?

Và có một tham chiếu nào đó mà một người nào đó có thể chỉ cho tôi điều đó sẽ giúp bạn viết các thuật toán khó hơn (có lẽ những thuật toán được tối ưu hóa bởi trạng thái chia sẻ) không?

Cảm ơn

Answer 1

Trước hết, như bạn có thể hoặc có thể không biết, một số ngôn ngữ, bao gồm Haskell, thực hiện chia sẻ, mà làm giảm bớt một số các vấn đề mà bạn có thể nghĩ đến.

Trong khi câu trả lời của Andrew chỉ vào Turing đầy đủ, nó không thực sự trả lời câu hỏi về thuật toán nào là cứng để triển khai bằng các ngôn ngữ chức năng. Thay vì yêu cầu các thuật toán khó triển khai bằng ngôn ngữ chức năng, mọi người thường hỏi cấu trúc dữ liệu khó triển khai bằng ngôn ngữ chức năng.

Câu trả lời đơn giản cho điều này: những thứ liên quan đến con trỏ. Không có chức năng tương đương với con trỏ khi bạn đi sâu vào cấp máy, có bản đồ và bạn có thể biên dịch một số cấu trúc dữ liệu một cách an toàn xuống các mảng hoặc những thứ được thực hiện như con trỏ, nhưng ở mức cao, bạn có thể không thể hiện mọi thứ bằng cách sử dụng các cấu trúc dữ liệu dựa trên con trỏ dễ dàng như bạn có thể sử dụng trong các ngôn ngữ bắt buộc.

Để làm được việc này, một số điều đã được thực hiện:

• Kể từ khi con trỏ hình thành cơ sở cho một bảng băm, và kể từ khi bảng băm thực sự chỉ là thực hiện một bản đồ, bản đồ chức năng hiệu quả đã được nghiên cứu một cách toàn diện . Trên thực tế, Chris Okasaki có một cuốn sách ("Cấu trúc dữ liệu chức năng thuần túy") chi tiết nhiều, nhiều cách để thực hiện các bản đồ chức năng, deques, ...
• Vì con trỏ có thể được sử dụng để biểu diễn các nút bên trong giao điểm của một số lớn hơn cấu trúc dữ liệu, cũng đã có công việc trong lĩnh vực này. Sản phẩm là dây kéo , một cấu trúc hiệu quả thể hiện ngắn gọn chức năng tương đương với kỹ thuật "con trỏ bên trong của cấu trúc sâu hơn".
• Vì con trỏ có thể được sử dụng để thực hiện tính toán hiệu ứng bên, monads đã được sử dụng để diễn tả loại tính toán này theo cách khá. Vì việc theo dõi trạng thái khó khăn trong việc sắp xếp xung quanh, việc sử dụng cho monads là để cho bạn mặt nạ một hành vi bắt buộc xấu xí của chương trình của bạn và sử dụng hệ thống kiểu để đảm bảo rằng chương trình được xích lại với nhau một cách chính xác (thông qua liên kết đơn thuần) .

Trong khi tôi muốn như để nói rằng bất kỳ thuật toán nào cũng có thể được dịch từ một mệnh lệnh sang hàm rất dễ dàng, điều này không đơn giản. Tuy nhiên, tôi khá thuyết phục rằng vấn đề không phải là thuật toán, nhưng cấu trúc dữ liệu họ thao tác, dựa trên khái niệm bắt buộc của nhà nước.Bạn có thể tìm thấy danh sách dài các cấu trúc dữ liệu chức năng trong this post.

Mặt trái của tất cả những điều này là nếu bạn bắt đầu sử dụng một phong cách thuần túy hơn, nhiều phần phức tạp trong chương trình của bạn bị hỏng và nhiều nhu cầu cấu trúc dữ liệu bắt buộc biến mất (ví dụ, việc sử dụng con trỏ rất phổ biến trong các ngôn ngữ bắt buộc là triển khai các mẫu thiết kế khó chịu, thường chuyển thành sử dụng thông minh đa hình và typeclases ở cấp chức năng).

EDIT: Tôi tin rằng bản chất của câu hỏi này đề cập đến cách diễn tả tính toán theo cách chức năng. Tuy nhiên, cần lưu ý rằng có nhiều cách để xác định tính toán trạng thái theo cách chức năng. Hay đúng hơn, có thể sử dụng các kỹ thuật chức năng để giải thích về tính toán trạng thái. Ví dụ, dự án Ynot thực hiện điều này bằng cách sử dụng một đơn nguyên tham số trong đó các sự kiện về đống (trong dạng logic tách) được theo dõi bởi các liên kết đơn thuần.

Nhân tiện, ngay cả trong ML, tôi không thấy lý do tại sao lập trình động là rằng khó. Nó có vẻ như các vấn đề lập trình động, thường xây dựng các bộ sưu tập của một số trình tự để tính toán câu trả lời cuối cùng, có thể tích lũy các giá trị được xây dựng thông qua các đối số cho hàm, có thể yêu cầu tiếp tục trong một số trường hợp. Sử dụng đệ quy đuôi không có lý do gì có thể không được đẹp và hiệu quả như trong ngôn ngữ mệnh lệnh. Bây giờ chắc chắn, bạn có thể chạy vào đối số rằng nếu các giá trị này là danh sách (ví dụ), trước tiên chúng ta có thể thực hiện chúng như mảng, nhưng cho rằng, xem nội dung của bài viết thích hợp :-)

Answer 2

Hãy nhớ rằng hầu hết ngôn ngữ chức năng cho phép một số khái niệm về tác dụng phụ; chúng có thể bị cau mày, hạn chế sử dụng cục bộ, v.v., nhưng bạn vẫn có thể sử dụng chúng. Trong OCaml, Haskell, F #, Scala hoặc Clojure, bạn có thể sử dụng các mảng có thể thay đổi nếu cần.

Vì vậy, nếu bạn tìm thấy thuật toán mà bạn có công thức sử dụng mảng có thể thay đổi và bạn cần tạo lại nó bằng một trong các ngôn ngữ này, chỉ cần sử dụng mảng có thể thay đổi!

Không có lý do gì để buộc bản thân phải làm mọi thứ bằng cách sử dụng một mô hình lập trình đơn; có một số lĩnh vực vấn đề trong đó lập trình bắt buộc là (cho kiến ​​thức hiện tại của chúng tôi) là công cụ phù hợp nhất cho công việc, cũng giống như có các lĩnh vực mà lập trình logic là tuyệt vời. Nếu nó giúp bạn tiết kiệm thời gian và công sức để tạo ra một cách sử dụng địa phương, đóng gói của một trong những mô hình này, bạn không nên ngần ngại sử dụng chúng.

Ví dụ, Sieve of Eratosthenes là tầm thường để thực hiện với các mảng có thể thay đổi và khó bắt chước hơn (hợp lý hiệu quả) theo cách hoàn toàn chức năng: xem Melissa O'Neill bài viết để biết chi tiết.

Mặt khác, việc tìm ra các giải pháp bất biến cho một vấn đề cụ thể có thể là một bài tập thú vị và khai sáng. Cuốn sách "Cấu trúc dữ liệu thuần túy về chức năng" của Crhis Okasaki là một ví dụ điển hình về việc cải cách rất tốt các thuật toán một cách thuần túy. Nếu bạn quan tâm đến các thuật toán của mình (chứ không phải là ứng dụng của họ cho vấn đề của bạn), điều này có thể là một hoạt động rất thú vị.

(Đối với ví dụ về sử dụng chia sẻ để tối ưu hóa một thuật toán hoàn toàn chức năng, xem Richard Bird và Ralf Hinze năm 2003 Functional Pearl: Trouble Shared is Trouble Halved.)

Answer 3

Người ta có thể thực hiện các tính năng bắt buộc với chi phí tiệm cận thấp, vì vậy trong một ý nghĩa trừu tượng không có khó khăn thiết yếu trong việc dịch mã bắt buộc đối với vũ trụ thuần túy chức năng. Trong thực tế, tất nhiên, có. :-) Hãy xem Pippenger "Pure so với Impure Lisp" và papers that cite it.