搜索兩個元素中的字符串

再一次我被卡住了。
我有一對字符串對[(String, String)]的列表，並希望在其中查找另一個字符串。當子串匹配元組中的第一個時，我想返回第二個，反之亦然。搜索兩個元素中的字符串

我有一些想法，但又一次，我不知道如何在Haskell中正確應用函數。我的第一個想法是使用map，但那不會真的能給我一個字符串作爲結果嗎？

我正在考慮使用filter。首先搜索一對中的第一個子串，然後搜索第二個子串。
這是據我得到：

search :: String -> [(String, String)] -> String 
search substr xs = filter(==substr) xs.fst

而且它甚至不工作：/

我很感謝任何意見！

感謝

來源

2013-12-14 Henry

我建議你換行返回類型Maybe的情況下，子是找不到的。

search :: Eq a => a -> [(a, a)] -> Maybe a 
search s xs = case lookup s xs of 
       Just x -> Just x 
       Nothing -> lookup s xs' 
    where xs' = map swap xs

如果你不想Maybe來包裝它，只需使用fromJust功能，並相應地改變類型簽名。在上面的代碼中，您正在使用庫定義的lookup函數。如果在第一次搜索中查找失敗，則交換元組並再次執行lookup操作。另外，不要忘記從Data.Tuple導入swap。

演示了ghci：

ghci > let a = [("hi","bye"),("cat", "dog")] 
ghci > search "hi" a 
Just "bye" 
ghci > search "dog" a 
Just "cat"

來源

2013-12-14 16:53:53 Sibi

這當然可以被推廣一下。 – Ingo

謝謝！但是如果我想返回一個默認的字符串以防萬一找不到，該怎麼辦？撇號的確做了什麼？' – Henry

@Ingo，謝謝，推廣它。 @Henry，Pattern在'Nothing'上匹配並返回你想返回的默認字符串。撇號沒什麼特別的。它只是與'xs'有關的另一個變量。 – Sibi

您可以致電名單上lookup，然後在列表中交換的每個元組後致電查詢。但是這意味着可能遍歷列表兩次。

lookup' k = foldl acc Nothing 
    where 
     acc (Just x) _ = Just x 
     acc _ (a,b) | k == b = Just a | k == a = Just b | otherwise = Nothing

這樣你只能遍歷列表一次。如果元素存在，此版本不會在無限列表上終止。您可以使用foldr編寫它，但是該版本的編號爲lookup' 0 [(0,1), undefined] == undefined，而不是首選行爲。

你也可以使用顯式遞歸來編寫它。一次，使用顯式遞歸更好！它包含了兩種以上所覆蓋的情況：

lookup'' k [] = Nothing 
lookup'' k ((a,b):xs) 
    | k == a = Just b 
    | k == b = Just a 
    | otherwise = lookup'' k xs 

>lookup'' 1 [(1,0), undefined] 
Just 0 
>lookup'' 1 (zip [0..] [0..]) 
Just 1

來源

2013-12-14 17:19:51 user2407038

確實。實際上，如果元素不存在，'map swap'版本會遍歷列表三次！ –

如果給出無限的元組列表，「lookup」不會終止，即使找到了「k」，而「lookup」也沒有。 – pat

user2407038的解決方案，lookup''是最有效的，因爲它遍歷該列表只有一次，當發現匹配的早期終止。它可以如下寫入而沒有顯式遞歸：

import Control.Monad (msum) 

lookup'' k = msum . map match 
    where match (a, b) | k == a = Just b 
        | k == b = Just a 
        | otherwise = Nothing

來源

2013-12-14 18:25:56 pat

搜索兩個元素中的字符串

回答

相關問題