How do I compare a given variable list with an infinite list to find the first non-occurring variabl-CodePudding

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!

CodePudding user response：

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

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

CodePudding user response：

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.

CodePudding user response：

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.