Cải thiện việc triển khai Bộ lọc Haskell của tôi

Question

Gần đây tôi đã tự dạy mình Haskell và một trong các bài tập của tôi là triển khai lại chức năng filter. Tuy nhiên, trong tất cả các bài tập tôi đã thực hiện, câu trả lời của tôi cho câu hỏi này dường như đối với tôi là xấu nhất và lâu dài nhất. Làm thế nào tôi có thể cải thiện nó? Có bất kỳ thủ thuật Haskell tôi chưa biết?

myfilter :: (a -> Bool) -> [a] -> [a] 
myfilter f (x:xs) = if f x 
    then x : myfilter f xs 
    else myfilter f xs 
myfilter _ [] = [] 

cảm ơn

Answer 1

Cách đơn giản nhất để neaten thực hiện của bạn là sử dụng guards. Thay vì pattern = value, bạn có thể viết ghi pattern | boolean = value; điều này sẽ chỉ khớp khi boolean là đúng. Do đó, chúng tôi có thể nhận được

filter1 :: (a -> Bool) -> [a] -> [a] 
filter1 p (x:xs) | p x  = x : filter1 p xs 
       | otherwise = filter1 p xs 
filter1 _ []     = [] 

(Lưu ý rằng otherwise chỉ là một từ đồng nghĩa với True.) Bây giờ, chúng tôi có filter p xs ở hai nơi, vì vậy chúng ta có thể di chuyển nó ra thành một điều khoản where; những được chia sẻ bởi tất cả những gì mà chia sẻ một mô hình phổ biến, thậm chí nếu nó có một người bảo vệ khác nhau: (. thực hiện Đây là một used by GHCs Prelude)

filter2 :: (a -> Bool) -> [a] -> [a] 
filter2 p (x:xs) | p x  = x : xs' 
       | otherwise = xs' 
    where xs' = filter2 p xs 
filter2 _ []     = [] 

Bây giờ, không ai trong số đó là những đuôi-đệ quy. Điều này có thể bất lợi, nhưng nó làm cho chức năng trở nên lười biếng. Nếu chúng ta muốn có một phiên bản đuôi-đệ quy, chúng ta có thể viết

filter3 :: (a -> Bool) -> [a] -> [a] 
filter3 p xs = let filter3' p (x:xs) ys | p x  = next $! x:ys 
             | otherwise = next $! ys 
        where next = filter3' p xs 
        filter3' _ []  ys    = reverse ys 
       in filter3' p xs [] 

Lưu ý, tuy nhiên, điều này sẽ thất bại trên danh sách vô hạn (mặc dù tất cả các hiện thực khác sẽ làm việc), nhờ vào sự reverse, vì vậy chúng tôi làm cho nó nghiêm ngặt với $!. (Tôi nghĩ rằng tôi đã làm điều này đúng - tôi có thể đã buộc sai biến. Tôi nghĩ rằng tôi đã có một quyền này, mặc dù.)

Những triển khai tất cả trông giống như của bạn. Có, tất nhiên, những người khác. Một được dựa trên foldr:

filter4 :: (a -> Bool) -> [a] -> [a] 
filter4 p = let check x | p x  = (x :) 
         | otherwise = id 
      in foldr check [] 

Chúng tôi tận dụng ưu điểm không có điểm ở đây; kể từ xs sẽ là đối số cuối cùng cho cả hai số filter4 và foldr check [], chúng tôi có thể tách nó và tương tự với đối số cuối cùng của check.

Bạn cũng có thể tận dụng lợi thế của danh sách đơn nguyên:

import Control.Monad 
filter5 :: MonadPlus m => (a -> Bool) -> m a -> m a 
filter5 p xs = do x <- xs 
        guard $ p x 
        return x 

Danh sách này đơn nguyên đại diện cho nondeterminism.Bạn chọn một phần tử x từ xs, đảm bảo rằng nó đáp ứng p và sau đó trả lại nếu có. Tất cả các kết quả này sau đó được thu thập lại với nhau. Nhưng lưu ý rằng điều này bây giờ là tổng quát hơn; điều này làm việc cho bất kỳ MonadPlus (một đơn vị nào cũng là một monoid, có hoạt động nhị phân kết hợp mplus - ++ cho danh sách — và một phần tử nhận dạng mzero - [] cho danh sách), chẳng hạn như [] hoặc Maybe. Ví dụ: filter5 even $ Just 1 == Nothing và filter5 even $ Just 2 == Just 2.

Chúng tôi cũng có thể thích ứng với phiên bản dựa trên foldr để có được một kiểu generic chữ ký khác nhau:

import Control.Monad 
import qualified Data.Foldable as F 
import qualified Data.Monoid as M 
filter6 :: (F.Foldable f, MonadPlus m, M.Monoid (m a)) 
     => (a -> Bool) -> f a -> m a 
filter6 p = let check x | p x  = return x 
         | otherwise = mzero 
      in F.foldMap check 

Các Data.Foldable module cung cấp các lớp Foldable loại, đại diện cho bất kỳ cấu trúc có thể được fold ed như một danh sách (đặt do đó, filter của chúng tôi cũng yêu cầu một ràng buộc MonadPlus về kết quả để chúng tôi có thể viết return x. Hàm foldMap yêu cầu một hàm chuyển đổi mọi thứ thành các phần tử của Monoid và sau đó ghép tất cả chúng lại với nhau. Sự không khớp giữa số f a ở bên trái và m a ở bên phải có nghĩa là bạn có thể, ví dụ: filter6 a Maybe và lấy lại danh sách.

Tôi chắc chắn rằng có (nhiều!) Triển khai khác của filter, nhưng đây là 6 mà tôi có thể nghĩ tương đối nhanh. Bây giờ, cái nào tôi thực sự thích nhất? Đó là một sự quăng giữa đơn giản filter2 và foldr dựa trên filter4. Và filter5 là tốt đẹp cho chữ ký loại chung của nó. (Tôi không nghĩ rằng mình đã từng cần một chữ ký kiểu như filter6.) Thực tế là filter2 được sử dụng bởi GHC là một điểm cộng, nhưng GHC cũng sử dụng một số quy tắc viết lại vui nhộn, vì vậy nó không rõ ràng với tôi không có. Cá nhân, tôi sẽ có thể là đi với filter4 (hoặc filter5 nếu tôi cần tính tổng thể), nhưng filter2 chắc chắn là tốt.

Answer 2

Bạn ít nhất có thể KHÔ nó lên một chút bằng cách kéo ra rằng chung myfilter f xs mã:

myfilter :: (a -> Bool) -> [a] -> [a] 
myfilter f (x:xs) = if f x 
    then x : rest 
    else rest 
     where rest = myfilter f xs 
myfilter _ [] = [] 

Answer 3

Trong Haskell, hầu hết thời gian bạn có thể (và nên) sử dụng guards thay vì if-then-else:

myfilter :: (a -> Bool) -> [a] -> [a] 
myfilter f (x:xs) 
    | f x  = x : myfilter f xs 
    | otherwise = myfilter f xs 
myfilter _ [] = [] 

Điều này kết thúc về cơ bản là định nghĩa ame như được sử dụng in the standard library.

Answer 4

Để so sánh, đây là thực hiện của Wikipedia:

myfilter :: (a -> Bool) -> [a] -> [a] 
myfilter _ []     = [] 
myfilter f (x:xs) | f x  = x : myfilter f xs 
        | otherwise = myfilter f xs 

Answer 5

Làm thế nào để hiểu danh sách?

myfilter f xs = [x | x <- xs, f x]