Overview | Schedule | Resources | Assignments | Home |
This handout covers the basics of programming in HasCl, which is essentially a subset of the functional language Haskell. Although the details are specific to the Funnie environment, most of it should apply to other Haskell systems such as Hugs or GHC (see http://www.haskell.org/ for more details on these and other implementations of the language). In comparison with other tutorials available on the web, the focus here will be on learning to work with recursion and some of the elementary data structures traditionally encountered in Computer Science II; it is not specifically about exploring the power of Haskell, which has many advanced features that we will not discuss.
When you start a session with Funnie you should see an expression window, plus a browseable list of pre-defined functions. This means that the system is ready to evaluate expressions, calculator-style, in the context of the standard collection of definitions known as the prelude. The prelude defines many powerful operations on numbers, strings, and lists. Try entering each of the following expressions at the prompt, clicking the evaluate button after each (or hitting Enter), and figure out what the responses mean; then test yourself by trying similar expressions and checking that you can predict what the responses will be.
1+2*3 1+2^3 (1+2)^3 product([1, 2, 3, 4, 5, 6]) product([1 .. 6]) sum([1 .. 6]) / length([1 .. 6]) sum([1 .. 6]) # length([1 .. 6]) 22/7 22.0/7 22#7 22%7 [1 .. 6] ++ reverse([1 .. 6]) "Hello" ++ "World!" toUpper('a') map(toUpper, "Hello!") map(sqrt, [1 .. 6]) map(odd, [1 .. 6]) head([1 .. 6]) tail([1 .. 6]) (head([1 .. 6]), head("Hello!")) zip([1 .. 6], "Hello!")
To use functions beyond those defined in the prelude, you will need to enter them in a definition window. From the Window menu, select ``New Definition Window,'' then click in the window to start typing. When the function is complete, click on the compile button; if the definition does not have any syntax errors, it will be added to the list of locally-defined functions in the top half of the function browser. Otherwise, read the message in the error window and try again.
For practice, enter the following definition:
fact(0) = 1 fact(n) = n * fact(n-1)
Once you have successfully entered a definition, it will be
available for use in the expression window just like the
functions in the prelude. With the above function definition,
you should now be able to enter an expression such as
fact(5)
to compute the factorial of 5 (5!). When you try this, you should also
click on the ``Open Stepper'' button to bring up a stepper
window, in which you can trace the individual evaluation
steps.
If you worked through the expressions in the previous section, you have already encountered most of the standard built-in types of values available in HasCl. Now we will look at each in more detail.
HasCl has a very rich collection of numeric values, but
as opposed to many programming languages, it does not have
separate types for integers and floating-point numbers;
instead, all numbers belong to the type Num
.
Unlike the type int
of Java, there is no upper
limit to the size of a Num
. For example, we
may use the fact
function defined above to
find 52! (which counts the number
of ways to arrange a deck of 52 playing cards):
fact(52) => 80658175170943878571660636856403766975289505440883277824000000000000
This 68-digit number is a value of type
Num
. HasCl will happily work with numbers
having thousands of digits, up to the limits of your
computer's memory. Arithmetic on large numbers is important
in applications such as cryptography, where schemes such as
RSA encryption are based on the ease of multiplying
multi-hundred-digit numbers (and the corresponding
difficulty of factoring the result back into the original
numbers).
All of the usual arithmetic operations are available on
Num
s: +
, -
,
*
, and /
. In general, division of
two integers will produce a rational number (for example,
try 22 / 8
). To divide a
by
b
and get an integer result, use the
#
operator: a # b
. This gives the
quotient; to get the remainder, use a % b
(this is the same as in Java). Exponentiation, which is not
a built-in operator in Java, is written with the caret
operator, ^
; that is, ab is written
a^b
.
We sometimes need to use an operator like a function. By
surrounding any operator in parentheses you can do just
that. For example, (+)
is a function which
takes two arguments, so (+)(1, 2)
is the same
as 1 + 2
.
Question: Convert the
expressions 1+(2*3)
and (1+2)*3
into equivalent calls to the functions (+)
and
(*)
. What can you discover about the
precedence rules for the arithmetic operators in HasCl
(that is, which of these two expressions is the same as
1+2*3
)?
The type Bool
represents truth conditions,
either true
or false
. It is
essentially equivalent to the boolean
type of
Java. Comparison operators such as ==
,
!=
(not equal), <
,
>=
, ..., return values of type
Bool
. The standard logical operations are
available: 1 < x && x < 10
is
true if x
is both greater than 1 and less than 10; x == 2 ||
odd(x)
is true if x
is either equal to
2 or odd; and
not(odd(x))
is true if x
is not odd (this can also be written
even(x)
).
Given a boolean value, the natural way to use it is to
make a decision between two choices. HasCl has a
conditional expression similar to that found in most
languages: if b
has type Bool
and
p
and q
are two expressions which
have the same type, then if b then p else q
is
an expression that evaluates to p
when
b
is true
and q
when
b
is false
. For example, if
1 < x && x < 10 then "OK" else "Out of
Range"
will evaluate to the string "OK"
whenever x
is strictly between 1 and 10, and
"Out of Range"
otherwise.
Question: Write an
expression using the variable x
which
evaluates to "Might be prime"
if
x
is either odd or equal to 2, and evaluates
to "Not prime"
otherwise. To turn this into a
function named primeTest
, enter the following
in a definition window and press Compile:
primeTest(x) = <your expression here>
(where <your expression here>
is
replaced by the expression). Test it on cases like
primeTest(2)
, primeTest(6)
, and
primeTest(15)
.
Question: Write a function
named myAnd
which takes two arguments,
x
and y
. Using
if-then-else
, the constants true
and false
, and the variables x
and y
, it should produce the same result as
the expression x && y
. That is, it
should produce true
when x
and
y
are both true
, and
false
otherwise, but you may not use the
built-in &&
operator.
The HasCl type Char
can represent any
single character. It is essentially identical to the
char
type in Java, even using the same
single-quote syntax: 'a'
is the character
a
. If you want a single-quote character, HasCl
uses the same backslash escape mechanism as Java:
'\''
. Here are some more escape codes for
characters that are otherwise hard to type:
\n |
newline | \r |
carriage return |
\t |
tab | \v |
vertical tab |
\a |
bell | \f |
form feed |
\b |
backspace | \\ |
backslash |
\' |
single-quote | \" |
double-quote |
Unlike Java, a Char
does not automatically
convert to an integer. If you want the ASCII code for a
character, use the ord
function. To convert
from an ASCII code back to a character, use the
chr
function. For example,
ord('A')
returns 65, while
chr(48)
gives '0'
.
Question: Given that the
ASCII codes of the digits are consecutive numbers from 48
for '0'
to 57 for '9'
, write a
function named digitToNum
that takes a digit
d
of type Char
and produces the
corresponding Num
. For example,
digitToNum('7')
should produce the result
7
(note that the result is the number 7, not the character '7'
).
As with many other parts of the HasCl
language, the syntax for strings is essentially the same as
in Java. That is, a string constant is a sequence of
characters surrounded by double-quotes: "Like
this"
. The escape codes listed above may be used to
embed ``difficult'' characters in strings: "My
favorite string is \"Hello World\"."
However, unlike
C and C++, where strings are arrays of characters
(reflecting the importance of the array in those
languages), in HasCl a String
is a list of elements of type
Char
. We will see more about lists below, but
one of the implications for strings is that the common
operation of appending two strings is achieved by using the
list append operator, ++
. For example,
"Hello" ++ "World"
evaluates to
"HelloWorld"
.
Question: Write a function
named echo
that takes a string s
and produces a new string with s
followed by
s
again in parentheses. For example,
echo("Hello")
should evaluate to "Hello
(Hello)"
. Be careful to get the correct spacing.
Several values may be packaged into a single data item
by wrapping them in a tuple. A
tuple is written as a comma-separated sequence of values in
parentheses: (42, 'a', "Hello", true)
. There
may be any number of values (even none at all) in a tuple;
the special case of two values is called a pair. The order of the values
matters, so the pair (1, 2)
is different from
the pair (2, 1)
. The type of a tuple is
written as a tuple of types, so these pairs each have type
(Num, Num)
, while the first tuple above has
type (Num, Char, String, Bool)
.
Question: Invent an
expression which has the type (Bool, Char,
String)
. Now find an expression whose type is
((Bool, Char), String)
(note the extra
parentheses). Recall that the type of an expression is
displayed after the colons (::
) when it is
evaluated in an expression window.
Tuples can hold a variety of types of values; they are roughly analogous to structs in C++ or simple objects in Java (although the fields are accessed only by position, not by name). One disadvantage of using a tuple is that a particular tuple type will always contain the same number of values. If we want to store a varying number of values in a single data object, we use a list. In this sense, lists are the HasCl equivalent of arrays in Java; however, lists are a more abstract concept than arrays (since an array is tied to a specific storage mechanism in memory), and HasCl provides many powerful operations on lists that have no direct equivalents in Java arrays. The tradeoff for this added power over tuples is that all of the data items in a list have to be of the same type; it is not possible to mix numbers with characters or strings in a single list (Java arrays have this same restriction).
The basic way to write a list of values is to enclose
them in square brackets, separated by commas. For example,
[1, 2, 3, 4, 5]
is a list of five numbers,
starting with 1
at the head of the list. Just
as with tuples, the order matters, so [2, 5, 3, 1,
4]
is a different list, even though it contains the
same values. Since each of these values is of type
Num
, we write the type of the list as
[Num]
. There is an abbreviation for lists
which consist of a regular sequence of values: [1 ..
5]
gives the list [1, 2, 3, 4, 5]
.
As mentioned above, a String
is just a list
of Char
s. The notation "Hello"
gives exactly the same list as ['H', 'e', 'l', 'l',
'o']
. Note that a list of Strings
is
not the same; ["Hello",
"World"]
is a list with two elements, each of which
is a list of characters (coincidentally, each one is five
characters long, but recall that a given type of list can
have any number of elements). The type of ["Hello",
"World"]
is [String]
; since
String
is a synonym for [Char]
,
this can also be written [[Char]]
(a list of
lists of characters).
The fundamental operations on lists allow us to take
them apart and put them together. Given a list, we may
remove the first element with head
, and obtain
the list of all except the
first element with tail
: head([1, 2, 3,
4, 5])
is 1
, while tail([1, 2, 3,
4, 5])
is [2, 3, 4, 5]
. A new list may
be formed from a head element and a tail list with the
colon operator: for example, [1 : [2, 3, 4,
5]]
produces [1, 2, 3, 4, 5]
. An entire
list may be put together in this way, with the initial tail
list being the empty list, [ ]
. That is,
[1, 2, 3, 4, 5]
is equivalent to [1 : [2
: [3 : [4 : [5 : [ ]]]]]]
. If you ask the type of
[ ]
, the system will say [ ] ::
[a]
, which is read ``[ ]
has the type
list of a
, where a
can be any type.'' Trying to take the
head
or tail
of an empty list
produces an error (try head(tail([1]))
).
We have seen a number of other operations on lists
already. The operator ++
will append two lists
of the same type, so [1, 2] ++ [3, 4, 5]
produces [1, 2, 3, 4, 5]
. The
reverse
function produces a list with all the
same elements as its argument, but in the opposite order:
reverse("Hello")
gives "olleH"
.
The length
function counts how many elements
are in a list; if you do length([ ])
, the
answer is 0
, while length(["Hello",
"World"])
is 2
(and
length(head(["Hello", "World"]))
is
5
). Given lists of numbers, sum
and product
will add or multiply all of the
numbers together.
A more interesting operation is map
, which
takes two arguments. The first is a one-argument function
and the second is a list; map
applies the
function to each of the elements of the list and returns
the list of results. For example, map(sqrt, [1 ..
10])
produces a list of the square roots of the
numbers from 1 to 10; it is equivalent to evaluating
[sqrt(1), sqrt(2), ..., sqrt(10)]
(the
...
here is not in the syntax of HasCl; I just
didn't feel like typing all ten terms).
One more function on lists that we have seen is
zip
. When zip
is applied to a
pair of lists, it creates a list of pairs of corresponding
elements from the two lists, until one or both of the lists
is exhausted. That is, zip([1, 2, 3], ["Hello",
"World"])
produces the list [(1, "Hello"), (2,
"World")]
; the 3
is ignored, because
there was no matching element in the second list.
Lists may be compared for equality; two lists are equal if they have the same length and if corresponding elements are equal.
Question: Write a function
that tests whether a string s
is a palindrome
(that is, it reads the same forwards as backwards). For
example, isPalindrome("radar")
should return
true
, while isPalindrome("Madam, I'm
Adam")
should return false
(that is,
the spaces and punctuation matter, as does
capitalization).
As seen in the map
example above, HasCl
allows functions to be used as values and passed as
arguments to other functions. HasCl is known as a
``functional'' language, partly because of this treatment
of functions as first-class values (that is, they are
treated just like the other basic types of the language).
The type of a function which takes an argument of type
a
and produces a result of type b
is (a) -> b
, which is an ASCII
approximation of the usual mathematical notation a
b
(the
parentheses around the argument type a
are to
remind us of the parentheses around the argument in a
function call; this is similar to Java, where we say that
if f
is a function that takes an argument of
type a
and produces a result of type
b
, then the prototype for f
is
b f(a);
). To express the type of
map
, note that map
takes a
function of any type (a) -> b
, as well as a
list of type [a]
; the result, after applying
the function to each element of the list, will be of type
[b]
. Therefore, the system will inform us that
map :: ((a) -> b, [a]) -> [b]
(try
it).
Question: What is the type
of zip
?
Apart from some of the syntactic abbreviations mentioned
above (for example, string constants), there is nothing special
about the built-in types described above. HasCl has a very
powerful system for defining new types and operations. The
basis of the means of defining new types is the
data
definition, which names a new type and lists
all of the fundamental ways of constructing new values of the
type. The standard way of defining new operations is then to
give a series of rules that cover each case of how an argument
could have been constructed; since all of the constructors are
listed in the data
definition, it is usually
sufficient to provide one rule for each constructor.
A simple example is a type which is just an enumeration of
all the possible values. Consider a Direction
type, which may be North
, East
,
South
, or West
. Here is an
appropriate definition:
data Direction = North | East | South | West
This says that the only way to construct a value of type
Direction
is to give one of the four main compass
directions; these four constructors name the four values of the
type. Now suppose that we want to define a function
degrees
which converts a Direction
into the corresponding numerical compass heading, where 0o is north, 90o is east, etc. The
following set of rules will cover all the cases:
degrees(North) = 0 degrees(East) = 90 degrees(South) = 180 degrees(West) = 270
That's it. Enter these lines in a New Definition window and
compile them. Now when the system encounters an expression such
as degrees(West)
, it can evaluate it by looking at
the rules, producing the result 270
. We have just
defined a new function degrees :: (Direction) ->
Num
.
When you enter a new function definition, it is a good idea to declare the expected type of the function on the first line, followed by a descriptive comment (this is no different from the good practice of providing function signatures and comments in Java). For example, the function above could also have been entered as
degrees :: (Direction) -> Num // Convert a compass direction into numeric degrees degrees(North) = 0 ...
The type declaration provides extra documentation about the
use of the function, as well as a check that the function
really does have the desired type (Funnie will give you an
error message when compile the function if you declare the
wrong type). Incidentally, a current limitation of Funnie is
that function definitions may not be deleted, and all
definitions of a given function must have the same name. If you
define a function incorrectly and it compiles with the wrong
type, you will need to make up a new name, such as
degrees2
, for the correct function (fixing this
problem is on the list of improvements for the summer).
Another example is the type Bool
; it acts as if
it were defined as data Bool = false | true
. Here
is the definition of the not
function from the
standard library:
not :: (Bool) -> Bool // Logical negation not(false) = true not(true) = false
As you can see, it is very similar to the
Direction
type. There are exactly two values of
type Bool
, false
and
true
. The not
function has a
correspondingly simple definition, since it only has to
consider two cases for its argument. The Char
type
is also handled conceptually as an enumeration, although it has
many more cases.
Question: Define a function
rotateDirLeft :: (Direction) -> Direction
which
will take North
to West
,
East
to North
, etc.
Constructors in a data
definition may also take
arguments. For example, suppose we want a type to represent
colors. We might use the following (a slightly different type
Color
is already defined in the Graphics module in
Funnie, so I will use the British spelling here to avoid a
conflict):
data Colour = Red | Green | Blue | Yellow | Cyan | Magenta | White | Black | rgb(Num, Num, Num)
This is like an enumeration, except the last constructor can
take three Num
s to represent an arbitrary color by
giving its red, green, and blue components (each going from 0
to 255). We could define a function getRGB
of type
(Colour) -> (Integer, Integer, Integer)
which
converts any value of type Colour
into a triple of
red, green, and blue components. Here is an appropriate list of
rules:
getRGB(Red) = (255, 0, 0) getRGB(Green) = ( 0, 255, 0) getRGB(Blue) = ( 0, 0, 255) getRGB(Yellow) = (255, 255, 0) getRGB(Cyan) = ( 0, 255, 255) getRGB(Magenta) = (255, 0, 255) getRGB(White) = (255, 255, 255) getRGB(Black) = ( 0, 0, 0) getRGB(rgb(r,g,b)) = ( r, g, b)
The name for this kind of function definition by giving
rules is a ``pattern-matching'' definition. Each rule gives a
pattern that will be matched against an argument; if the match
is successful, then the rule is used; otherwise, the next rule
in the list is tried. For no-argument constructors, such as
Red
, the name of the constructor is the entire
pattern. For constructors taking arguments, the pattern is
formed by giving the constructor name followed by enough
variables to match whatever argument values come along with
that constructor. For example, if we evaluate
getRGB(rgb(64, 128, 192))
, the ninth rule will
succeed by matching r
to 64
,
g
to 128
, and b
to
192
. These variable matches, also known as bindings, are roughly equivalent to
associating actual arguments with formal parameters in calling
a function in Java; for the course of the execution of the
function, the variables will contain the values passed in from
the caller (in Java this has to be qualified to say ``unless
the variables are assigned different values in the course of
execution''; HasCl has no notion of changing the value assigned
to a variable--this is part of what makes the functions so
pure, since we don't have to worry about changing the state of
variables--so this qualification is not necessary). Therefore,
in evaluating the right-hand-side of the rule, the expression
(r, g, b)
becomes (64, 128, 192)
;
this is the result of the function.
Although they depend on some special syntax, the built-in
tuple types are an instance of this kind of data type. For
example, we may define a new type that is essentially
equivalent to the type (Bool, Char)
as
follows:
data BoolChar = BoolChar(Bool, Char)
For convenience, we may also define functions to extract
individual components from a BoolChar
value:
first :: (BoolChar) -> Bool first(BoolChar(b,c)) = b second :: (BoolChar) -> Char second(BoolChar(b,c)) = c
These mirror the built-in functions fst
and
snd
which extract the two components of a pair.
Thus, we could write an expression such as
first(BoolChar(false, 'x'))
to mirror the standard
expression fst(false, 'x')
; each evaluates to
false
.
The prelude does not provide functions analogous to
fst
and snd
for tuple types with more
values, because it is more common to extract the parts of a
tuple by pattern matching. For example, suppose we want to
write a function brightness :: (Num, Num, Num) ->
Num
which takes a triple of Num
s, as
produced by the getRGB
function above, and returns
the average of the three components. It may be defined as
follows:
brightness((r, g, b)) = (r + g + b) # 3
Evaluating brightness(getRGB(Cyan))
first
applies the getRGB
function to Cyan
,
producing the triple (0, 255, 255)
. Then it
applies the brightness
function to this result:
brightness((0, 255, 255))
. This matches the rule
for brightness
, binding 0
to
r
, 255
to g
, and
255
to b
. Finally, it plugs these
values into the right-hand-side, producing (0 + 255 +
255) # 3
, which gives 170
as the final
result.
Question: Give a direct
definition of a function colourBrightness :: Colour ->
Num
, such that colourBrightness(c)
produces
the same result as brightness(getRGB(c))
for any
Colour
value c
(but without using the
brightness
or getRGB
functions).
At this point it is a minor step to allow recursive data
types--types where a constructor may take another value of the
type being constructed as an argument. For example, here is the
definition of a type Path
, where a path is either
empty or it consists of a segment going right, left, up, or
down followed by another path:
data Path = End | R(Path) | L(Path) | U(Path) | D(Path)
An example of a value of type Path
is
R(U(R(D(End))))
, which may be drawn as
The only extra ability needed to support this is to allow a
similar recursion when defining a function--we will allow the
use of the function being defined on the right-hand-side of a
rule, usually applied to a variable that was bound to another
instance of the type when matching one of the recursive
constructors. For example, here is a rotateLeft
function on Path
s, which changes all of the path
segments to be rotated 90o
counter-clockwise:
rotateLeft(End) = End rotateLeft(R(p)) = U(rotateLeft(p)) rotateLeft(L(p)) = D(rotateLeft(p)) rotateLeft(U(p)) = L(rotateLeft(p)) rotateLeft(D(p)) = R(rotateLeft(p))
For each of the recursive constructors, which build a longer
path by adding a segment onto the beginning of another path, we
give a rule that says how to rotate the added segment, and then
we make a recursive call to rotateLeft
to rotate
the rest of the path. The base case is where the recursion
bottoms out, in this case at the empty path
End
.
The canonical example of a recursive data type is the
built-in list type. Indeed, we can frequently ``code up'' other
recursive types by representing them as lists--you should be
able to imagine using [Direction]
as a replacement
for Path
, where we might write [East, North,
East, South]
instead of
R(U(R(D(End))))
.
Question: How would you define
rotateDirListLeft :: ([Direction]) ->
[Direction]
to perform the analogous operation to
rotateLeft :: (Path) -> Path
? Try to use
functions we have already defined.
Although the syntax is not legal HasCl, you should imagine
the list type [a]
as being defined by
data [a] = [ ] | [a : [a]]
That is, a list of values of type a
is either
an empty list, [ ]
, or the result of using the
colon operator to add a value of type a
onto the
front of another list of values of type a
.
Here is an example of defining our own version of the
length
function:
len([ ]) = 0 len([x : xs]) = 1 + len(xs)
Note how the structure of the function definition exactly
follows the structure of the data
definition. To
find the length of a list with one element (x
)
added to it, we add one to the length of the shorter list,
obtained by recursively calling the len
function
on the tail (xs
). That rule, plus the base case
for the empty list, is all we need to define the function.
Question: Write a function
countVertical :: ([Direction]) -> Num
which
counts how many ``vertical'' segments (North
or
South
) are in a Direction
list. For
example, evaluating the expression
countVertical([North, East, North, South, West])
should produce 3
.
For another example, here is the definition of a
listMap
function which is equivalent to the
built-in map
function:
listMap(f, [ ]) = [ ] listMap(f, [x : xs]) = [f(x) : listMap(f, xs)]
Reading this off in words, it says that the result of
mapping a function f
over an empty list is just an
empty list, while mapping f
over a list that
starts with x
is the list with f(x)
at the head and the result of mapping f
over the
rest of the list as the tail.
Question: Define your own
version of the zip
function.
Overview | Schedule | Resources | Assignments | Home |
DePauw
University, Computer Science
Department, Spring 2005
Maintained by Brian Howard (bhoward@depauw.edu
).
Last updated