Programming with HasCl

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.HasCl.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.

Interacting with Funnie

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]) [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.

Basic Types

Num

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 C++, 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 Nums: +, -, *, 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 C++). Exponentiation, which is not a built-in operator in C++, is written with the caret operator, ^; that is, a^b 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?

Bool

The type Bool represents truth conditions, either true or false. It is essentially equivalent to the bool type of C++. 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 x and y are expressions of 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 a function named myAnd which takes two arguments, x and y. Just 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.

Char

The HasCl type Char can represent any single character. It is essentially identical to the char type in C++, 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 C++: '\''. 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 C++, 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').

String

As with many other parts of the HasCl language, the syntax for strings is essentially the same as in C++. That is, a string constant is a sequence of characters surrounded by double-quotes: "Like this". The same escape codes as 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)".

Pairs and Tuples

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).

Lists

Tuples can hold a variety of types of values; they are roughly analogous to structs in C++ (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 C++; 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 C++ arrays. The tradeoff for this added power 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.

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 Chars. 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 : []]]]]]. Instead of the colon syntax, the head and tail of a string may be indicated with a tilde (~) separating them, so "Hello" is short for "H" ~ "e" ~ "l" ~ "l" ~ "o" ~ "". 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).

Functions

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 $\rightarrow$ 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 C++, 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?