CODEWITHSUNDEEP
haskell
Henry
Henry

Reputation: 777

Search for String in both elements of pairs

Again I am stuck.
I have a list of pairs of strings [(String, String)] and want to look for another String in it. When the substring matches the first in the tuple, I'd like to return the second one and vice versa.

I had some ideas but again, I don't know how to correctly apply functions in Haskell. My first idea was to use map but that wouldn't really be able to give me a String as a result, would it?

I was thinking about using filter. First searching the substring in the first of the pair and then in the second ones.
This is as far as I got:

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

And it doesn't even work :/

I'd be thankful for any kind of advice!

Thanks

Upvotes: 1

Views: 184

Answers (3)

user2407038
user2407038

Reputation: 14578

You can call lookup on the list, and then call lookup after swapping each tuple in the list. But this means possibly traversing the list twice.

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

This way you traverse the list only once. This version doesn't terminate on infinite lists if the element is present. You can write it using foldr, but that for that version, lookup' 0 [(0,1), undefined] == undefined as opposed to the preferred behavior.

You can also write it using explicit recursion. For once, using explicit recursion is better! It covers both of the cases covered above:

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

Upvotes: 3

pat
pat

Reputation: 12749

user2407038's solution, lookup'' is the most efficient since it traverses the list only once, and terminates early when a match is found. It can be written without explicit recursion as follows:

import Control.Monad ( msum )

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

Upvotes: 1

Sibi
Sibi

Reputation: 48644

I would suggest you to wrap the return type in Maybe in case the substring isn't found. 

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

If you don't want to wrap it with Maybe, just use the fromJust function and change the type signature accordingly. In the above code, you are using the library defined lookup function. And in case the lookup fails in the first search you exchange the tuples and again perform the lookup operation. Also, Don't forget to import swap from Data.Tuple.

Demo in ghci:

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

Upvotes: 4

Related Questions