Cách triển khai xóa với foldr trong Haskell

Question

Tôi đã nghiên cứu các nếp gấp trong vài ngày qua. Tôi có thể triển khai các chức năng đơn giản với chúng, như length, concat và filter. Những gì tôi đang mắc kẹt đang cố triển khai với các chức năng foldr như delete, take và find. Tôi đã thực hiện với các đệ quy rõ ràng nhưng nó không có vẻ rõ ràng với tôi làm thế nào để chuyển đổi các loại chức năng để nếp gấp bên phải.

Tôi đã nghiên cứu các hướng dẫn của Graham Hutton và Bernie Pope. Bắt chước của Hutton dropWhile, tôi đã có thể triển khai delete với foldr nhưng không thành công trên danh sách vô hạn.

Từ đọc Implement insert in haskell with foldr, How can this function be written using foldr? và Implementing take using foldr, có vẻ như tôi cần sử dụng foldr để tạo chức năng sau đó thực hiện điều gì đó. Nhưng tôi không thực sự hiểu những giải pháp này và không có ý tưởng làm thế nào để thực hiện ví dụ delete theo cách này.

Bạn có thể giải thích cho tôi một chiến lược chung để triển khai với foldr các phiên bản chức năng lười biếng như các chức năng tôi đã đề cập hay không. Có lẽ bạn cũng có thể thực hiện delete làm ví dụ vì đây có thể là một trong những cách dễ nhất.

Tôi đang tìm kiếm giải thích chi tiết mà người mới bắt đầu có thể hiểu. Tôi không chỉ quan tâm đến các giải pháp, tôi muốn phát triển một sự hiểu biết để tôi có thể đưa ra các giải pháp cho các vấn đề tương tự.

Cảm ơn.

Chỉnh sửa: Tại thời điểm viết, có một câu trả lời hữu ích nhưng không hoàn toàn là những gì tôi đang tìm kiếm. Tôi quan tâm nhiều hơn đến cách tiếp cận sử dụng foldr để tạo ra một hàm, sau đó thực hiện một cái gì đó. Các liên kết trong câu hỏi của tôi có các ví dụ về điều này. Tôi không hiểu những giải pháp đó vì vậy tôi muốn có thêm thông tin về cách tiếp cận này.

Answer 1

delete là tìm kiếm phương thức. Nó có hai chế độ hoạt động khác nhau - cho dù nó đã được tìm thấy kết quả hay chưa. Bạn có thể sử dụng foldr để tạo một hàm chuyển trạng thái xuống dưới dòng khi mỗi phần tử được chọn. Vì vậy, trong trường hợp của delete, trạng thái có thể là đơn giản Bool. Nó không phải là loại tốt nhất, nhưng nó sẽ làm.

Sau khi bạn đã xác định loại trạng thái, bạn có thể bắt đầu làm việc với việc xây dựng foldr. Tôi sẽ đi qua tìm ra nó theo cách tôi đã làm. Tôi sẽ cho phép ScopedTypeVariables chỉ để tôi có thể chú thích loại biểu thức phụ tốt hơn. Một bạn biết loại trạng thái, bạn biết bạn muốn foldr để tạo một hàm lấy giá trị của loại đó và trả về giá trị của loại cuối cùng mong muốn. Đó là đủ để bắt đầu phác thảo mọi thứ.

{-# LANGUAGE ScopedTypeVariables #-} 

delete :: forall a. Eq a => a -> [a] -> [a] 
delete a xs = foldr f undefined xs undefined 
    where 
    f :: a -> (Bool -> [a]) -> (Bool -> [a]) 
    f x g = undefined 

Bắt đầu. Ý nghĩa chính xác của g là một chút khó khăn ở đây. Nó thực sự là chức năng để xử lý phần còn lại của danh sách. Đó là chính xác để xem nó như là một sự tiếp nối, trên thực tế. Nó hoàn toàn đại diện cho phần còn lại của gấp, với bất kỳ trạng thái nào bạn chọn để vượt qua. Cho rằng, đó là thời gian để tìm ra những gì để đưa vào một số trong những nơi undefined.

{-# LANGUAGE ScopedTypeVariables #-} 

delete :: forall a. Eq a => a -> [a] -> [a] 
delete a xs = foldr f undefined xs undefined 
    where 
    f :: a -> (Bool -> [a]) -> (Bool -> [a]) 
    f x g found | x == a && not found = g True 
       | otherwise   = x : g found 

Điều đó có vẻ tương đối đơn giản. Nếu phần tử hiện tại là phần tử đang được tìm kiếm, và nó vẫn chưa được tìm thấy, không xuất nó, và tiếp tục với trạng thái được đặt là True, cho biết nó đã được tìm thấy. otherwise, xuất giá trị hiện tại và tiếp tục với trạng thái hiện tại.Điều này chỉ để lại phần còn lại của các đối số cho foldr. Cái cuối cùng là trạng thái ban đầu. Một trong những khác là chức năng nhà nước cho một danh sách trống. Ok, những thứ đó cũng không quá tệ.

{-# LANGUAGE ScopedTypeVariables #-} 

delete :: forall a. Eq a => a -> [a] -> [a] 
delete a xs = foldr f (const []) xs False 
    where 
    f :: a -> (Bool -> [a]) -> (Bool -> [a]) 
    f x g found | x == a && not found = g True 
       | otherwise   = x : g found 

Bất kể trạng thái là gì, tạo danh sách trống khi danh sách trống gặp phải. Và trạng thái ban đầu là phần tử được tìm kiếm vẫn chưa được tìm thấy.

Kỹ thuật này cũng được áp dụng trong các trường hợp khác. Ví dụ: foldl có thể được viết dưới dạng foldr theo cách này. Nếu bạn nhìn vào foldl như một hàm liên tục biến đổi một bộ tích lũy ban đầu, bạn có thể đoán đó là hàm đang được tạo ra - cách chuyển đổi giá trị ban đầu.

{-# LANGUAGE ScopedTypeVariables #-} 

foldl :: forall a b. (a -> b -> a) -> a -> [b] -> a 
foldl f z xs = foldr g id xs z 
    where 
    g :: b -> (a -> a) -> (a -> a) 
    g x cont acc = undefined 

Các trường hợp cơ sở không quá khó khăn để tìm thấy khi các vấn đề được định nghĩa là thao tác accumulator ban đầu, tên z đó. Danh sách trống là chuyển đổi nhận dạng, id và giá trị được chuyển đến hàm được tạo là z.

Việc triển khai g là phức tạp hơn. Nó không thể được thực hiện một cách mù quáng trên các loại, bởi vì có hai triển khai khác nhau sử dụng tất cả các giá trị mong đợi và kiểm tra kiểu. Đây là trường hợp các loại không đủ, và bạn cần phải xem xét ý nghĩa của các hàm sẵn có.

Hãy bắt đầu với khoảng không quảng cáo của các giá trị có vẻ như chúng nên được sử dụng và loại của chúng. Những thứ có vẻ như chúng phải được sử dụng trong phần thân của g là f :: a -> b -> a, x :: b, cont :: (a -> a) và acc :: a. f rõ ràng sẽ lấy x làm đối số thứ hai của nó, nhưng có một câu hỏi về địa điểm thích hợp để sử dụng cont. Để tìm ra nơi nó đi, hãy nhớ rằng nó đại diện cho hàm chuyển đổi được trả về bằng cách xử lý phần còn lại của danh sách và rằng foldl xử lý phần tử hiện tại và sau đó chuyển kết quả của quá trình đó đến phần còn lại của danh sách.

{-# LANGUAGE ScopedTypeVariables #-} 

foldl :: forall a b. (a -> b -> a) -> a -> [b] -> a 
foldl f z xs = foldr g id xs z 
    where 
    g :: b -> (a -> a) -> (a -> a) 
    g x cont acc = cont $ f acc x 

này cũng cho thấy rằng foldl' có thể được viết theo cách này chỉ với một thay đổi nhỏ:

{-# LANGUAGE ScopedTypeVariables #-} 

foldl' :: forall a b. (a -> b -> a) -> a -> [b] -> a 
foldl' f z xs = foldr g id xs z 
    where 
    g :: b -> (a -> a) -> (a -> a) 
    g x cont acc = cont $! f acc x 

Sự khác biệt là ($!) được sử dụng để đề nghị thẩm định của f acc x trước khi nó được truyền cho cont. (Tôi nói "gợi ý" vì có một số trường hợp cạnh nơi ($!) không buộc đánh giá thậm chí xa như WHNF.)

Answer 2

delete không hoạt động trên toàn bộ danh sách đồng đều. Cấu trúc của tính toán không chỉ xem xét toàn bộ danh sách một phần tử tại một thời điểm. Nó khác sau khi nó chạm vào yếu tố mà nó đang tìm kiếm. Điều này cho bạn biết rằng bạn không thể triển khai chỉ số này chỉ a foldr. Sẽ phải có một số loại hậu xử lý liên quan.

Khi điều đó xảy ra, mẫu chung là bạn xây dựng một cặp giá trị và chỉ cần lấy một trong hai giá trị khi hoàn thành foldr. Đó có lẽ là những gì bạn đã làm khi bạn bắt chước Hutton's dropWhile, mặc dù tôi không chắc chắn vì bạn không bao gồm mã. Một cái gì đó như thế này?

delete :: Eq a => a -> [a] -> [a] 
delete a = snd . foldr (\x (xs1, xs2) -> if x == a then (x:xs1, xs1) else (x:xs1, x:xs2)) ([], []) 

Ý tưởng chính là xs1 luôn sẽ là đuôi đầy đủ danh sách, và xs2 là kết quả của delete trên đuôi của danh sách. Vì bạn chỉ muốn xóa phần tử đầu tiên khớp, bạn không muốn sử dụng kết quả của delete trên đuôi khi bạn so khớp giá trị bạn đang tìm kiếm, bạn chỉ muốn trả lại phần còn lại của danh sách - mà may mắn thay là những gì sẽ luôn ở trong xs1.

Và vâng, điều đó không hoạt động trên danh sách vô hạn - nhưng chỉ vì một lý do rất cụ thể. Lambda là quá nghiêm ngặt.foldr chỉ hoạt động trên các danh sách vô hạn khi hàm được cung cấp không phải lúc nào cũng đánh giá đối số thứ hai của nó và lambda luôn đánh giá đối số thứ hai của nó trong khớp mẫu trên cặp. Chuyển sang một bản sửa lỗi mẫu không thể chối cãi, bằng cách cho phép lambda tạo ra một hàm tạo trước khi kiểm tra đối số thứ hai của nó.

delete :: Eq a => a -> [a] -> [a] 
delete a = snd . foldr (\x ~(xs1, xs2) -> if x == a then (x:xs1, xs1) else (x:xs1, x:xs2)) ([], []) 

Đó không phải là cách duy nhất để có được kết quả đó. Sử dụng lệnh ràng buộc hoặc fst và snd làm người truy cập trên bộ túp cũng sẽ thực hiện công việc. Nhưng đó là sự thay đổi với sự khác biệt nhỏ nhất.

Điều quan trọng nhất ở đây là phải rất cẩn thận khi xử lý đối số thứ hai cho hàm giảm mà bạn chuyển đến foldr. Bạn muốn trì hoãn việc kiểm tra đối số thứ hai bất cứ khi nào có thể, để foldr có thể phát trực tiếp một cách uể oải trong nhiều trường hợp nhất có thể.

Nếu bạn nhìn vào lambda đó, bạn thấy rằng nhánh được chọn được chọn trước khi thực hiện bất kỳ điều gì với đối số thứ hai cho hàm reduce. Hơn nữa, bạn sẽ thấy rằng hầu hết thời gian, hàm reduce tạo ra một hàm tạo danh sách trong cả hai nửa của bộ kết quả trước khi nó cần để đánh giá đối số thứ hai. Vì những người xây dựng danh sách này là những gì làm cho nó ra khỏi delete, họ là những gì quan trọng cho streaming - miễn là bạn không để cho các cặp có được trong cách. Và làm cho mô hình phù hợp trên đôi không thể chối cãi là những gì giữ nó ra khỏi con đường.

Như một ví dụ tiền thưởng của các thuộc tính trực tuyến của foldr, hãy xem xét ví dụ yêu thích của tôi:

dropWhileEnd :: (a -> Bool) -> [a] -> [a] 
dropWhileEnd p = foldr (\x xs -> if p x && null xs then [] else x:xs) [] 

Nó suối - nhiều như nó có thể. Nếu bạn tìm ra chính xác thời điểm và lý do tại sao nó hoạt động và không phát trực tuyến, bạn sẽ hiểu khá nhiều chi tiết về cấu trúc phát trực tiếp của foldr.

Answer 3

đây là một đơn giản xóa, thực hiện với foldr:

delete :: (Eq a) => a -> [a] -> [a] 
delete a xs = foldr (\x xs -> if x == a then (xs) else (x:xs)) [] xs