CODEWITHSUNDEEP
haskell
vixero
vixero

Reputation: 514

Haskell - Recursion/Syntax

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.

Upvotes: 1

Views: 108

Answers (2)

daniel gratzer
daniel gratzer

Reputation: 53881

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!

Upvotes: 6

user268396
user268396

Reputation: 11976

This is an implementation of filter:

  1. a-> Bool means a function (predicate) which takes an a and spits out a Bool.
  2. The function does not remove elements from the input list. Instead, it builds a new one.
  3. If the predicate evaluates to true for the head of the input list, then it is prepended (:) 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.

Upvotes: 4

Related Questions