Lập trình chức năng cho các thuật toán cơ bản

Question

Lập trình chức năng 'thuần túy' tốt như thế nào cho việc triển khai thường trình cơ bản, ví dụ: sắp xếp danh sách, đối sánh chuỗi v.v ...?

Việc phổ biến các hàm cơ bản như vậy trong trình thông dịch cơ sở của bất kỳ ngôn ngữ chức năng nào cũng có nghĩa là chúng sẽ được viết bằng ngôn ngữ bắt buộc (c/C++). Mặc dù có nhiều ngoại lệ ..

Ít nhất, tôi muốn hỏi: Làm thế nào để mô phỏng phong cách bắt buộc khi viết mã bằng ngôn ngữ chức năng 'thuần túy'?

Answer 1

Làm thế nào tốt là 'tinh khiết' chức năng lập trình cho cơ bản thói quen triển khai, ví dụ sắp xếp danh sách, kết hợp chuỗi v.v ...?

Rất. Tôi sẽ làm các vấn đề của bạn trong Haskell, và tôi sẽ tiết lộ một chút về nó. Mục tiêu của tôi không phải là thuyết phục bạn rằng vấn đề có thể được thực hiện trong 5 ký tự (có thể là trong J!), Mà là để cho bạn ý tưởng về các cấu trúc.

import Data.List -- for `sort` 
stdlistsorter :: (Ord a) => [a] -> [a] 
stdlistsorter list = sort list 

Sắp xếp một danh sách bằng cách sử dụng chức năng sort từ Data.List

import Data.List -- for `delete` 
selectionsort :: (Ord a) => [a] -> [a] 
selectionsort [] = [] 
selectionsort list = minimum list : (selectionsort . delete (minimum list) $ list) 

Selection sort thực hiện.

quicksort :: (Ord a) => [a] -> [a] 
quicksort [] = [] 
quicksort (x:xs) = 
    let smallerSorted = quicksort [a | a <- xs, a <= x] 
     biggerSorted = quicksort [a | a <- xs, a > x] 
    in smallerSorted ++ [x] ++ biggerSorted 

Triển khai sắp xếp nhanh.

import Data.List -- for `isInfixOf` 
stdstringmatch :: (Eq a) => [a] -> [a] -> Bool 
stdstringmatch list1 list2 = list1 `isInfixOf` list2 

Chuỗi phù hợp sử dụng isInfixOf chức năng từ Data.list

Đó là thông thường để thực hiện như vậy cơ bản chức năng trong các thông dịch viên cơ sở của bất kỳ ngôn ngữ chức năng, mà có nghĩa là họ sẽ được ghi trong một bắt buộc ngôn ngữ (c/C++). Mặc dù có nhiều ngoại lệ ..

Tùy thuộc. Một số chức năng được thể hiện tự nhiên hơn một cách tự nhiên. Tuy nhiên, tôi hy vọng tôi đã thuyết phục bạn rằng một số thuật toán cũng được thể hiện một cách tự nhiên theo cách chức năng.

Ít nhất, tôi muốn hỏi: Làm thế nào khó khăn là nó bắt chước phong cách bắt buộc trong khi mã hóa trong 'tinh khiết' ngôn ngữ chức năng ?

Tùy thuộc vào mức độ khó mà bạn tìm thấy Monads trong Haskell. Cá nhân tôi thấy khá khó nắm bắt.

Answer 2

Nó hoạt động khá tốt theo cách khác vòng mô phỏng chức năng với phong cách bắt buộc.

Hãy nhớ rằng nội bộ của một thông dịch viên hoặc VM rất gần với kim loại và hiệu suất quan trọng là bạn nên xem xét đến cấp độ tháng mười một và đếm chu kỳ đồng hồ cho mỗi lệnh (như Smalltalk Dophin chỉ làm việc đó và kết quả thật ấn tượng). CPU là bắt buộc.

Nhưng không có vấn đề gì khi thực hiện tất cả việc triển khai thuật toán cơ bản - một trong những bạn đề cập là NOT mức độ thấp - chúng là cơ bản.

Answer 3

Gần như tất cả các ngôn ngữ lập trình hàm có một số cấu trúc để cho phép mã hóa bắt buộc (như do trong Haskell). Có nhiều vấn đề miền không thể được giải quyết bằng lập trình hàm "thuần túy". Một trong số đó là giao thức mạng, ví dụ: nơi bạn cần một loạt lệnh theo đúng thứ tự. Và những điều như vậy không cho vay tốt cho lập trình chức năng thuần túy.

Tôi phải đồng ý với Lothar, tuy nhiên, danh sách sắp xếp và đối sánh chuỗi không thực sự là ví dụ bạn cần giải quyết một cách bất hợp pháp. Có những thuật toán nổi tiếng cho những thứ như vậy và chúng có thể được triển khai hiệu quả bằng các ngôn ngữ chức năng.

Answer 4

Tôi nghĩ rằng 'các thuật toán' (ví dụ: thân phương pháp và cấu trúc dữ liệu cơ bản) là nơi lập trình hàm là tốt nhất. Giả sử không có gì hoàn toàn IO/phụ thuộc vào nhà nước, các chương trình chức năng trội là các thuật toán và cấu trúc dữ liệu, thường dẫn đến mã ngắn hơn/đơn giản hơn/sạch hơn so với các giải pháp bắt buộc. (Đừng mô phỏng phong cách bắt buộc, kiểu FP tốt hơn cho hầu hết các loại nhiệm vụ này.)

Bạn muốn đôi khi phải xử lý IO hoặc hiệu năng cấp thấp và bạn muốn OOP phân vùng cao cấp thiết kế và kiến ​​trúc của một chương trình lớn, nhưng "trong nhỏ", nơi bạn viết hầu hết mã của bạn, FP là một chiến thắng.

cũng

How does functional programming affect the structure of your code?

Answer 5

Xem Tôi không biết về danh sách phân loại, nhưng bạn muốn được cứng ép để bootstrapp một ngôn ngữ mà không một số loại phù hợp với chuỗi trong trình biên dịch hoặc chạy. Vì vậy, bạn cần có thói quen đó để tạo ra ngôn ngữ. Vì không có nhiều điểm viết cùng một mã hai lần, khi bạn tạo thư viện cho các chuỗi phù hợp trong ngôn ngữ, bạn gọi mã được viết trước đó. Mức độ mà điều này xảy ra trong các bản phát hành liên tiếp sẽ phụ thuộc vào cách tự lưu trữ ngôn ngữ, nhưng trừ khi đó là một mục tiêu thiết kế mạnh mẽ sẽ không có lý do gì để thay đổi nó.

Answer 6

1) Tốt theo tiêu chuẩn nào? Bạn mong muốn những đặc tính nào?

Liệt kê sắp xếp? Dễ dàng.Hãy làm Quicksort trong Haskell:

sort [] = [] 
sort (x:xs) = sort (filter (< x) xs) ++ [x] ++ sort (filter (>= x) xs) 

Mã này có lợi thế là cực kỳ dễ hiểu. Nếu danh sách trống, nó được sắp xếp. Nếu không, hãy gọi phần tử đầu tiên x, tìm các phần tử nhỏ hơn x và sắp xếp chúng, tìm các phần tử lớn hơn x và sắp xếp các phần tử đó. Sau đó, nối các danh sách được sắp xếp với x ở giữa. Hãy thử làm cho cái nhìn đó dễ hiểu trong C++.

Tất nhiên, Mergesort nhanh hơn nhiều để sắp xếp danh sách được liên kết, nhưng mã cũng dài hơn 6 lần.

2) Rất dễ thực hiện phong cách bắt buộc trong khi vẫn hoạt động hoàn toàn. Bản chất của phong cách bắt buộc là sắp xếp các hành động. Các hành động được sắp xếp theo trình tự trong một thiết lập thuần túy bằng cách sử dụng các monads. Bản chất của monads là chức năng ràng buộc:

(Monad m) => (>>=) :: m a -> (a -> m b) -> m b 

Chức năng này tồn tại trong C++ và được gọi là ;.

Một chuỗi các hành động trong Haskell, ví dụ, được viết thusly:

putStrLn "What's your name?" >>= 
    const (getLine >>= \name -> putStrLn ("Hello, " ++ name)) 

Một số đường cú pháp có sẵn để làm cho cái nhìn này bắt buộc hơn (nhưng lưu ý rằng đây là chính xác cùng một mã):

do { 
    putStrLn "What's your name?"; 
    name <- getLine; 
    putStrLn ("Hello, " ++ name); 
}