Đoạn trích này sẽ dịch sang Haskell như thế nào?

Question

Tôi đang đấu tranh với Haskell, và ý tưởng sử dụng đệ quy để lặp qua mọi thứ.

Ví dụ, làm thế nào

// this might seem silly but I need to do it 
list1 = empty list 
list2 = list of numbers 
for i from 0 to N // N being a positive integer 
    for each number in list2 
     if number == i, add to list1 

sẽ chuyển thành các 'mô hình chức năng'? Mọi hướng dẫn sẽ được đánh giá cao.

Answer 1

Đi từng bước:

list2 = list of numbers 

Chúng tôi sẽ thực hiện việc này là điều đương nhiên, vì vậy list2 vẫn chỉ là một danh sách các số.

for i from 0 to N // N being a positive integer 

Các cách chính xác để làm điều này trong Haskell nói chung là với một danh sách. Laziness có nghĩa là các giá trị sẽ được tính toán chỉ khi được sử dụng, vì vậy việc duyệt qua một danh sách từ 0 đến N kết thúc bằng cùng một thứ với vòng lặp bạn có ở đây. Vì vậy, chỉ cần [0..n] sẽ thực hiện thủ thuật; chúng ta chỉ cần tìm ra những gì cần làm với nó.

for each number in list2 

Với "cho mỗi" chúng ta có thể suy ra rằng chúng tôi sẽ cần phải đi qua toàn bộ list2 đây; những gì chúng tôi làm với nó, chúng tôi chưa biết.

if number == i, add to list1 

Chúng tôi đang xây dựng list1 khi chúng ta đi, vì vậy lý tưởng nhất chúng tôi muốn điều đó là kết quả cuối cùng của biểu thức. Điều đó cũng có nghĩa là ở mỗi bước đệ quy, chúng tôi muốn kết quả là list1 chúng tôi có "cho đến nay". Để làm điều đó, chúng tôi sẽ cần phải đảm bảo rằng chúng tôi vượt qua kết quả của mỗi bước khi chúng tôi đi.

Vì vậy, nhận được xuống để thịt của nó:

Chức năng filter tìm tất cả các yếu tố trong một danh sách phù hợp với một số vị; chúng tôi sẽ sử dụng filter (== i) list2 tại đây để tìm những gì chúng tôi đang theo dõi, sau đó nối thêm vào kết quả của bước trước đó. Vì vậy, mỗi bước sẽ trông giống như sau:

step :: (Num a) => [a] -> a -> [a] 
step list1 i = list1 ++ filter (== i) list2 

Điều đó xử lý vòng lặp bên trong. Bước lùi ra phía sau, chúng ta cần phải chạy điều này cho mỗi giá trị i từ danh sách [0..n], với giá trị list1 được truyền đi ở mỗi bước.Đây chính là điều gấp chức năng là cho, và trong trường hợp này step là chính xác những gì chúng ta cần cho một lần trái:

list2 :: (Num a) => [a] 
list2 = -- whatever goes here... 

step :: (Num a) => [a] -> a -> [a] 
step list1 i = list1 ++ filter (== i) list2 

list1 :: (Num a) => a -> [a] 
list1 n = foldl step [] [0..n] 

Nếu bạn đang tự hỏi nơi đệ quy là, cả hai filter và foldl đang làm điều đó cho chúng ta . Theo quy tắc chung, tốt hơn là tránh đệ quy trực tiếp khi có các hàm cấp cao hơn để thực hiện điều đó cho bạn.

---

Điều đó nói rằng, thuật toán ở đây là ngớ ngẩn theo nhiều cách, nhưng tôi không muốn tham gia bởi vì nó có vẻ như nó sẽ phân tâm khỏi câu hỏi thực tế của bạn nhiều hơn nó sẽ giúp ích.

Answer 2

Xin lỗi, nhưng tôi không thể giúp đỡ, nhưng sử dụng một thuật toán tốt hơn ...

let goodNumber n = (0 <= n && n < N) 
let list1 = sort (filter goodNumber list2) 

---

Chỉnh sửa: Trong nhận thức muộn màng này là một chút quá mức cần thiết, kể từ khi OP đã cố gắng để thực hiện một phân loại bản ngã ngay từ đầu.

Answer 3

let list1 = sort [a | a<-list2, a>=0, a<=N] 

a<-list2 cuốc lên mỗi số List2 a>=0, a<=N kiểm tra nếu số chọn đáp ứng tất cả những điều kiện này nếu điều kiện được đáp ứng, một là đưa vào một danh sách mới Khi tất cả các yếu tố của List2 đã được như vậy, kiểm tra và đưa vào danh sách mới, chúng tôi sắp xếp theo số này Danh sách kết quả được chỉ định cho list1