Haskell 101

February 3, 2008

Count matches in a list

Filed under: Functional programming, Guards, Haskell, Pattern matching, Recursion — Haskell 101 blogger @ 8:07 pm

What if, instead of just checking to see whether a value exists in a list, we want to count the number of times it is in the list? In other words, we want a function that will take a value, compare it to a given list of integers, and return an integer with the number of times it matches.As usual, let’s start with our function signature, which we have just about created with the previous sentence: 

(1) instances::Int->[Int]->Int

 By the way, we’ll generalize this function to be used for a list of any type (integers, strings, etc.) in a near-future posting as a way of introducing the concept of classes in type signatures. But for now, let’s stick with the simple case of integers. OK, we know that we need to look through the list, adding one to our total number of instances for each item that matches our chosen item. Since Haskell does not use the the loop structures typical in imperative programming, we can use what turns out to be a very simple approach with recursion. One helpful way to think about this is ask what will end the recursion. Usually it is an empty list. If we are evaluating our function on an empty list, we know that empty list does not match our chosen value. In other words: 

(2) instances x [] = 0

 What about if we are evaluating a non-empty list? Well, let’s split that list into one item in the list and the rest of the list, using the (y:ys) concept. Here, y represents the first item, and ys represents the remainder of the list. We should add one to our total if y equals our chosen value. Then we should re-run our function on the remainder of the list, or ys. In an imperative programming language, we might say something likeif x==y then return 1+(instances x ys)else return (instances x ys)But in Haskell, we’ll use the concept of guards to do this. 

(3) instances x (y:ys)
	| x==y = 1+(instances x ys)
	| otherwise = instances x ys

 All those equal signs can be confusing to a new Haskeller. Remember, the first thing just to the right of the guard (|) is an expression that will be evaluated. So x==y is evaluated, and, if true, then the function evaluates to the expression onthe right. Otherwise, the function will evaluate to to the expression to the right of the “otherwise” item.

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: