I have here some code and I need someone to explain me what it does.
fun :: (a -> Bool) -> [a] -> [a]
fun p [] = []
fun p (x:xs) = if (p x) then (x : fun p xs) else (fun p xs)
I don't get the part
a -> Bool
and
(p x)
So the code iterates through a list, if it's empty, it returns an empty list. If the list is not empty, it checks if (p x). If it's true, it leaves the element unchanged and goes to the next element in the list, else it removes the element.
So the first bit is the type signature
fun :: (a -> Bool) -> [a] -> [a]
The (a -> Bool) signifies a function that takes an a and returns a Bool. Since it's being passed as an argument, fun is a "higher order function" — a function that takes another function as an argument (here p, using "p" for "predicate"). The second argument is a list of a's and a list of a's is returned.
The [] case is quite clear. However, when we have at least one element (the x in (x:xs) pattern) we check to see whether p returns true for it (i.e. when (p x) is called). If it does, we add the element to the front of our resulting list, and if not, we just throw that element away. Then we recurse.
Let's step through an example to see what this does.
fun even [1, 2, 3]
if (even 1) then (1 : fun even [2, 3]) else (fun even [2, 3])
fun even [2, 3]
if (even 2) then (2 : fun even [3]) else (fun even [3])
2 : (fun even [3])
2 : (if (even 3) then (3 : fun even []) else (fun even []))
2 : (fun even [])
2 : []
[2]
Look familiar? That's just filter!
(a -> Bool) signifies a function that takes an a and returns a Bool", given OP is clearly a Haskell beginner.This is an implementation of filter:
a-> Bool means a function (predicate) which takes an a and spits out a Bool.:) to the result of evaluating fun on the tail of the input list; otherwise the result is fun evaluated on the tail of the input list.
