là có một cách lười biếng để viết các chức năng trừ (loại bỏ các mục từ một danh sách)?

Question

chức năng của tôi trông như thế này:

minus :: (Eq a) => [a] -> [a] -> [a] 
minus [] xs      = [] 
minus (y:ys) xs | y `notElem` xs = y : (minus ys xs) 
       | otherwise  = minus ys xs 

Nó có thể được sử dụng như thế này:

[99,44,55,22,23423] `minus` [55,22] 

với sản lượng: [99,44,23423]

tôi đã viết này bởi vì tôi đang nhìn vào Dự án Euler vấn đề 7 và Sàng Eratosthenes có vẻ như là công cụ thích hợp, và nó đã được, nhưng tôi tiếp tục đọc xuống Wikipedia page và nhận được một phần về sàng của Euler.

Tôi đã cố gắng sao chép/dán mã và chạy nó trong GHCi, nhưng phiên bản GHCi của tôi không có mô-đun gọi là Data.OrdList và tôi không thể tìm thấy hàm có tên minus trong Hoogle.

Đây là mã từ Wikipedia:

import Data.OrdList (minus) 

primes = euler [2..] 
euler (p : xs) = p : euler (xs `minus` map (*p) (p : xs)) 

Nếu tôi thay thế chức năng trừ của tôi ở đó, tôi nhận được một số lỗi bộ nhớ, bởi vì chức năng của tôi là không lười biếng.

Có cách nào để thực hiện chức năng trừ đi không?

Chức năng trừ của tôi có giống với chức năng trừ trong bài viết trên Wikipedia không?

Answer 1

Vì sepp2k đã chỉ ra, việc triển khai minus phải giả định danh sách được sắp xếp. Ở đây có thể triển khai:

minus :: Ord a => [a] -> [a] -> [a] 
minus [] _ = [] 
minus xs [] = xs 
minus l1@(x:xs) l2@(y:ys) 
    | x > y = minus l1 ys 
    | x < y = x : minus xs l2 
    | otherwise = minus xs l2 

Answer 2

Có cách nào để thực hiện chức năng trừ đi không?

Nếu bạn không cho rằng danh sách đầu vào được sắp xếp (và bạn không được phép sắp xếp chúng) thì không có. Bạn sẽ cần phải biết liệu phần tử đầu tiên của list1 có trong list2 hay không trước khi bạn biết phần tử đầu tiên của kết quả sẽ là gì. Vì vậy, bạn không thể có được xung quanh có để đánh giá toàn bộ danh sách thứ hai trước khi sản xuất một yếu tố duy nhất trong trường hợp xấu nhất. Tuy nhiên nếu bạn giả định rằng danh sách đầu vào được đặt hàng (trừ đi được sử dụng bởi wikipedia rõ ràng là module được gọi là * Ord * List), nó rất dễ dàng để viết một hàm trừ đủ lười.

Và vì danh sách đầu vào của bạn được đặt hàng thực tế, nên chức năng trừ sẽ hoạt động hoàn hảo cho nhu cầu của bạn.

Answer 3

Google hoạt động tốt hơn Hoogle.

Taken từ http://hackage.haskell.org/packages/archive/data-ordlist/0.0.1/doc/html/src/Data-OrdList.html

minus :: (Ord a) => [a] -> [a] -> [a] 
minus = minusBy compare 

minusBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a] 
minusBy cmp = loop 
    where 
    loop [] _ys = [] 
    loop xs [] = xs 
    loop (x:xs) (y:ys) 
     = case cmp x y of 
      LT -> x : loop xs (y:ys) 
      EQ ->  loop xs ys 
      GT ->  loop (x:xs) ys