CODEWITHSUNDEEP
listhaskell
user1670032
user1670032

Reputation: 770

Finding pairs in a list

I'm trying to look for pairs of elements in a list, assuming that they are the only pair in the list, and there are no more than 3 identical consecutive elements.

I have a function that takes in a list, and returns the index of the first element of the pair, if there is any. If not, then it returns -1

searchForPairs xs = searchHelp xs ((genericLength xs) - 1)
    where searchHelp xs n
        | searchHelp xs 0 = -1              -- no pairs found
        | (xs !! n) == (xs !! (n - 1)) = n
        | otherwise = searchHelp xs n-1

For some reason, it is returning the error:

Couldn't match expected type `Bool' with actual type `Int'
In the expression: n
In an equation for `searchHelp':
    searchHelp xs n
      | searchHelp xs 0 = - 1
      | (xs !! n) == (xs !! (n - 1)) = n
      | otherwise = searchHelp xs n - 1
In an equation for `searchForPairs':
    searchForPairs xs
      = searchHelp xs ((genericLength xs) - 1)
      where
          searchHelp xs n
            | searchHelp xs 0 = - 1
            | (xs !! n) == (xs !! (n - 1)) = n
            | otherwise = searchHelp xs n - 1

It seems like it should work. Any ideas why it is not?

Upvotes: 0

Views: 1667

Answers (4)

Olivier Verdier
Olivier Verdier

Reputation: 49246

For what it's worth, here is a somewhat idiomatic (and point-free) implementation of what you are trying to do:

searchPairs :: Eq a => [a] -> Maybe Int
searchPairs = interpret . span (uncurry (/=)) . (zip <*> tail)
    where
    interpret (flag, res) = if null flag then Nothing else Just $ length res

Explanation: zip <*> tail creates a list of pairs of successive elements (using the reader Applicative type class). uncurry (/=) tests if such a pair is made of identical elements. Finally, interpret translates the result in a value of Maybe Int type.

Upvotes: 1

gereeter
gereeter

Reputation: 4761

You have two problems. The first is in this line:

        | otherwise = searchHelp xs n-1

The compiler interperets this as (searchHelp xs n) - 1, not searchHelp xs (n-1), as you intended. The second problem is in you use of guards:

        | searchHelp xs 0 = -1              -- no pairs found

Since searchHelp xs 0 is not a boolean expression (you wanted to use it as a pattern), the compiler rejected it. I can see two easy solutions:

searchForPairs xs = searchHelp xs ((genericLength xs) - 1)
    where searchHelp xs n
        | n == 0 = -1              -- no pairs found
        | (xs !! n) == (xs !! (n - 1)) = n
        | otherwise = searchHelp xs (n-1)

and

searchForPairs xs = searchHelp xs ((genericLength xs) - 1)
    where
      searchHelp xs 0 = -1         -- no pairs found
      searchHelp xs n
        | (xs !! n) == (xs !! (n - 1)) = n
        | otherwise = searchHelp xs (n-1)

Now, unfortunately, although this works, it is terribly inefficient. This is because of your use of !!. In Haskell, lists are linked lists, and so xs !! n will take n steps, instead of 1. This means that the time your function takes is quadratic in the length of the list. To rectify this, you want to loop along the list forward, using pattern matching:

searchForPairs xs = searchHelp xs 0 where
    searchHelp (x1 : x2 : xs) pos
        | x1 == x2 = pos
        | otherwise = searchHelp (x2 : xs) (pos + 1)
    searchHelp _ _ = -1

Upvotes: 2

pat
pat

Reputation: 12749

I couldn't quite grok what you want to do, but from the code, it looks like you're trying to find two consecutive elements in a list that are equal. Instead of using !! to index the list, you can use pattern matching to extract the first two elements of the list, check if they are equal, and continue searching the remainder (including the second element) if they are not. If the list doesn't have at least two elements, you return Nothing

searchForPairs xs = go 0 xs where
  go i (x1:xs@(x2:_)) | x1 == x2 = Just i
                      | otherwise = go (i+1) xs
  go _ _ = Nothing

Upvotes: 2

Andrej Bauer
Andrej Bauer

Reputation: 2477

@gereeter already explained your errors, I would just like to point out that you should not return -1 in case the answer is not found. Instead, you should return Nothing if there is no answer and Just pos if the answer is pos. This protects you from many kinds of errors.

Upvotes: 2

Related Questions