Comparing with List Patterns

Question

First consider the following code, which counts the number of blank spaces in a string:

countSpaces :: String -> Int
countSpaces [] = 0
countSpaces (c : restOfString)
    = d + countSpaces restOfString
       where d = if c == ’ ’ then 1
                             else 0

Here is my questions:

1, if I make a call: countSpaces "abc" , then what happens when this function tries to match the string "abc" with (c: restOfString). I mean, restOfString is: "abc" in this call but what is (c:restOfString) ? you are 'consing' something(the variable? c ) to restOfstring and then you are trying to match? I just don't get it.

2, I try to run the code but I am getting a parse error why?

parse error on input ‘´’

3,will this function call countSpaces to infinity? since restOfString is always the same and not reduced, eg. making the call countSpaces "aaa" will not change after the first call,second or any call, right?

Added afterwards*

Now consider this code which completes the same task:

countSpaces :: String -> Int
countSpaces [] = 0
countSpaces (’ ’ : restOfString)
        = 1 + countSpaces restOfString
countSpaces (_ : restOfString)
        = 0 + countSpaces restOfString

1, so if we try to make a call countSpaces "abc" the pattern (’ ’ : restOfString) will just get bigger since every time countSpaces gets called this will just cons a ' ' to restOfString, Unless every time countSpaces will get called the first char in the string will be changed to: ' ' . so in the first call of countSpaces "abc" then (’ ’ : restOfString) is ' ':"bc" , which is confusing right, since it replaced "a" with a blank instead of consing it so that we get: " abc"

"abc" is just syntactic sugar for ['a', 'b', 'c'] or 'a':'b':'c':[]. — chepner
– chepner, Commented Apr 29, 2016 at 18:10
You're using weird apostrophes. Compare this: ' to yours, ’. They're different characters. — Arnon
– Arnon, Commented Apr 29, 2016 at 19:15

Chad Gilbert · Accepted Answer · 2016-04-29 19:02:02Z

6

1, if I make a call: countSpaces "abc" , then what happens when this function tries to match the string "abc" with: (c: restOfString).

When you match that pattern using the cons operator :, the element on the left of : is the first element in the list, and on the right of : is the remainder of the list. The following are equivalent:

"abc" == 'a' : "bc"

Since a String is a list of characters (specifically, [Char]), the above could also be written as:

"abc" == 'a' : 'b' : 'c' : []

2, I try to run the code but I am getting a parse error why?

Your parse error is because you are using the wrong character for a single quote. You are using unicode 0x2019 when you should be using the ASCII/Unicode Apostrophe character: '

3,will this function call countSpaces to infinity?

It will only count to infinity if your string is infinite. The reduction actually happens in this part:

 countSpaces restOfString

To understand why, see my answer for part 1. In the case of "abc", restOfString is "bc".

4, so if we try to make a call countSpaces "abc" the pattern: (’ ’ : restOfString) will just get bigger since everytime countSpaces gets called this will just cons a ' ' to restOfString, Unless every time countSpaces will get called then the first char in the string will be changed to: ' ' . so in the first call of countSpaces "abc" then (’ ’ : restOfString) is ' ':"bc" , which is confusing right?

I think your confusion originates from the fact that pattern matching and building a list look identical. i.e. what happens when you write (' ':restOfString) depends entirely on context.

You can think of a function definition as being broken up into two parts separated by the = sign:

countSpaces (' ' : restOfString)   =   1 + countSpaces restOfString
^                              ^   ^   ^                          ^
|                              |   |   |                          |
--------------------------------   |   ----------------------------
               |                   |                 |
        Pattern Matching       Separator       Function Body

The Pattern Matching portion does not affect the output. When you use (' ' : restOfString) on the Pattern Matching side, you are saying, "If the parameter passed into the countSpaces function starts with a space, then return what is in this function body. If the first character is not a space, then try the next pattern defined". In either case (whether it is matched or not), the value passed into countSpaces is not modified in any way (it does not have a space put in front of it; that kind of thing only happens in the function body).

Conversely, when you put (' ' : restOfString) in the Function Body, you are saying "return the restOfString value prefixed with a space character".

edited Apr 29, 2016 at 19:02

answered Apr 29, 2016 at 17:28

Chad Gilbert

36.4k4 gold badges93 silver badges99 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

J.doe Over a year ago

Ok, here is what confuses me: if we were to change: c to 'c' would that imply that you would change the first element in restOfList to 'c' ? but ('c':"ab") would produce "cab". The result differs if it is a parameter(as in this function) or a string(that is not a parameter to a call) @Chad Gilberg

Chad Gilbert Over a year ago

('c':"ab") in the context of pattern matching will only ever match the string "cab". If you are instead returning ('c':"ab"), then you are returning the string "cab". Remember that c is a variable name and 'c' is a Char because it is surrounded by single quotes.

Chad Gilbert Over a year ago

countSpaces (' ' : restOfString) = 1 + countSpaces restOfString and countSpaces (_ : restOfString) = 0 + countSpaces restOfString are valid ways of solving the problem through pattern matching.

J.doe Over a year ago

sorry for asking so many question, I just want to understand , hope you could bear with me :) . I changed(added) in the main question above, maybe u could take a look :) @Chad Gillberg

Chad Gilbert Over a year ago

I've added a response to my answer that should hopefully shed a bit more light on the difference between pattern matching and function bodies.

|

Collectives™ on Stack Overflow

Comparing with List Patterns

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related