summaryrefslogtreecommitdiff log msg author committer range
 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 ``` ``````You'll want to look over the [Haskell Tutorial for C Programmers](http://www.haskell.org/~pairwise/intro/intro.html) and some of the other tutorials that are linked from that one, but here are some basic concepts. This declares a function named double that takes a numeric argument and returns that argument times 2: double x = x * 2 This expression is an anonymous function that takes a numeric argument and returns that argument times 2. This kind of thing is apparently called a "section". (* 2) So you can use double and (\* 2) interchangeably. In fact, you can define double using (\* 2): double = (* 2) Most of the time, a list can be written like so: [1, 2] However, this is syntactic sugar for the following expression. 1 : 2 : [] The value [] is the empty list, and the operator ':' is called "cons" -- it takes a value on the left and a list of values on the right, and returns a new list resulting from sticking the two things together. The list concatenation operator is '++': [1,2] ++ [3,4] == [1,2,3,4] Haskell provides a convenient notation for lists of particular patterns. [1 .. 6] == [1, 2, 3, 4, 5, 6] [1,3..6] == [1, 3, 5] This notation includes infinite lists: [1..] == [1, 2, 3, 4, ... [1,3..] == [1, 3, 5, 7, ... It's often useful to look at the first several values in a list, especially when working with infinite lists. You can use the _take_ function for this: take 5 [1..] == [1..5] Higher-order functions are those that accept functions as parameters. One standard example is map: map (* 2) [1, 2, 3] == [2, 4, 6] map (* 2) [1..] == [2, 4..] (Your computer can't check that second example, because it will run forever. An inductive proof using the definition of map is left as an exercise for the reader.) You can write the list of all positive integers yourself, recursively: nat = 1 : map (+ 1) nat This is a common enough way of defining lists: identify a base element, and a function from one element of the set to another; then map the function across the list that you're defining. Function declaration allows you to pattern-match on the function's arguments. Here's a function that works like map, except it only affects the first element of the list. (We call that element the "head".) mapHead f [] = [] mapHead f (x:xs) = (f x) : xs So: mapHead (* 5) [1, 2, 3] == [5, 2, 3] Functions can be used like infix operators by surrounding the function name with back-quotes. 10 `mod` 4 == 2 But you can also define your own infix operators, and you can use all sorts of symbols for names: a <-~/ b = if a < b then a `div` 2 else (a `div` 2) <-~/ (b * 2) map (<-~/ 2) [1..30] # Exercises Here are a few exercises, with [[solutions|/HaskellProgramming/Solutions.hs]]. They illustrate lazy evaluation (including infinite data structures), higher-order functions, parametric polymorphism, pattern matching, sections, and some common list manipulation tools. As you do these exercises, think about how you'd perform the same tasks in an imperative language like C, C++, or Java. 1) The quicksort algorithm goes like this: given a list to sort, select and remove a "pivot element". Partition the remaining list into those elements that are less than the pivot, and those that are greater/equal. Recursively sort the two partitions. Your sorted list is: the sorted "less-than" partition, then the pivot element, then the sorted other partition. The recursive base case is that the empty list is already sorted. Write a function "quicksort" that implements this algorithm. The "List" module provides a function called partition that you may find helpful. 2) Two sorted lists with no duplicates can be merged into a combined list that's still sorted and still has no duplicates, in O(n) time. Implement an operator named ~~ that does this. 3) The "Hamming numbers" are those numbers that can be written as 2^i * 3^j * 5^k where i, j, and k are non-negative integers. You can define the list of all Hamming numbers by making these observations. - 1 is obviously in the list (when i, j, and k are 0). - If you multiply any element in the list by 2, the result is another element in the list; similarly for 3 and 5. Write a value "hamming" that is an infinite list containing all the Hamming numbers. If your solution produces the list in sorted order, then this expression will be True: take 9 hamming == [1,2,3,4,5,6,8,9,10] Try evaluating hamming !! 100000 and see how long it takes. Then evaluate it again -- it should respond instantly. If the first time wasn't noticeably slow, try adding a 0. :-) Beware: If your solution attempts to concatenate an infinite list with another list, your code probably won't work. Testing whether this list: [1..] ++ [0] contains 0, for example, will never halt -- so effectively it does not contain 0. 4) Consider this data type declaration for trees: data Tree a = Tip | Branch (Tree a) a (Tree a) Write a function "inorder" that returns a list of "a"s resulting from an in-order traversal of such a tree. 5) Write a function "treeEqual" that tests whether two trees have the same elements, in the same order, regardless of whether the trees have the same structure. For example, this should be True: (Branch (Branch (Branch Tip 1 Tip) 2 Tip) 3 Tip) `treeEqual` (Branch Tip 1 (Branch Tip 2 (Branch Tip 3 Tip))) # Resources - [Haskell Tutorial for C Programmers](http://www.haskell.org/~pairwise/intro/intro.html) - The Haskell [Prelude](http://www.cs.uu.nl/~afie/haskell/tourofprelude.html) has a wealth of well-written Haskell code. - The newsgroup is relatively active. - PSAS has a small [module](http://svn.psas.pdx.edu/trunk/haskell/) of Haskell code for parsing CAN packets. - Many other resources are linked from the [main Haskell web site](http://www.haskell.org/). ``````