How do I compare a given variable list with an infinite list to find the first non-occurring variable in Haskell?

user_17534555 0
Viewed 62

hoping for some help on this one with my newbie Haskell code.

I'm trying to compare an input list of variables with an infinite list of variables

input = ["a", "b", "x"]
variables = ["a", "b", "c", "d", ... "a1", "b1", ... and so on]

I'd like to find the first non-occurring variable in the input list, in this case it should be "c".

I think the right way to go about it is using a filter...

ourFilter :: [Var] -> [Var] -> [Var]
ourFilter p [] = []
ourFilter p (x:xs) | matches x = x ourFilter xs
                   | otherwise = ourFilter xs

matches :: Var -> Bool
matches n = n `elem` variables

...but I'm getting the two errors thrown before compilation and I can't get my head around them:

• Couldn't match expected type ‘([Var] -> [Var] -> [Var])
                                -> [Var] -> [Var]’
              with actual type ‘[Char]’
• The function ‘x’ is applied to two arguments,
  but its type ‘[Char]’ has none

Can somebody help to explain what on earth is going on? Is this the right way to go?

Thanks!

haskell
3 Answers

List difference \\ can subtract a finite list from an infinite list:

> import Data.List
> head $ [1..] \\ [1,2,3,5,7,9]
4
user_32349590

You forgot a colon:

... = x : ourFilter xs
        ^

You also need to pass p again on each recursive call:

... | matches x = x : ourFilter p xs | otherwise = ourFilter p xs
                                ^                            ^

There are other problems (for example, the fact that p isn't ever actually used seems like a red flag), but this will get it compiling so that you can play with it and fix them yourself.

user_7916040

You should enumerate over the infinite list, and for each item check if it is a member of the list. If that is not the case, then return that value; otherwise recurse on the tail of the list. This thus looks like:

ourFilter :: [Var] -> [Var] -> Var
ourFilter input = go
    where go (x:xs)
        | x `elem` input = …  -- (1)
        | otherwise = …       -- (2)

Where I leave filling in the … parts as an exercise. For (1) you make recursive all to go with the tail of the list; and for (2) you return the variable, since that is the first one that does not occur.

One can turn this function into a function that uses foldr with:

ourFilter :: [Var] -> [Var] -> Var
ourFilter input = foldr f undefined
    where f x y | x `elem` input = …  -- (1)
                | otherwise = …       -- (2)

here y is the result of making a recursive call to the tail of the list.

user_675790
Related