Haskell - filter string list based on some conditions

Question

I am new in this comunity. I learn Haskell and have difficulties with Haskell-coding. I hope you can help me.

I searched here and in Google, without any success.

My problem ist as fowllows: I want to write a function which takes a list as parameter like this:

myStringListFilter :: [String] -> [String]

process the following steps:

1. Remove the first letter

   myStringListFilter myList = map tail strListe myList
   

2. Filter every element in the list which begins with "u" or "U".

   myStringListFilter myList = filter (´elem´ ['u', 'U']) (map tail strListe myList)
   

Step two doesn't work. I get error.

How do I achieve the solution, if I want the following:

Input: ["butter", "chees", "aUbergine", "egg", "milk", "bUbble", "curry"]

Output: ["chees", "egg", "milk"]

Answer 1

I'm a beginner too, so maybe my explanation will help.

What does the point "." mean and what is it called? For instance in this line:

filterBy notAllowedChars = not . (elem notAllowedChars) . head . tail

The dot does "function composition", where:

(f1 . f2) xs 

is defined to be:

f1 (f2 xs) 

What that means is that haskell takes the function on the righthand side of the dot, f2, and applies xs to it:

(f2 xs)

Then haskell takes the return value of f2 and applies it to f1:

f1 retValFromf2

Here is a simple example using function composition:

func1 x = x * 2
func2 x = x + 10

dostuff x = (func1 . func2) x

ghci> dostuff 0
20

And how does the filter works here? I don't see any filter function in this line:

filterBy notAllowedChars = not . (elem notAllowedChars) . head . tail

That function creates a filter. That function is a substitute for the non point free function I provided first:

myFilter :: String -> String -> Bool
myFilter notAllowedChars str = 
    if head (tail str)  `elem` notAllowedChars
    then False    --if match, reject this string
    else True     --if no match, include this string in result list

So I should have named the point free function better:

createFilter notAllowedChars = not . (`elem` notAllowedChars) . head . tail

What you see on the righthand side is a chain of function compositions, and the rightmost function, tail, executes first. tail takes a list as an argument and returns a list. The returned list is then applied to head. head takes a list as an argument and returns a single element of the list. The partial function:

(`elem` notAllowedChars) 

takes a single elment on its left side as an argument, which is exactly what head returns, and elem returns a Bool. not takes a Bool as an argument, e.g. True, and returns a Bool, e.g. False. Note that when you chain functions together with the dot you must make sure that whatever is returned by the function on the righthand side of the dot is an argument that the function on the lefthand side of the dot accepts.

1. What is actually "point-free"?

I think it means that no argument is specified in the function definition. I like to think of it as xs being a list of points, and when the xs term doesn't appear anywhere in the function definition, then you have written the function in point free style. The dot is not 'a point'. If the dot were 'a point', then something like this:

not . (`elem` notAllowedChars) . head . tail

...could hardly be called 'point free'.

In Haskell, if you have a function defined like this:

myfunc xs = head xs

where xs appears on the righthand side on both sides of the equals sign, then just like an equation, you can cancel them out producing:

myfunc = head

Then if you call:

myfunc xs

you get the same result as with the original myfunc definition.

Now look at this function definition:

myfunc xs = tail (head xs)

In this case, if you remove the xs from both sides you get:

myfunc = tail (head)

But tail takes a list as an argument--not a function, so that would produce an error. However, if you rewrite the righthand side of myfunc using function composition:

myfunc xs = (tail . head) xs

…then once again you can cancel the xs from both sides:

myfunc = tail . head

And that is point free style again. As for why you would bother rewriting a function in point free style, I'm not sure. For now, I think of it as I trick I can do. You will find that when you study a computer programming language, you learn a bunch of tricks. Sometimes, you are not sure why a trick is useful when you learn it. You just have to accept the fact that as a beginner, you don't always get to understand why a trick is useful. It isn't until you become more experienced that the usefulness of a certain trick becomes apparent.

In any case, writing a function in point free style does not change how the function works, so don't worry about it if you don't understand it. As you study Haskell more, then you can do some of the more advanced things.

My intention is to comprehens Haskell

You should realize that 1) In my opinion, Haskell is an extremely difficult language, 2) You can never 'know' a computer programming language. The level of understanding is infinite. So the more you study and use a language, the more you learn about it. That means that no matter how expert you are in a language, you will still encounter code that is difficult or impossible to comprehend.

@7Stud

...does not produce the correct output.

As I wrote above, the code of Daniel Fischer works fine as yours. Could you please tell me what you mean by that?

I posted Daniel Fischer's example and the output it produces. If you compare that output to the output you posted in your op, they don't match.

Answer 2

The type of filter is

filter :: (a -> Bool) -> [a] -> [a]

so if you want to filter a list of Strings according to a predicate, you need a function String -> Bool, but what you wrote, (`elem` ['u',U']) has type Char -> Bool.

So you need a function

beginsWithU :: String -> Bool

the easiest way to define it is

beginsWithU (c:_) = c == 'u' || c == 'U'
beginsWithU _ = False                      -- empty list

Then you have misunderstood how filter works, it keeps the elements satisfying the predicate, you want to remove them, so you need to compose the predicate with a not (or define as doesn'tbeginWithU directly).

However, as 7stud points out, you do not actually want to change the elements you want to keep from the original list, what

myStringListFilter myList = filter (not . beginsWithU) (map tail myList)

or, point-free:

myStringListFilter = filter (not . beginsWithU) . map tail

would achieve. So you need to incorporate the tail into the predicate too, and need no map, that would yield

myStringListFilter = filter (not . beginsWithU . tail)

or, if the possibility that an empty String occurs in the input list shall be dealt with benignly,

myStringListFilter = filter (not . beginsWith . drop 1)

since tail "" would produce an *** Exception: Prelude.tail: empty list whereas drop 1 "" produces "".

But, as you want to keep the original list element, you can also define the predicate to directly look at the second character,

secondCharIsU :: String -> Bool
secondCharIsU (_:c:_) = c == 'u' || c == 'U'
secondCharIsU _       = False

myStringListFilter = filter (not . secondCharIsU)

Answer 3

The proposed solution:

beginsWithU (c:_) = c == 'u' || c == 'U'
beginsWithU _ = False      

myStringListFilter myList = filter (not . beginsWithU) (map tail myList)


ghci>myStringListFilter ["butter", "cheese", "aUbergine", "egg", "milk", "bUbble", "curry"] 
["heese","gg","ilk"]

...does not produce the correct output.

map changes the original strings, so filtering a list of map'ed strings will not produce a list containing any of the original strings. The op needs to filter the original list with a custom filter:

myFilter :: String -> String -> Bool
myFilter notAllowedChars str = 
    if head (tail str)  `elem` notAllowedChars
    then False    --if match, reject this string
    else True     --if no match, include this string in result list 


ghci>filter (myFilter "uU") ["butter", "cheese", "aUbergine", "egg", "milk", "bUbble", "curry"] 
["cheese","egg","milk"]

point-free:

filterBy :: String -> String -> Bool
filterBy notAllowedChars = 
    not . (`elem` notAllowedChars) . head . tail 

Remember that an array of chars, such as ['u', 'U'], is the same thing as the String "uU".