Tìm hiểu Haskell: Cách xóa một mục khỏi Danh sách trong Haskell

Question

Đang cố gắng tìm hiểu Haskell. Tôi đang cố gắng để viết một chức năng đơn giản để loại bỏ một số từ một danh sách mà không cần sử dụng chức năng được xây dựng trong (xóa ... tôi nghĩ). Để đơn giản, hãy giả sử tham số đầu vào là một số nguyên và danh sách là một danh sách Integer. Đây là mã tôi có, hãy cho tôi biết những gì xảy ra với đoạn mã sau

areTheySame :: Int -> Int-> [Int] 

areTheySame x y | x == y = [] 
       | otherwise = [y] 

removeItem :: Int -> [Int] -> [Int] 

removeItem x (y:ys) = areTheySame x y : removeItem x ys 

Answer 1

Các vấn đề khác là vấn đề là nhà điều hành :. Tuy nhiên, tôi cho rằng hàm areTheySame trả về danh sách của bạn là phương pháp sai. Thay vì chuyển sang các nhà điều hành ++, một thực hiện tốt hơn chức năng đó sẽ là:

removeItem _ []     = [] 
removeItem x (y:ys) | x == y = removeItem x ys 
        | otherwise = y : removeItem x ys 

Như bạn có thể thấy, đây là một thực hiện khá đơn giản. Ngoài ra, consing như thế này là ít hơn nhiều thuế cho chương trình của bạn hơn là nối một loạt các danh sách với nhau. Nó cũng có những lợi ích khác, chẳng hạn như làm việc lười biếng.

Answer 2

Nhà điều hành : không làm những gì bạn nghĩ nó:

(:) :: a -> [a] -> [a] 

Phải mất một mục kiểu a và thêm nó vào đầu danh sách loại a. Bạn đang sử dụng nó để tham gia hai danh sách loại a. Để làm được điều đó, bạn cần sử dụng ++:

(++) :: [a] -> [a] -> [a] 

Ngoài ra, nếu bạn thực hiện chức năng đệ quy, nó cần điều kiện kết thúc. Vì vậy, hãy thử điều này:

removeItem _ [] = [] 
removeItem x (y:ys) = areTheySame x y ++ removeItem x ys 

Bằng cách đó, khi bạn đến cuối danh sách, chức năng sẽ ngừng đệ quy.

Answer 3

Đây là sửa chữa tối thiểu để làm ví dụ công việc của bạn:

removeItem :: Int -> [Int] -> [Int] 
removeItem _ []  = [] 
removeItem x (y:ys) = areTheySame x y ++ removeItem x ys 

Trước tiên, bạn cần phải sử dụng ++ để nối danh sách, như các nhà điều hành : sử dụng bởi bạn cho biết thêm chỉ là một yếu tố để khởi đầu của một danh sách (nó không thể được sử dụng để thêm danh sách với một phần tử cũng như không thêm danh sách trống). Trước tiên, bạn so sánh đầu danh sách (y) với mục bạn muốn xóa và trả lại chính xác mục hoặc danh sách trống bằng cách sử dụng areTheySame. Sau đó, bạn muốn đệ quy tiếp tục sử dụng removeItem trên phần còn lại của danh sách (ys). Danh sách kết quả cần được ghép nối bằng cách sử dụng ++.

Thứ hai, như Chris Lutz đã lưu ý, bạn cần điều kiện kết thúc khi bạn đến cuối danh sách. Bằng cách thêm dòng này, Haskell biết phải làm gì với một danh sách trống (có nghĩa là, không có gì, chỉ cần trả về một danh sách trống). Như Chuck đã nói, bạn có thể đơn giản hóa mã cho nhiệm vụ này bằng cách removeItem không ủy nhiệm nhiệm vụ so sánh, nhưng so sánh chính nó và vứt bỏ phần tử nếu nó bị xóa, nếu không hãy giữ nó ở đầu danh sách (sử dụng :). Trong mọi trường hợp, tiếp tục đệ quy với phần còn lại của danh sách.

-- nothing can be removed from an empty list 
-- ==> return empty list and stop recursion 
removeItem _ []  = [] 

-- if the list is not empty, cut off the head in y and keep the rest in ys 
--     if x==y, remove y and continue 
removeItem x (y:ys) | x == y = removeItem x ys  
--     otherwise, add y back and continue 
        | otherwise = y : removeItem x ys 

Answer 4

Để tham khảo, bạn có thể quan tâm đến việc xem how it's done in delete from Data.List.

Bạn có thể rời khỏi areTheySame như là, nhưng sau đó bạn sẽ cần phải sử dụng concatMap trong removeItem sụp đổ danh sách rỗng:

removeItem :: Int -> [Int] -> [Int] 
removeItem x xs = concatMap (areTheySame x) xs 

hoặc tương đương

removeItem :: Int -> [Int] -> [Int] 
removeItem x = concatMap (areTheySame x) 

Lưu ý rằng các loại của bạn chức năng có thể tổng quát hơn:

areTheySame :: (Eq a) => a -> a -> [a] 
removeItem :: (Eq a) => a -> [a] -> [a] 

Điều này cho phép xóa các mục khỏi danh sách thuộc bất kỳ loại nào mà == được xác định, không chỉ là Int.

Answer 5

Bạn cũng có thể làm điều này như một danh sách-hiểu

delete :: Eq a => a -> [a] -> [a] 
delete deleted xs = [ x | x <- xs, x /= deleted ] 

Answer 6

Tôi tin rằng tất cả các giải pháp cho công việc cho đến nay khác so với Data.List.delete, mà chỉ xóa các thành viên đầu tiên.

deleteFromList x xs = 
    case break (==x) xs of 
    (_,[]) -> xs 
    (notsat,sat) -> notsat ++ tail sat 

là nỗ lực của tôi để chỉ xóa thành viên đầu tiên (chưa đạt điểm DL).

Không rõ hành vi mà người đăng hàng đầu muốn.

Answer 7

Tôi đã viết một chức năng chỉ trong một dòng mã:

remove element list = filter (\e -> e/=element) list 

Ví dụ:

remove 5 [1..10] 

[1,2,3,4,6,7,8,9,10 ]

remove 'b' ['a'..'f'] 

"acdef"