Haskell Tutorial for C Programmers - Section IVWritten by Eric Etheridge Page-Wise Table of Contents
Section IV: Haskell and YouPart I: Where Are the 'For' Loops?
'for' loops are unnecessary. Not just in Haskell, but in general. The only reason that you have ever used 'for' loops is that you had to 'do' something to a chunk of memory to store the right value in the right spot. Haskell frees you from this, and when you got lost and wonder where your 'for' loops are, check here: bar :: Int -> Int bar = ... foo :: [Int] -> [Int] foo (x:xs) = bar x : foo xs foo [] = [] That looks a little too easy, and is actually equivalent to 'foo = map bar'. Here's a less contrived example. What if you were implementing a physics simulation, gravity for example, and you needed to calculate a new position of each object based on the other objects' positions? The following function calculates part of the process, which is finding, for each object, the sum of its mass times another object's mass divided by distance, over all other objects. In C, this would be accomplished by a pair of nested for loops, the outer one reading the mass and position from an array of objects, and the inner one computing mass1 times mass2 over the distance and summing it. Here are the types for that operation in Haskell:
--types for variables
type Mass = Double --only a type rename, but useful for clarifying parameters
type Pos = (Double, Double, Double) --x, y, z
type Obj = (Mass, Pos) --interchangeable with (Double, (Double, Double, Double))
--list of functions needed
{-
Takes a list of objects.
Returns a list of (sum of mass times other object mass over distance for all objects)
Order is preserved.
-}
--overall function type
calcMassesOverDists :: [Obj] -> [Double]
That's definitely the setup. I defined some types for keeping track of the variables, listed the mathematical operations needed, and defined a type for the overall function. In the above code, '--' indicated that the rest of the line is a comment. '{-' and '-}' open and close block comments. The reason that I separate this from the code is that it is unlikely to change, while code is likely to be altered, optimized, debugged, etc. With some useful comments, here's one way to write the code: --Here we pass the objects in as two parameters to the helper function so we can iterate twice. --This does not copy the list of objects. calcMassesOverDists :: [Obj] -> [Double] calcMassesOverDists objs = calcHelper objs objs --This is a function that computes a distance between two Pos values, used in calcMMoD. distXYZ :: Pos -> Pos -> Double distXYZ (x1, y1, z1) (x2, y2, z2) = sqrt (xd * xd + yd * yd + zd * zd) where (xd, yd, zd) = (x1 - x2, y1 - y2, z1 - z2) --three assignments at once using a tuple --This iterates over the list of objects and calculates the sum for each. --It uses pattern matching to recurse and terminate. calcHelper :: [Obj] -> [Obj] -> [Double] calcHelper (obj:objs) objList = (sum (calcMMoD obj objList)) : calcHelper objs objList calcHelper [] _ = [] --This calculates the list of mass times mass over distance for a single object. --It uses pattern matching to recurse and terminate and a where clause to keep the code clear. calcMMoD :: Obj -> [Obj] -> [Double] calcMMoD obj@(m1, pos1) ((m2, pos2):rest) = safeValue : calcMMoD obj rest where dist = distXYZ pos1 pos2 safeValue = if pos1 == pos2 then 0 else m1 * m2 / dist calcMMoD _ [] = [] I threw something extra in there, specifically 'obj@' in front of '(m1, pos1)'. The '@' is read 'as', and it means that 'obj' will refer to the whole value of type 'Obj', while '(m1, pos1)' will pattern match against the values in 'obj'. It's handy, because otherwise I would have to write '(m1, pos1)' again when I called 'calcMMoD' recursively, and I might make a typo when I did. Also, it's clearer. Note also that I did not have to completely 'take apart' obj. I left the value of type 'Pos' bound to 'pos1'. And note that I put all the sub-computations for 'distXYZ' into one line to save space. I defined the tuple '(x1 - x2, y1 - y2, z1 - z2)', and then bound it to the pattern of '(xd, yd, zd)', thus defining 'xd', 'yd', and 'zd' how I needed to. Finally note that dist is not evaluated in a call to calcMMoD if pos1 == pos2, and neither is m1 * m2 / dist, which avoids the division by zero. I can compare equality between pos1 and pos2 because a tuple of types which are all in the class 'Eq' is also in the class 'Eq'. The definitions allowing that are here, although you have to scroll down about two pages: Prelude, Section: the Eq class What you're looking for is a line like this: (Eq a, Eq b) => Eq (a, b) When listed in the 'Instances' section of the Eq class, that means that somewhere in the source code for the Prelude, there is an instance of Eq defined for '(a, b)' with the condition that both a and b are also members of Eq. The definition of that instance is fairly straightforward; the point is that it is there. Because it is present, any tuples of size 2 (and also those of many larger sizes) whose items are all members of the Eq class, and those tuples can be compared using '==' and '/=' without any further work on your part. 'sqrt' is a class function, and is defined (separately) for all types in the class 'Floating', which of course includes 'Double'. The type of 'sqrt' can be found here: Prelude, Section: the Floating class 'sum' is a polymorphic function, and is defined (one time) for all types in the class 'Num', which also of course includes 'Double'. The type of 'sum' can be found here: Prelude, Section: Special Folds I could have had calcMMoD return the sum, but code will compile to a more efficient result if the tasks are broken up, since 'sum' in the prelude is based on a tail-recursive and (I believe) highly optimized function. The definition of 'sum' is in the Prelude, and more about 'tail recursion' can hopefully be found here: http://en.wikipedia.org/wiki/Tail_recursion So where are the 'for' loops? Each recursive function iterates over a list, and the two together act as a nested pair of 'for' loops. This code is good, but there is a quicker way to write 'calcMassesOverDists' and 'calcMMoD', with the same types, and using a much simpler helper function for 'calcMMod'. Here is a cleaner implementation: --Here we use 'map' instead of writing the recursion out. calcMassesOverDists :: [Obj] -> [Double] calcMassesOverDists objList = map (\obj -> sum (calcMMoD obj objList)) objList --Again, we use 'map' instead of writing the recursion out. calcMMoD :: Obj -> [Obj] -> [Double] calcMMoD obj objList = map (mMoDHelper obj) objList --Here we don't bother spacing out the code since we're not forming a list any more. --Note that this function no longer operates or returns a list. mMoDHelper :: Obj -> Obj -> Double mMoDHelper (m1, pos1) (m2, pos2) = if pos1 == pos2 then 0 else m1 * m2 / distXYZ pos1 pos2 --This is unchanged. distXYZ :: Pos -> Pos -> Double distXYZ (x1, y1, z1) (x2, y2, z2) = sqrt (xd * xd + yd * yd + zd * zd) where (xd, yd, zd) = (x1 - x2, y1 - y2, z1 - z2) I could have also avoided writing 'mMoDHelper' by using a lambda function: --Same as above. calcMassesOverDists :: [Obj] -> [Double] calcMassesOverDists objList = map (\obj -> sum (calcMMoD obj objList)) objList --The code which avoids division by zero is now included here. calcMMoD :: Obj -> [Obj] -> [Double] calcMMoD (m1, pos1) objList = map (\(m2, pos2) -> if pos1 == pos2 then 0 else m1 * m2 / distXYZ pos1 pos2) objList --This is unchanged. distXYZ :: Pos -> Pos -> Double distXYZ (x1, y1, z1) (x2, y2, z2) = sqrt (xd * xd + yd * yd + zd * zd) where (xd, yd, zd) = (x1 - x2, y1 - y2, z1 - z2) Or I could have avoided writing calcMMoD, but at that point it gets ridiculous: --Now we have nested lambda functions which avoid a function call. --Not really necessary, since no clarity is gained. calcMassesOverDists :: [Obj] -> [Double] calcMassesOverDists objList = map (\obj1@(m1, pos1) -> sum (map (\(m2, pos2) -> if pos1 == pos2 then 0 else m1 * m2 / distXYZ pos1 pos2) objList) ) objList --This is unchanged. distXYZ :: Pos -> Pos -> Double distXYZ (x1, y1, z1) (x2, y2, z2) = sqrt (xd * xd + yd * yd + zd * zd) where (xd, yd, zd) = (x1 - x2, y1 - y2, z1 - z2)
mMoDHelper obj :: Obj -> Double This in turn is suitable as a parameter to 'map', as it only takes one parameter, rather than two. Not every instance of a for loop should be turned into a 'map'. In this case, there is the Prelude function 'sum', which will take the list generated by the 'map' in calcMMoD and return the sum of its values. There is not always a pre-built function for your purposes. List functions are part of Haskell's core tools, and there are more advanced functions to use when you need them, such as 'foldr' and its variants. Learning how to use 'foldr' and 'foldl' is a rite of passage for Haskell programmers. You will learn in time, by studying their definitions (in the Prelude) and definitions of other functions defined in terms of 'foldr' and 'foldl', such as 'concat', 'or', and 'sum'. For loops were just the beginning. When you get away from sequential behavior, real power comes out. Also, keep in mind that since foldr and map are used everywhere, GHC has heavily optimized them, and functions like them, so it's a good idea to use them.
Part II: Remember Lazy Evaluation? It's Still There
data Tree a = Null | Node a (Tree a) (Tree a) This is a relatively complicated type. It is a 'data' type, defined with the reserved word 'data', like 'Maybe a' was. It is also polymorphic like 'Maybe a'; you can tell because the type, 'Tree a', takes a type variable. It has two data constructors, 'Null' and 'Node'. 'Null' has no arguments and 'Node' has three. The way it is named indicates that it is a tree, and on inspection it is a binary tree, having two children in 'Node'. So how would this work? First, let's write a value of this type: t1 :: Tree Int t1 = Node 3 (Node 2 Null Null) (Node 5 (Node 4 Null Null) Null) If we were to graph this tree, not including Null branches, it would look like this:
3
/ \
2 5
/
4
The first node has both a 'left' child and a 'right' child, and the 'right' child of the first node also has a 'left' child. Let us review 'constructors'. In this example 'Tree a' is a type, and 'Node' and 'Null' are 'data constructors' for that type. A data constructor, often simply called a constructor, acts like a function that groups together objects to form an object of a datatype. They only exist for types defined using 'data' or 'newtype'. Note that they are different from type constructors, such as IO and Maybe. Data constructors act like functions, and do not belong in type signatures. Type constructors act like functions on types, and only belong in type signatures. They do not live in the same namespace, so often a 'data' type will have a data constructor of the same name out of convenience. Constructors are also used to 'deconstruct' objects of 'data' types, like so: inOrderList :: Tree a -> [a] inOrderList Null = [] inOrderList (Node item left right) = inOrderList left ++ [item] ++ inOrderList right 'inOrderList' uses pattern matching to determine which constructor its parameter uses. Further, it 'deconstructs' a value that uses the constructor 'Node' and binds its member values to the variables 'item', 'left', and 'right', which are of types 'a', 'Tree a', and 'Tree a', respectively. We know these types because Node's definition reads, "Node a (Tree a) (Tree a)", and 'a' is not further specified in this example. For those of you unfamiliar with trees, 't1' above is a 'binary search tree', and evaluating 'inOrderList t' will result in the following: *Main> inOrderList t1 [2,3,4,5] *Main> Those values are in ascending order, since that is the definition of a 'binary search tree'. Read up on them if you're not familiar with them already. There's another funny thing about the definition of 'Tree a'. It's recursive. It used 'Tree a' to define each child. You can do that in Haskell as well as C, but as usual, there's a twist, and again as usual it involves lazy evaluation. In C/C++, to use a type in its own definition, you must declare a pointer to an object of its type rather than including it directly. In Haskell, pointers aren't used like that, so the type is included directly, as in the tree example. So what about this definition: foo :: Int -> Tree Int foo n = Node n (foo (n - 1)) (foo (n + 1)) t2 = foo 0 What is the value of 't2'? And what is its type? The value of 't2' requires an infinite amount of space to store. The first few levels of the trees could be drawn like this:
0
/ \
-1 1
/ \ / \
-2 0 0 2
/ \ / \ / \ / \
And so on. But the type of 't2' is simple, and should be clear from the type of 'foo': t2 :: Tree Int When you get an error message (not if ever, but when you get an error message) that says "can't do such-and-such, unification would result in infinite type", it means that the type would require an infinite amount of space to store. Typically this happens with pattern matching on lists. In that case a careful check will show that something incorrect in the code would have resulted in nested lists infinitely deep, meaning a type that looks like this: [[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[.... And so on. But back to 't2'. Its type is not infinite, even though its type is defined recursively and t2 has a value that, when evaluated, would require infinite space to store. Because its type is defined recursively, Haskell (and you) know that values of type 'Tree a' can contain other values of type 'Tree a'. The fact that each value of type Tree a which is 'in' t2 uses the constructor 'Node' is not stored in the type of t2, so the type of t2 is finite and Haskell can use it. Also, multiple values of type 'Tree Int' can exist, some infinite, some not, and they all have the same type. Okay?
Part III: The Point(s)
data Forever a = AThing a (Forever a) It is a polymorphic type, it has a single constructor 'AThing', and it is recursive. Values of this type will always be infinite if fully evaluated. That's okay, and you could use this in a program if you wanted to. Haskell would not attempt to fully evaluate an object of this type unless you told it to. The second point is that learning and using Haskell requires unlearning and rethinking the basic assumptions most coders have developed about programming. Unlike so many languages, Haskell is not 'a little different', and will not 'take a little time'. It is very different and you cannot simply pick it up, although I hope that this tutorial will help. If you play around with Haskell, do not merely write toy programs. Simple problems will not take advantage of Haskell's power. Its power shines mostly clearly when you use it to attack difficult tasks. Once Haskell's syntax is familiar to you, write programs that you would ordinarily think of as too complicated. For instance, implement graph-spanning algorithms and balanced-tree data types. At first, you'll probably trudge ahead using 'imperative thought processes'. As you work, you'll hopefully see that Haskell's tools let you dramatically simplify your code. A big tip is, "Don't use arrays." Most of the time, you need to access members of a list one at a time, in order. If that is the case, you do not need an array, and it would take you a lot of work to set one up. Use a list. If you are truly storing data that needs random access, still don't use arrays. Use lists and '!!'. When you need speed, then use arrays. Use Arrays, and then switch to IOArrays. But only use them if you actually need speed. Your class projects absolutely will not need arrays unless you are writing a game, or working on something for at least three months. Then, you might need fast random-access data. Maybe. Use lists. The tutorial has been expanded to include section six after the commentary, with examples. Additionally, all examples from these sections are included in source files as well. Hopefully, these will show how Haskell implementations differ from imperative code. Check them out and compare them to your own Haskell programs. My style is not perfect, but I know some good techniques. As a general rule, shorter, more concise source code makes programming and debugging faster. If you find yourself writing extensive cases or repeated code, that's probably unnecessary in Haskell.
Continue to Section V: Final Commentary
|