CODEWITHSUNDEEP
haskellrecursion
Johnathan Scott
Johnathan Scott

Reputation: 291

Recursively dropping elements from list in Haskell

Right now I'm working on a problem in Haskell in which I'm trying to check a list for a particular pair of values and return True/False depending on whether they are present in said list. The question goes as follows:

Define a function called after which takes a list of integers and two integers as parameters. after numbers num1 num2 should return true if num1 occurs in the list and num2 occurs after num1. If not it must return false.

My plan is to check the head of the list for num1 and drop it, then recursively go through until I 'hit' it. Then, I'll take the head of the tail and check that against num2 until I hit or reach the end of the list.

I've gotten stuck pretty early, as this is what I have so far:

after :: [Int] -> Int -> Int -> Bool
after x y z
    | y /= head x =  after (drop 1 x) y z

However when I try to run something such as after [1,4,2,6,5] 4 5 I get a format error. I'm really not sure how to properly word the line such that haskell will understand what I'm telling it to do.

Any help is greatly appreciated! Thanks :)

Edit 1: This is the error in question: 

Program error: pattern match failure: after [3,Num_fromInt instNum_v30 4] 3 (Num_fromInt instNum_v30 2)

Upvotes: 0

Views: 1430

Answers (4)

Zacharie 007
Zacharie 007

Reputation: 126

   after :: [Int] -> Int -> Int -> Bool
   Prelude> let after xs a b =  elem b . tail $ dropWhile (/=a) xs

Examples:

  Prelude> after   [1,2,3,4,3] 88  7
  *** Exception: Prelude.tail: empty list

It raises an exception because of tail. It's easy to write tail' such that it won't raise that exception. Otherwise it works pretty well.

  Prelude> after  [1,2,3,4,3] 2  7
  False
  Prelude> after   [1,2,3,4,3] 2  4
  True

Upvotes: 0

dfeuer
dfeuer

Reputation: 48580

after xs p1 p2 = [p1, p2] `isSubsequenceOf` xs

So how can we define that? Fill in the blanks below!

isSubsequenceOf :: Eq a => [a] -> [a] -> Bool

[] `isSubsequenceOf` _ = ?
(_ : _) `isSubsequenceOf` [] = ?
xss@(x : xs) `isSubsequenceOf` (y:ys)
  | x == y = ?
  | otherwise = ?

Upvotes: 2

Joe Hillenbrand
Joe Hillenbrand

Reputation: 875

after :: Eq a => [a] -> a -> a -> Bool
after ns a b =
  case dropWhile (/= a) ns of
    [] -> False
    _:xs -> b `elem` xs

http://hackage.haskell.org/package/base-4.8.2.0/docs/src/GHC.List.html#dropWhile

Upvotes: 3

Kwarrtz
Kwarrtz

Reputation: 2753

Try something like this:

after :: [Int] -> Int -> Int -> Bool
after (n:ns) a b | n == a = ns `elem` b
                 | otherwise = after ns a b
after _      _ _ = False

Basically, the function steps through the list, element by element. If at any point it encounters a (the first number), then it checks to see if b is in the remainder of the list. If it is, it returns True, otherwise it returns False. Also, if it hits the end of the list without ever seeing a, it returns False.

Upvotes: 4

Related Questions