Tìm hiểu bản đồ Haskell, nếp gấp, vòng lặp và đệ quy

Question

Tôi chỉ vừa mới nhúng ngón chân vào thế giới của Haskell như một phần trong hành trình lập trình của tôi (chuyển từ, thủ tục sang OOP để đồng thời với chức năng hiện tại).

Tôi đã thử trực tuyến Haskell Evaluator.

Tuy nhiên tôi là bây giờ bị mắc kẹt trên một vấn đề:

Tạo một chức năng đơn giản mà mang lại cho tổng của một dãy số.

Trong một ngôn ngữ thủ tục này đối với tôi là đủ dễ dàng (sử dụng đệ quy) (C#):

private int sum(ArrayList x, int i) 
{ 
    if (!(x.Count < i + 1)) { 
     int t = 0; 

     t = x.Item(i); 
     t = sum(x, i + 1) + t; 
     return t; 
    } 
} 

Tất cả tuy nhiên thất bại của tôi rất tốt tại Haskell là như sau:

let sum x = x+sum in map sum [1..10] 

này dẫn đến lỗi sau (từ trang web được đề cập ở trên):

Occurs check: cannot construct the infinite type: a = a -> t 

Xin lưu ý rằng tôi chỉ sử dụng Haskell trong 30 phút qua!

Tôi không chỉ đơn giản là tìm câu trả lời mà còn giải thích thêm về nó.

Answer 1

Tôi không tìm kiếm chỉ đơn giản là một câu trả lời nhưng một giải thích thêm về nó.

Ở phía bên trái của = bạn sử dụng sum làm chức năng được áp dụng cho x. Trình biên dịch không biết loại x, do đó trình biên dịch sử dụng biến kiểu a để đứng cho "loại x". Do đó, trình biên dịch không biết loại kết quả của hàm sum hoặc là, do đó, nó chọn một biến kiểu khác, loại này là t, để đứng cho loại kết quả. Bây giờ ở phía bên trái trình biên dịch nghĩ rằng loại x là a -> t (chức năng chấp nhận a và trả lại t).

Ở bên phải của = bạn thêm x và sum. Trong Haskell, tất cả các loại số có thể được thêm vào, nhưng bạn chỉ có thể thêm hai số nếu chúng có loại cùng loại. Vì vậy, ở đây trình biên dịch giả định rằng sum có cùng loại với x, cụ thể là loại a.

Nhưng trong số nhận dạng Haskell có một loại — có thể là loại phức tạp nhưng có thể là một loại. Điều này bao gồm sum, có loại cần phải giống nhau trên cả hai mặt của 'dấu hiệu, do đó trình biên dịch sẽ cố gắng để giải quyết phương trình

a = a -> t 

Không có giá trị cho a và t rằng giải quyết phương trình này. Nó chỉ đơn giản là không thể được thực hiện. Không có a sao cho a bằng một hàm tự chấp nhận làm đối số. Do đó, hãy gửi thông báo lỗi

cannot construct the infinite type: a = a -> t 

Ngay cả với tất cả giải thích, đó không phải là một thông báo lỗi tuyệt vời, phải không?

Chào mừng bạn đến Haskell :-)

---

T.B. Bạn có thể thích thử "Helium, để học Haskell", cung cấp nhiều thông báo lỗi đẹp hơn cho người mới bắt đầu.

Answer 2

'tổng' lấy danh sách các giá trị và giảm giá trị đó thành một giá trị duy nhất. Bạn có thể viết nó như là một vòng lặp rõ ràng (hãy nhớ rằng Haskell không có từ khóa vòng lặp nào, nhưng sử dụng đệ quy). Lưu ý cách định nghĩa có hai phần, dựa trên hình dạng của danh sách:

mysum []  = 0 
mysum (x:xs) = x + mysum xs 

Hoặc một cách hiệu quả hơn, theo một phong cách tail-recursive:

mysum xs = go 0 xs 
    where 
     go n []  = n 
     go n (x:xs) = go (n+x) xs 

Tuy nhiên, Haskell có một thư viện phong phú của các cấu trúc điều khiển hoạt động trên danh sách lười biếng. Trong trường hợp này, việc giảm của danh sách thành một giá trị có thể được thực hiện với chức năng giảm: gấp.

Vì vậy mysum có thể được viết như sau:

mysum xs = foldr (+) 0 xs 

Ví dụ:

Prelude> foldr (+) 0 [1..10] 
55 

sai lầm của bạn là sử dụng một bản đồ , mà biến đổi một danh sách, một yếu tố tại một thời điểm, chứ không phải so với số gấp.

Tôi khuyên bạn nên bắt đầu bằng phần giới thiệu về Haskell, có lẽ là "Programming in Haskell", để có được cảm nhận về các khái niệm cốt lõi về lập trình hàm. Các tài liệu giới thiệu tốt khác được mô tả in this question.

Answer 3

Bạn cần đọc một hướng dẫn hay, có một số hiểu lầm lớn.

Trước tiên, tôi sẽ giả sử bạn có nghĩa là danh sách chứ không phải mảng. Mảng tồn tại trong Haskell, nhưng chúng không phải là thứ bạn gặp ở cấp độ mới bắt đầu. (Chưa kể bạn đang sử dụng [1..10] là danh sách các số từ 1 đến 10).

Các chức năng bạn muốn thực sự được xây dựng trong, và gọi Tóm lại, vì vậy chúng tôi sẽ phải gọi một cái gì đó của chúng tôi khác, new_sum:

new_sum [] = 0 
new_sum (h:t) = h + (sum t) 

Answer 4

Hãy nhìn vào phần đầu tiên của việc này:

let sum x = x+sum 

Điều gì sẽ loại tổng thể trong trường hợp này? Nó lấy một số và trả về một hàm nhận một số trả về một hàm lấy số vv nếu bạn đã viết nó để tổng x = + x bạn sẽ có một hàm lấy một số và trả về hàm + x . và cho phép sum = + sẽ trả về một hàm lấy hai số nguyên và thêm chúng.

vì vậy hãy xem phần thứ hai. trong tổng số bản đồ [1..10] bản đồ có chức năng của một đối số và áp dụng nó cho mọi phần tử trong danh sách.Không có chỗ để nêm một ắc quy trong đó, vì vậy chúng ta hãy nhìn vào các chức năng danh sách khác trong foldl cụ thể, foldr. cả hai hàm này lấy một hàm của hai đối số một danh sách và một giá trị bắt đầu. Sự khác biệt giữa foldl và foldr là ở phía bên mà chúng bắt đầu. l bị bỏ lại quá 1 + 2 + 3 vv và r là đúng 10 + 9 + 8 vv

let sum = (+) trong tổng foldl 0 [1..10]