Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

a haskell function to test if an integer appears after another integer

I'm writing a function called after which takes a list of integers and two integers as parameters. after list num1 num2 should return True if num1 occurs in the list and num2 occurs in list afternum1. (Not necessarily immediately after).

after::[Int]->Int->Int->Bool
after [] _ _=False
after [x:xs] b c 
    |x==b && c `elem` xs =True 
    |x/=b && b `elem` xs && b `elem` xs=True

This is what I have so far,my biggest problem is that I don't know how to force num2 to be after num1.

like image 606
user3358850 Avatar asked Jan 04 '23 03:01

user3358850


2 Answers

There's a few different ways to approach this one; while it's tempting to go straight for recursion on this, it's nice to avoid using recursion explicitly if there's another option.

Here's a simple version using some list utilities. Note that it's a Haskell idiom that the object we're operating over is usually the last argument. In this case switching the arguments lets us write it as a pipeline with it's third argument (the list) passed implicitly:

after :: Int -> Int -> [Int] -> Bool
after a b = elem b . dropWhile (/= a)

Hopefully this is pretty easy to understand; we drop elements of the list until we hit an a, assuming we find one we check if there's a b in the remaining list. If there was no a, this list is [] and obviously there's no b there, so it returns False as expected.

You haven't specified what happens if 'a' and 'b' are equal, so I'll leave it up to you to adapt it for that case. HINT: add a tail somewhere ;)

Here are a couple of other approaches if you're interested:

This is pretty easily handled using a fold;

We have three states to model. Either we're looking for the first elem, or we're looking for the second elem, or we've found them (in the right order).

data State =
  FindA | FindB | Found
  deriving Eq

Then we can 'fold' (aka reduce) the list down to the result of whether it matches or not.

after :: Int -> Int -> [Int] -> Bool
after a b xs = foldl go FindA xs == Found
  where
    go FindA x = if x == a then FindB else FindA
    go FindB x = if x == b then Found else FindB
    go Found _ = Found

You can also do it recursively if you like:

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

Cheers!

like image 133
Chris Penner Avatar answered Jan 06 '23 18:01

Chris Penner


You can split it into two parts: the first one will find the first occurrence of num1. After that, you just need to drop all elements before it and just check that num2 is in the remaining part of the list.

There's a standard function elemIndex for the first part. The second one is just elem.

import Data.List (elemIndex)

after xs x y = 
    case x `elemIndex` xs of 
        Just i -> y `elem` (drop (i + 1) xs)
        Nothing -> False
like image 21
kraskevich Avatar answered Jan 06 '23 16:01

kraskevich