如何僅從Haskell的列表中獲取特定類型的元素？

Question

我正在學習Haskell Book，並在第10章（摺疊列表）中，我試圖解決有關從包含不同類型的元素的列表中僅獲取一種特定類型的元素的練習。

作者給出了下面的代碼：

import Data.Time 

data DatabaseItem = DbString String 
        | DbNumber Integer 
        | DbDate UTCTime 
        deriving (Eq, Ord, Show) 

theDatabase :: [DatabaseItem] 
theDatabase = [ DbDate (UTCTime 
         (fromGregorian 1911 5 1) 
         (secondsToDiffTime 34123)) 
       , DbNumber 9001 
       , DbString "Hello, world!" 
       , DbDate (UTCTime 
         (fromGregorian 1921 5 1) 
         (secondsToDiffTime 34123)) 
       ] 

和第一個問題是：

編寫過濾器DBDATE值和返回的 列表裏面他們UTCTime值的功能。

filterDbDate :: [DatabaseItem] -> [UTCTime] 
filterDbDate = undefined 

因爲章是關於摺疊名單，我認爲它可以使用，例如，foldr來完成。

我最初的嘗試是先寫一些輔助功能，並在foldr使用它們，如：

getDbDate1 :: DatabaseItem -> UTCTime 
getDbDate1 (DbDate utcTime) = utcTime 

isDbDate :: DatabaseItem -> Bool 
isDbDate (DbDate _) = True 
isDbDate _ = False 

filterDbDate1 :: [DatabaseItem] -> [UTCTime] 
filterDbDate1 database = foldr ((:) . getDbDate1) [] (filter isDbDate database) 

這似乎做的工作，這是因爲：

λ> filterDbDate1 theDatabase 
[1911-05-01 09:28:43 UTC,1921-05-01 09:28:43 UTC] 

但我對此解決方案並不舒服，因爲首先它給出以下警告：

/Users/emre/code/haskell/chapter10_folding_lists/database.hs:36:1: Warning: … 
    Pattern match(es) are non-exhaustive 
    In an equation for ‘getDbDate1’: 
     Patterns not matched: 
      DbString _ 
      DbNumber _ 

而且我使用了兩個輔助函數，一個幫助濾除不是DbDate的值，另一個幫助處理UTCTime組件。

因此，擺脫非詳盡的模式匹配的警告，並使用一個輔助函數，我決定把它寫這樣的：

getDbDate2 :: DatabaseItem -> Maybe UTCTime 
getDbDate2 (DbDate utcTime) = Just utcTime 
getDbDate2 _ = Nothing 

filterDbDate2 :: [DatabaseItem] -> [UTCTime] 
filterDbDate2 database = foldr ((:) . getDbDate2) [] database 

但是，當然，上面沒有編譯，因爲它沒有類型檢查，因爲，例如：

λ> foldr ((:) . getDbDate2) [] theDatabase 
[Just 1911-05-01 09:28:43 UTC,Nothing,Nothing,Just 1921-05-01 09:28:43 UTC] 

換句話說，它可以與Nothing值返回Just UTCTime值的列表，在一起，不僅UTCTime值的列表。

所以我的問題是：如何編寫一個（幫助器？）函數，以便我不必使用filter），檢查其值是否爲DbNumber，如果是，則返回UTCTime組件？ （如果不是......它也有返回的東西（如Nothing？），而這正是我有麻煩，那就是使用Maybe UTCTime，然後讓Just UTCTime值等）

Answer 1

還有一些其他的答案在這裏覆蓋好的建議有關其他的方式來思考這個問題：使用catMaybes到Munge時間數據挑選出Maybe UTCTime後第二次S;使用列表推導和便利的語法來篩選出不匹配的模式;使用列表的一元結構來包含或跳過結果;並編寫一個定製的遞歸函數。在這個答案中，我將解答你的直接問題，展示如何使用已有的程序結構，而不必完全重新思考列表操作的方法 - 使用幫助函數調用foldr，該函數可以一次性完成所需的一切。

首先，我觀察到，現有的所有嘗試發送foldr無條件地調用一個函數(:)：

foldr ((:) . getDbDate1) [] (filter isDbDate database) 
foldr ((:) . getDbDate2) [] database 

這個模式的事情是，這意味着你走出foldr將有名單與您傳遞的函數的長度相同 - 因爲輸入列表中的每個(:)在輸出列表中變爲(:)。在您的第一個解決方案中，您通過從輸入列表中刪除了一些您不關心的條目來處理此問題;在第二種解決方案中，您通過在輸出列表中添加了多餘的無趣元素來處理此問題。

第三種解決方案是在決定是否調用(:)之前查看列表元素。這裏是一個可以如何做到這一點：特別

conditionalCons :: DatabaseItem -> [UTCTime] -> [UTCTime] 
conditionalCons (DbDate t) ts = t:ts 
conditionalCons _   ts = ts 

注意，第二個條款中，我們不叫(:) - 這濾掉名單的非匹配元素。我們也不關心丟失模式。現在，我們可以寫

filterDbDate3 :: [DatabaseItem] -> [UTCTime] 
filterDbDate3 = foldr conditionalCons [] 

測試在ghci中試驗：

> filterDbDate3 theDatabase 
[1911-05-01 09:28:43 UTC,1921-05-01 09:28:43 UTC] 

完美！

Answer 2

列表是單子。所以我們可以使用Monad類型的功能。

utcTimes :: [UTCTime] 
utcTimes = 
    theDatabase >>= 
    \ item -> 
    case item of 
     DbDate utcTime -> [utcTime] 
     _ -> [] 

這裏的(>>=)函數是關鍵。它與其他語言中的「flatMap」基本相同，如果鈴聲響起的話。

以下是一樣的上面在執行 - 符號表示：

utcTimes :: [UTCTime] 
utcTimes = 
    do 
    item <- theDatabase 
    case item of 
     DbDate utcTime -> [utcTime] 
     _ -> [] 

事實上，我們甚至可以概括這一個功能，這會爲任何單子超過UTCTime工作（當然，MonadPlus真的）：

pickUTCTime :: MonadPlus m => DatabaseItem -> m UTCTime 
pickUTCTime item = 
    case item of 
    DbDate utcTime -> return utcTime 
    _ -> mzero 

utcTimes :: [UTCTime] 
utcTimes = 
    theDatabase >>= pickUTCTime 

Answer 3

一個簡單的方法來做到這一點是如下

filterDbDate :: [DatabaseItem] -> [UTCTime] 
filterDbDate db = filterDbDate' [] db 
    where filterDbDate' :: [UTCTime] -> [DatabaseItem] -> [UTCTime] 
     filterDbDate' rest ((DbDate utcTime):xs) = filterDbDate' (rest ++ [utcTime]) xs 
     filterDbDate' rest (_:xs) = filterDbDate' rest xs 
     filterDbDate' rest _  = rest 

也就是說，您傳遞另一個包含要保留的值的參數。如果仔細觀察，您會發現這正是foldl所指示的類型foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b（您也可以使用foldr執行此操作，但我會將其保留給您），但它一次只能包含一個元素。所以我們重寫filterDbDate'也是這樣。

filterDbDate2 :: [DatabaseItem] -> [UTCTime] 
filterDbDate2 db = foldl filterDbDate'' [] db 
    where filterDbDate'' :: [UTCTime] -> DatabaseItem -> [UTCTime] 
     filterDbDate'' rest (DbDate utcTime) = (rest ++ [utcTime]) 
     filterDbDate'' rest _    = rest 

這不是最高效的函數，但希望您會看到如何將函數轉換爲使用摺疊。試用foldr！

Answer 4

一個簡單的列表解析會做

filterDbDate xs = [ x | DbDate x <- xs ] 

Answer 5

有一些很好的答案，但我想添加另一種方法如何找到這些任務的解決方案。

首先，寫出最簡單可能的解決方案，即一個帶有直接遞歸的解決方案。

filterDbDate :: [DatabaseItem] -> [UTCTime] 
filterDbDate ((DbDate time):items) = time:(filterDbDate items) 
filterDbDate (_   :items) =  filterDbDate items 

這有助於瞭解所涉及的結構並使您能夠熟悉所需的實際步驟。這不是最高性能的版本，但它很容易編寫，而且對於手頭的任務而言通常已足夠。

下一步將是使代碼更具性能尾部遞歸。這是一個簡單的，幾乎是機械的轉變。

1. 確定累加器類型。這通常也是返回類型;在這種情況下，列表。這給了你新的第一線

   filterDbDate :: [DatabaseItem] -> [UTCTime] 
   filterDbDate = go [] 
       where ... 
   

2. 現在把原來的功能，並通過與蓄電池替換每個遞歸調用，然後把結果放入一個遞歸調用go把它變成內部go功能。

   go acc ((DbDate time):items) = go (time:acc) items 
       go acc (_   :items) = go  acc items 
   

3. 添加處理結束案例。請注意，操作順序將顛倒過來。

   go acc []     = reverse acc 
   

4. 將結束案例的處理移動到原始調用中。如果你想在這裏停下來，這不是必要的，但它有助於在摺疊的路上。

   filterDbDate = reverse . go [] 
       where 
       go acc [] = acc 
       ... 
   

我們把它轉換成摺疊。累加器與摺疊將使用的相同，並且轉換再次幾乎是機械的。

1. 通過調用摺疊替換呼叫到go。

   filterDbDate :: [DatabaseItem] -> [UTCTime] 
   filterDbDate = reverse . foldl f [] 
   

2. 打開go爲f通過除去模式的列表部分相匹配，最終的情況下，和遞歸調用。

   where f acc (DbDate time) = time:acc 
        f acc _   =  acc 
   

3. 思考一下，如果最好扭轉遞歸的方向。

   filterDbDate :: [DatabaseItem] -> [UTCTime] 
   filterDbDate = foldr f [] 
       where f (DbDate time) = (time:) 
        f _    = id 
   

現在進行最後的清理，額外加分和激怒Haskell的教師使其作爲通用的，你可以不打破東西。

{-# LANGUAGE NoImplicitPrelude, GADTs #-} 
import ClassyPrelude 

filterDbDate :: (MonoFoldable items, Element items ~ DatabaseItem 
       , Monoid times, SemiSequence times, Element times ~ UTCTime) 
      => items -> times 
filterDbDate = foldr f mempty 
    where f (DbDate time) = cons time 
     f _    = id