Là một giảng viên tại Hogeschool Utrecht, tôi dạy Python cho những sinh viên mới học lập trình. Gần đây tôi đã bắt đầu lại nỗ lực học Haskell, tôi có thể đồng cảm với cảm giác lạc lõng hoặc choáng ngợp của học sinh. Nó đưa tôi trở lại lần đầu tiên tôi bắt đầu viết mã. Nó không chỉ mang lại cho tôi niềm vui khi học được điều gì đó mới, mà quá trình này còn cho tôi cái nhìn sâu sắc về những điều chúng ta coi là hiển nhiên khi nói về mã và học một ngôn ngữ. cú pháp, phân tích vấn đề, các mẫu và cách tiếp cận
Trong bài đăng này, chúng tôi khám phá những điểm tương đồng và khác biệt trong các cách tiếp cận mệnh lệnh và chức năng để tích lũy các giá trị trên một chuỗi bằng Python và Haskell
Để minh họa, chúng ta sẽ tính tổng của một dãy [danh sách] các số nguyên mà không sử dụng hàm
def rec_sum[numbers]:
# Base case
if numbers == []:
return 0
# Split head and tail
x, *xs = numbers
# Recursive case
return x + rec_sum[xs]
result = rec_sum[[1, 2, 3]]
# Prints: 6
print[result]
Mẫu bộ tích lũy được sử dụng để thu thập thông tin từ một chuỗi và lưu kết quả vào một biến. Cốt lõi của ý tưởng là chúng ta khởi tạo một biến bộ tích lũy [trong các ví dụ sau được gọi là
def rec_sum[numbers]:
# Base case
if numbers == []:
return 0
# Split head and tail
x, *xs = numbers
# Recursive case
return x + rec_sum[xs]
result = rec_sum[[1, 2, 3]]
# Prints: 6
print[result]
Để tính tổng của một danh sách các số sử dụng mẫu bộ tích lũy, người ta sẽ bắt đầu đếm từ 0 và đối với mỗi số trong danh sách, hãy thêm số đã nói vào giá trị bộ tích lũy, cập nhật giá trị bộ tích lũy trong mỗi lần lặp lại. Đây là một cách suy nghĩ bắt buộc. hướng dẫn được viết theo kiểu cụ thể, từng bước, sửa đổi trạng thái của chương trình trong quá trình thực hiện
Trong Python, việc thực hiện tổng này sẽ như sau
def acc_sum[numbers]:
acc = 0
for number in numbers:
acc = acc + number
return acc
result = acc_sum[[1, 2, 3]]
# Prints: 6
print[result]
Có thể tìm thấy một cách khác để tích lũy giá trị mà không sửa đổi trạng thái trong đệ quy. Sử dụng đệ quy, giải pháp của một vấn đề phụ thuộc vào các giải pháp cho các trường hợp nhỏ hơn của cùng một vấn đề
Có ba quy tắc để một hàm đệ quy có hiệu quả
- Chức năng phải có một trường hợp cơ sở
- Hàm này có trường hợp đệ quy [cũng. trường hợp quy nạp] di chuyển về phía trường hợp cơ sở
- Hàm gọi chính nó một cách đệ quy
Trong các ngôn ngữ mệnh lệnh như Python, đệ quy có thể được thực hiện bằng cách tự gọi một hàm cho đến khi gặp một dạng trường hợp cơ sở nào đó. một giá trị duy nhất được trả về thay vì gọi lại chính nó
def rec_sum[numbers]:
# Base case
if numbers == []:
return 0
# Split head and tail
x, *xs = numbers
# Recursive case
return x + rec_sum[xs]
result = rec_sum[[1, 2, 3]]
# Prints: 6
print[result]
Chúng tôi kiểm tra xem trường hợp cơ sở của chúng tôi có được tìm thấy hay không bằng cách sử dụng câu lệnh if. nếu chúng tôi gặp một danh sách trống, chúng tôi trả về 0. Nếu đó không phải là trường hợp, chúng tôi tiếp tục trường hợp đệ quy. Sau đó, chúng tôi chia các số đầu vào thành đầu [được gọi là
def rec_sum[numbers]:
# Base case
if numbers == []:
return 0
# Split head and tail
x, *xs = numbers
# Recursive case
return x + rec_sum[xs]
result = rec_sum[[1, 2, 3]]
# Prints: 6
print[result]
def rec_sum[numbers]:
# Base case
if numbers == []:
return 0
# Split head and tail
x, *xs = numbers
# Recursive case
return x + rec_sum[xs]
result = rec_sum[[1, 2, 3]]
# Prints: 6
print[result]
def rec_sum[numbers]:
# Base case
if numbers == []:
return 0
# Split head and tail
x, *xs = numbers
# Recursive case
return x + rec_sum[xs]
result = rec_sum[[1, 2, 3]]
# Prints: 6
print[result]
def rec_sum[numbers]:
# Base case
if numbers == []:
return 0
# Split head and tail
x, *xs = numbers
# Recursive case
return x + rec_sum[xs]
result = rec_sum[[1, 2, 3]]
# Prints: 6
print[result]
def rec_sum[numbers]:
# Base case
if numbers == []:
return 0
# Split head and tail
x, *xs = numbers
# Recursive case
return x + rec_sum[xs]
result = rec_sum[[1, 2, 3]]
# Prints: 6
print[result]
Các bước trình thông dịch sẽ thực hiện để giải quyết đệ quy
rec_sum[[1, 2, 3]]
# Base condition not met: take head, call function on tail
1 + rec_sum[[2, 3]]
# Base condition not met: take head, call function on tail
2 + 1 + rec_sum[[3]]
# Base condition met: add 0 to all previous heads
3 + 2 + 1 + rec_sum[[]]
# Resulting expression
3 + 2 + 1 + 0
rec_sum[[1, 2, 3]]
# Base condition not met: take head, call function on tail
1 + rec_sum[[2, 3]]
# Base condition not met: take head, call function on tail
2 + 1 + rec_sum[[3]]
# Base condition met: add 0 to all previous heads
3 + 2 + 1 + rec_sum[[]]
# Resulting expression
3 + 2 + 1 + 0
Như bạn có thể thấy, biểu thức
rec_sum[[1, 2, 3]]
# Base condition not met: take head, call function on tail
1 + rec_sum[[2, 3]]
# Base condition not met: take head, call function on tail
2 + 1 + rec_sum[[3]]
# Base condition met: add 0 to all previous heads
3 + 2 + 1 + rec_sum[[]]
# Resulting expression
3 + 2 + 1 + 0
rec_sum[[1, 2, 3]]
# Base condition not met: take head, call function on tail
1 + rec_sum[[2, 3]]
# Base condition not met: take head, call function on tail
2 + 1 + rec_sum[[3]]
# Base condition met: add 0 to all previous heads
3 + 2 + 1 + rec_sum[[]]
# Resulting expression
3 + 2 + 1 + 0
Trong Python, chúng ta cần sử dụng câu lệnh if để xác định trường hợp cơ sở của mình. Haskell hỗ trợ khớp mẫu, nghĩa là chúng ta có thể xác định trường hợp cơ sở của mình theo một mẫu nhất định để khớp và trường hợp thay thế của chúng ta là một mẫu khác. Khớp mẫu hơi giống với nạp chồng hàm trong các ngôn ngữ dựa trên C như C, C++, C# và Java, nhưng mạnh hơn vì nó không chỉ khớp dựa trên loại mà còn thực hiện một số khớp cấu trúc.
def rec_sum[numbers]:
# Base case
if numbers == []:
return 0
# Split head and tail
x, *xs = numbers
# Recursive case
return x + rec_sum[xs]
result = rec_sum[[1, 2, 3]]
# Prints: 6
print[result]
Trong Haskell, chúng tôi bắt đầu với một định nghĩa kiểu để thiết lập chức năng của chúng tôi nên làm gì. đi từ một dãy số nguyên đến một số nguyên duy nhất
Chúng tôi xác định chức năng
def rec_sum[numbers]:
# Base case
if numbers == []:
return 0
# Split head and tail
x, *xs = numbers
# Recursive case
return x + rec_sum[xs]
result = rec_sum[[1, 2, 3]]
# Prints: 6
print[result]
def rec_sum[numbers]:
# Base case
if numbers == []:
return 0
# Split head and tail
x, *xs = numbers
# Recursive case
return x + rec_sum[xs]
result = rec_sum[[1, 2, 3]]
# Prints: 6
print[result]
def rec_sum[numbers]:
# Base case
if numbers == []:
return 0
# Split head and tail
x, *xs = numbers
# Recursive case
return x + rec_sum[xs]
result = rec_sum[[1, 2, 3]]
# Prints: 6
print[result]
Haskell trông gọn gàng hơn khi thực hiện đệ quy so với Python. Điều này không có gì ngạc nhiên với tính chất chức năng của Haskell
đệ quy đuôi
Người ta có thể tưởng tượng rằng đệ quy có thể tốn kém về bộ nhớ, vì trình thông dịch [hoặc trình biên dịch] sẽ cần thực hiện nhiều lệnh gọi hàm do đó mỗi lệnh hoạt động trên ngăn xếp lệnh gọi, tạo ra một chồng lệnh gọi cho chính nó. Đây là lý do tại sao một số ngôn ngữ lập trình có sẵn các kỹ thuật tối ưu hóa một số dạng đệ quy bằng cách làm cho nó trông giống đối tác tích lũy bắt buộc của nó hơn
Điều này thường chỉ có thể được thực hiện khi thực hiện đệ quy đuôi, nghĩa là lần gọi cuối cùng [cuộc gọi đuôi] là đệ quy. Trong trường hợp của chúng tôi, hoạt động cuối cùng không phải là lệnh gọi của chúng tôi tới
def rec_sum[numbers]:
# Base case
if numbers == []:
return 0
# Split head and tail
x, *xs = numbers
# Recursive case
return x + rec_sum[xs]
result = rec_sum[[1, 2, 3]]
# Prints: 6
print[result]
rec_sum[[1, 2, 3]]
# Base condition not met: take head, call function on tail
1 + rec_sum[[2, 3]]
# Base condition not met: take head, call function on tail
2 + 1 + rec_sum[[3]]
# Base condition met: add 0 to all previous heads
3 + 2 + 1 + rec_sum[[]]
# Resulting expression
3 + 2 + 1 + 0
Trong Python, nó sẽ trông như thế này
def rec_sum[numbers]:
# Base case
if numbers == []:
return 0
# Split head and tail
x, *xs = numbers
# Recursive case
return x + rec_sum[xs]
result = rec_sum[[1, 2, 3]]
# Prints: 6
print[result]
Tuy nhiên, xin lưu ý rằng Python không tối ưu hóa các cuộc gọi đuôi. Đây là một sự lựa chọn có chủ ý của Guido van Rossum, tác giả chính của Python, vì ông tin rằng đệ quy là không phổ biến và việc loại bỏ đệ quy đuôi [TRE] sẽ phải trả giá bằng khả năng sửa lỗi. Từ quan điểm thiết kế ngôn ngữ, điều này là dễ hiểu. mặc dù Python có một số cấu trúc chức năng và khai báo, nhưng triết lý chính của nó là bắt buộc về bản chất
Việc viết lại hàm của bạn để sử dụng vòng lặp có thực sự là một vấn đề lớn không? . . -]
– Hướng dẫn van Rossum, 2009
Mặc dù Haskell tối ưu hóa theo những cách khác nhau do tính thuần túy của ngôn ngữ, nhưng chúng ta có thể định nghĩa một hàm đệ quy đuôi rõ ràng theo cùng một nguyên tắc. đảm bảo lệnh gọi hàm là lệnh gọi cuối cùng xảy ra trong hàm. Nó trông như thế này
def acc_sum[numbers]:
acc = 0
for number in numbers:
acc = acc + number
return acc
result = acc_sum[[1, 2, 3]]
# Prints: 6
print[result]
Bạn có thể nhận thấy hai điều. Trước hết, chúng tôi rõ ràng chuyển vào bộ tích lũy giữa các cuộc gọi. Thứ hai, chữ ký kiểu của chức năng đã thay đổi. Điều này là do chúng tôi phải chuyển vào giá trị ban đầu của bộ tích lũy mỗi lần. Điều này có thể được giảm thiểu bằng cách giới thiệu một chức năng khác đề cập đến chức năng với đệ quy cuộc gọi đuôi rõ ràng
def acc_sum[numbers]:
acc = 0
for number in numbers:
acc = acc + number
return acc
result = acc_sum[[1, 2, 3]]
# Prints: 6
print[result]
Như chúng ta đã thấy, đệ quy là một khuôn mẫu chung để chia nhỏ vấn đề thành từng phần và giới thiệu một hàm có thể giải quyết từng phần bằng cách gọi chính nó.
Ngoài ra còn có một mẫu chức năng đặc biệt hướng tới các trường hợp giảm một chuỗi các giá trị thành một giá trị duy nhất. Trong một số ngôn ngữ, điều này được gọi là giảm hoặc rút gọn. Trong các ngôn ngữ khác, đây được gọi là nếp gấp
Hàm rút gọn là một hàm bậc cao hơn, nghĩa là nó nhận một hàm khác. Nó áp dụng hàm đã cho trên từng giá trị để tích lũy giá trị kết quả cuối cùng
Bởi vì Python chủ yếu là mệnh lệnh, hàm
rec_sum[[1, 2, 3]]
# Base condition not met: take head, call function on tail
1 + rec_sum[[2, 3]]
# Base condition not met: take head, call function on tail
2 + 1 + rec_sum[[3]]
# Base condition met: add 0 to all previous heads
3 + 2 + 1 + rec_sum[[]]
# Resulting expression
3 + 2 + 1 + 0
def acc_sum[numbers]:
acc = 0
for number in numbers:
acc = acc + number
return acc
result = acc_sum[[1, 2, 3]]
# Prints: 6
print[result]
Ngoài ra, một chức năng không tên có thể được sử dụng. Đây được gọi là hàm lambda, theo tên nhánh toán học mà lập trình hàm dựa trên. Điều này trông như sau trong Python
def acc_sum[numbers]:
acc = 0
for number in numbers:
acc = acc + number
return acc
result = acc_sum[[1, 2, 3]]
# Prints: 6
print[result]
Cuối cùng, bạn có thể tham khảo toán tử cộng trong Python thay vì định nghĩa phép toán theo cách thủ công. Sử dụng mô-đun toán tử, người ta có thể tham chiếu đến một toán tử như thể đó là một hàm. Điều này đọc khá rõ ràng. giảm tất cả các số bằng cách cộng chúng lại với nhau
def acc_sum[numbers]:
acc = 0
for number in numbers:
acc = acc + number
return acc
result = acc_sum[[1, 2, 3]]
# Prints: 6
print[result]
Việc gói
rec_sum[[1, 2, 3]]
# Base condition not met: take head, call function on tail
1 + rec_sum[[2, 3]]
# Base condition not met: take head, call function on tail
2 + 1 + rec_sum[[3]]
# Base condition met: add 0 to all previous heads
3 + 2 + 1 + rec_sum[[]]
# Resulting expression
3 + 2 + 1 + 0
def rec_sum[numbers]:
# Base case
if numbers == []:
return 0
# Split head and tail
x, *xs = numbers
# Recursive case
return x + rec_sum[xs]
result = rec_sum[[1, 2, 3]]
# Prints: 6
print[result]
rec_sum[[1, 2, 3]]
# Base condition not met: take head, call function on tail
1 + rec_sum[[2, 3]]
# Base condition not met: take head, call function on tail
2 + 1 + rec_sum[[3]]
# Base condition met: add 0 to all previous heads
3 + 2 + 1 + rec_sum[[]]
# Resulting expression
3 + 2 + 1 + 0
Trong Haskell, một nếp gấp được sử dụng để “xử lý cấu trúc dữ liệu theo thứ tự nào đó và tạo giá trị trả về. ” Nó nhận một hàm kết hợp, giá trị ban đầu và cấu trúc dữ liệu và kết hợp các giá trị trong cấu trúc dữ liệu đó khi được đánh giá
def rec_sum[numbers]:
# Base case
if numbers == []:
return 0
# Split head and tail
x, *xs = numbers
# Recursive case
return x + rec_sum[xs]
result = rec_sum[[1, 2, 3]]
# Prints: 6
print[result]
Các loại nếp gấp
Về cơ bản, có hai loại nếp gấp. nếp gấp bên trái và nếp gấp bên phải
Một nếp gấp bên trái kết hợp tất cả các phần tử cho đến phần tử cuối cùng với phần tử cuối cùng [kết hợp trái], trong khi một nếp gấp bên phải kết hợp phần đầu với kết quả của việc kết hợp phần đuôi [kết hợp bên phải]
def rec_sum[numbers]:
# Base case
if numbers == []:
return 0
# Split head and tail
x, *xs = numbers
# Recursive case
return x + rec_sum[xs]
result = rec_sum[[1, 2, 3]]
# Prints: 6
print[result]
Đối với các phép toán giao hoán, các phép toán mà thứ tự không quan trọng, việc bạn sử dụng đường gấp trái hay phải không quan trọng. Đối với các phép toán không giao hoán, như phép trừ hoặc phép chia, nó không
def rec_sum[numbers]:
# Base case
if numbers == []:
return 0
# Split head and tail
x, *xs = numbers
# Recursive case
return x + rec_sum[xs]
result = rec_sum[[1, 2, 3]]
# Prints: 6
print[result]
Bạn biết đấy, phần giảm của Python là một nếp gấp bên trái
def rec_sum[numbers]:
# Base case
if numbers == []:
return 0
# Split head and tail
x, *xs = numbers
# Recursive case
return x + rec_sum[xs]
result = rec_sum[[1, 2, 3]]
# Prints: 6
print[result]
Chúng ta đã thấy rằng Haskell có nếp gấp bên phải [] và nếp gấp bên trái []
Ngoài ra còn có [gấp trái prime]. Việc sử dụng
def rec_sum[numbers]:
# Base case
if numbers == []:
return 0
# Split head and tail
x, *xs = numbers
# Recursive case
return x + rec_sum[xs]
result = rec_sum[[1, 2, 3]]
# Prints: 6
print[result]
Lưu ý rằng các cấu trúc chức năng như reduce mang tính khai báo hơn so với các cấu trúc bắt buộc của chúng. Thay vì nêu rõ từng lệnh riêng lẻ, bạn thể hiện ý định của mình và trình biên dịch hoặc bộ thực thi sẽ tìm ra nó. giảm số danh sách thành một số duy nhất bằng cách thêm chúng lại với nhau. Bằng cách sử dụng một ngôn ngữ chung để giải quyết các vấn đề có hình dạng giống nhau, bạn có thể sử dụng các giải pháp tương tự về mặt trừu tượng – như các mẫu thiết kế. Những trừu tượng này có thể tổng hợp được trong tự nhiên và lý tưởng để tái sử dụng
Điều này dẫn đến ít mã hơn, nhưng yêu cầu phải làm quen với các khái niệm cấp cao hơn này để hiểu nó. Tải trọng nhận thức của việc bước qua các bước chi tiết trong các giải pháp cấp bách được đánh đổi dựa trên kiến thức trước đó về các khái niệm trừu tượng chung trong các phương pháp tiếp cận chức năng hơn. Nói cách khác. “sự phức tạp” chuyển từ những gì trên màn hình sang những khái niệm mà bạn biết
Tôi nghĩ thật tệ khi Python che giấu chức năng rút gọn để ủng hộ cách tiếp cận tích lũy bắt buộc hơn. Điều đó đang được nói, Python có. Hiểu là một cách lập trình khai báo cũng được tìm thấy trong các ngôn ngữ chức năng như Haskell. Chúng rất hữu ích để tạo một trình tự mới dựa trên một trình tự hiện có và áp dụng một phép biến đổi và/hoặc một bộ lọc hoặc lựa chọn cho nó. Tuy nhiên, việc hiểu không thể dễ dàng được sử dụng để tích lũy giá trị, do đó, một trong các mẫu trên vẫn cần thiết. Có lẽ chúng ta sẽ kiểm tra khả năng hiểu trong một bài đăng sau
Tóm lại làTích lũy một giá trị duy nhất dựa trên một chuỗi các giá trị có thể được thực hiện thông qua mẫu bộ tích lũy bắt buộc hoặc thông qua các mẫu chức năng như đệ quy hoặc nếp gấp
Các cấu trúc chức năng có thể được áp dụng để đạt được phong cách khai báo hơn. nêu ý định của bạn và trình biên dịch hoặc thời gian chạy sẽ tuân theo. Tuy nhiên, điều này đòi hỏi sự quen thuộc với các khái niệm cấp cao hơn này từ phía nhà phát triển
Như chúng ta đã thấy, mặc dù lập trình hàm có thể thực hiện được nhưng Python không thực sự là một ngôn ngữ hàm. Về bản chất, nó bắt buộc và tránh các khái niệm chức năng điển hình như đệ quy và nếp gấp vì nó "không phức tạp" và vì thiếu tối ưu hóa cuộc gọi đuôi