text:
Yet Another Haskell Tutorial/Modules

In Haskell, program subcomponents are divided into modules. Each module sits in its own file and the name of the module should match the name of the file (without the ".hs" extension, of course), if you wish to ever use that module in a larger program.

For instance, suppose I am writing a game of poker. I may wish to have a separate module called "Cards" to handle the generation of cards, the shuffling and the dealing functions, and then use this "Cards" module in my "Poker" modules. That way, if I ever go back and want to write a blackjack program, I don't have to rewrite all the code for the cards; I can simply import the old "Cards" module.

Exports
Suppose as suggested we are writing a cards module. I have left out the implementation details, but suppose the skeleton of our module looks something like this:

module Cards where

data Card = ... data Deck = ...

newDeck :: ... -> Deck newDeck = ...

shuffle :: ... -> Deck -> Deck shuffle = ...

-- 'deal deck n' deals 'n' cards from 'deck' deal :: Deck -> Int -> [Card] deal deck n = dealHelper deck n []

dealHelper = ... In this code, the function  calls a helper function . The implementation of this  helper function is very dependent on the exact data structures you used for  and so we don't want other people to be able to call this function. In order to do this, we create an export list, which we insert just after the module name declaration:

module Cards ( Card,              Deck,               newDeck,               shuffle,               deal             ) where

... Here, we have specified exactly what functions the module exports, so people who use this module won't be able to access our function. The  after   and   specify that we are exporting the type but none of the constructors. For instance if our definition of  were:

data Card = Card Suit Face data Suit = Hearts | Spades | Diamonds | Clubs data Face = Jack | Queen | King | Ace | Number Int Then users of our module would be able to use things of type , but wouldn't be able to construct their own s and wouldn't be able to extract any of the suit/face information stored in them.

If we wanted users of our module to be able to access all of this information, we would have to specify it in the export list:

module Cards ( Card(Card),              Suit(Hearts,Spades,Diamonds,Clubs),               Face(Jack,Queen,King,Ace,Number),               ...             ) where

... This can get frustrating if you're exporting datatypes with many constructors, so if you want to export them all, you can simply write , as in:

module Cards ( Card(..),              Suit(..),               Face(..),               ...             ) where

... And this will automatically export all the constructors.

Imports
There are a few idiosyncrasies in the module import system, but as long as you stay away from the corner cases, you should be fine. Suppose, as before, you wrote a module called "Cards" which you saved in the file "Cards.hs". You are now writing your poker module and you want to import all the definitions from the "Cards" module. To do this, all you need to do is write:

module Poker where

import Cards This will enable you to use any of the functions, types and constructors exported by the module "Cards". You may refer to them simply by their name in the "Cards" module (as, for instance, ), or you may refer to them explicitly as imported from "Cards" (as, for instance, ). It may be the case that two modules export functions or types of the same name. In these cases, you can import one of the modules qualified which means that you would no longer be able to simply use the  format but must use the longer  format, to remove ambiguity. If you wanted to import "Cards" in this qualified form, you would write:

import qualified Cards Another way to avoid problems with overlapping function definitions is to import only certain functions from modules. Suppose we knew the only function from "Cards" that we wanted was, we could import only this function by writing:

import Cards (newDeck) On the other hand, suppose we knew that that the  function overlapped with another module, but that we didn't need the "Cards" version of that function. We could hide the definition of and import everything else by writing:

import Cards hiding (deal) Finally, suppose we want to import "Cards" as a qualified module, but don't want to have to type  out all the time and would rather just type, for instance,  -- we could do this using the as keyword:

import qualified Cards as C These options can be mixed and matched -- you can give explicit import lists on qualified/as imports, for instance.

Hierarchical Imports
Though technically not part of the Haskell 98 standard, most Haskell compilers support hierarchical imports. This was designed to get rid of clutter in the directories in which modules are stored. Hierarchical imports allow you to specify (to a certain degree) where in the directory structure a module exists. For instance, if you have a "haskell" directory on your computer and this directory is in your compiler's path (see your compiler notes for how to set this; in GHC it's "-i", in Hugs it's "-P"), then you can specify module locations in subdirectories to that directory.

Suppose instead of saving the "Cards" module in your general haskell directory, you created a directory specifically for it called "Cards". The full path of the Cards.hs file is then haskell/Cards/Cards.hs (or, for Windows haskell\Cards\Cards.hs). If you then change the name of the Cards module to "Cards.Cards", as in: module Cards.Cards(...) where

... You could then import it in any module, regardless of this module's directory, as:

import Cards.Cards If you start importing these module qualified, I highly recommend using the as keyword to shorten the names, so you can write:

import qualified Cards.Cards as Cards

... Cards.newDeck ... instead of:

import qualified Cards.Cards

... Cards.Cards.newDeck ... which tends to get ugly.

Literate Versus Non-Literate
The idea of literate programming is a relatively simple one, but took quite a while to become popularized. When we think about programming, we think about the code being the default mode of entry and comments being secondary. That is, we write code without any special annotation, but comments are annotated with either  or .  Literate programming swaps these preconceptions.

There are two types of literate programs in Haskell; the first uses so-called Bird-scripts and the second uses LaTeX-style markup. Each will be discussed individually. No matter which you use, literate scripts must have the extension  instead of   to tell the compiler that the program is written in a literate style.

Bird-scripts
In a Bird-style literate program, comments are default and code is introduced with a leading greater-than sign (" "). Everything else remains the same. For example, our Hello World program would be written in Bird-style as:

This is a simple (literate!) Hello World program.

> module Main >    where

All our main function does is print a string:

> main = putStrLn "Hello World" Note that the spaces between the lines of code and the "comments" are necessary (your compiler will probably complain if you are missing them). When compiled or loaded in an interpreter, this program will have exactly the same properties as the non-literate version from the section on Files.

LaTeX-scripts
LaTeX is a text-markup language very popular in the academic community for publishing. If you are unfamiliar with LaTeX, you may not find this section terribly useful.

Again, a literate Hello World program written in LaTeX-style would look like:

This is another simple (literate!) Hello World program.

\begin{code} module Main where \end{code}

All our main function does is print a string:

\begin{code} main = putStrLn "Hello World" \end{code} In LaTeX-style scripts, the blank lines are not necessary.

title: Yet Another Haskell Tutorial/Modules


text:
Yet Another Haskell Tutorial/Language advanced

Sections and Infix Operators
We've already seen how to double the values of elements in a list using :

However, there is a more concise way to write this:

This type of thing can be done for any infix function:

You might be tempted to try to subtract values from elements in a list by mapping  across a list. This won't work, though, because while the  in   is parsed as the standard plus operator (as there is no ambiguity), the  in   is interpreted as the unary minus, not the binary minus. Thus  here is the number $$-2$$, not the function $$\lambda x. x-2$$.

In general, these are called sections. For binary infix operators (like ), we can cause the function to become prefix by enclosing it in parentheses. For example:

Additionally, we can provide either of its argument to make a section. For example:

Non-infix functions can be made infix by enclosing them in backquotes ("\`"). For example:

Local Declarations
Recall back from the section on Functions, there are many computations which require using the result of the same computation in multiple places in a function. There, we considered the function for computing the roots of a quadratic polynomial:

roots a b c = ((-b + sqrt(b*b - 4*a*c)) / (2*a),    (-b - sqrt(b*b - 4*a*c)) / (2*a)) In addition to the let bindings introduced there, we can do this using a where clause. clauses come immediately after function definitions and introduce a new level of layout (see the section on Layout). We write this as:

roots a b c = ((-b + det) / (2*a), (-b - det) / (2*a)) where det = sqrt(b*b-4*a*c)

Any values defined in a where clause shadow any other values with the same name. For instance, if we had the following code block:

det = "Hello World"

roots a b c = ((-b + det) / (2*a), (-b - det) / (2*a)) where det = sqrt(b*b-4*a*c)

f _ = det The value of  doesn't notice the top-level declaration of, since it is shadowed by the local definition (the fact that the types don't match doesn't matter either). Furthermore, since cannot "see inside" of, the only thing it knows about  is what is available at the top level, which is the string "Hello World."

We could also pull out the computation and get the following code:

roots a b c = ((-b + det) / (a2), (-b - det) / (a2)) where det = sqrt(b*b-4*a*c) a2 = 2*a Sub-expressions in where clauses must come after function definitions. Sometimes it is more convenient to put the local definitions before the actual expression of the function. This can be done by using let/in clauses. We have already seen let clauses; where clauses are virtually identical to their <tt>let</tt> clause cousins except for their placement. The same function can be written using <tt>let</tt> as:

roots a b c = let det = sqrt (b*b - 4*a*c) a2 = 2*a in ((-b + det) / a2, (-b - det) / a2) Using a <tt>where</tt> clause, it looks like:

roots a b c = ((-b + det) / a2, (-b - det) / a2) where det = sqrt (b*b - 4*a*c) a2 = 2*a These two types of clauses can be mixed (i.e., you can write a function which has both a <tt>let</tt> cause and a <tt>where</tt> clause). This is strongly advised against, as it tends to make code difficult to read. However, if you choose to do it, values in the <tt>let</tt> clause shadow those in the <tt>where</tt> clause. So if you define the function:

f x = let y = x+1 in y    where y = x+2 The value of  is , not. Of course, I plead with you to never ever write code that looks like this. No one should have to remember this rule and by shadowing <tt>where</tt>-defined values in a <tt>let</tt> clause only makes your code difficult to understand.

In general, whether you should use <tt>let</tt> clauses or <tt>where</tt> clauses is largely a matter of personal preference. Usually, the names you give to the subexpressions should be sufficiently expressive that without reading their definitions any reader of your code should be able to figure out what they do. In this case, <tt>where</tt> clauses are probably more desirable because they allow the reader to see immediately what a function does. However, in real life, values are often given cryptic names.

Partial Application
Partial application is when you take a function which takes $$n$$ arguments and you supply it with $$<n$$ of them. When discussing Sections, we saw a form of "partial application" in which functions like  were partially applied. For instance, in the expression, the section  is a partial application of. This is because really takes two arguments, but we've only given it one.

Partial application is very common in function definitions and sometimes goes by the name "η (eta) reduction". For instance, suppose we are writing a function  which converts a whole string into lower case. We could write this as:

lcaseString s = map toLower s Here, there is no partial application (though you could argue that applying no arguments to  could be considered partial application). However, we notice that the application of occurs at the end of both   and of. In fact, we can remove it by performing eta reduction, to get:

lcaseString = map toLower Now, we have a partial application of : it expects a function and a list, but we've only given it the function.

This all is related to the type of, which is  , when all parentheses are included. In our case, is of type. Thus, if we supply this function to, we get a function of type  , as desired.

Now, consider the task of converting a string to lowercase and removing all non letter characters. We might write this as:

lcaseLetters s = map toLower (filter isAlpha s) But note that we can actually write this in terms of function composition:

lcaseLetters s = (map toLower . filter isAlpha) s And again, we're left with an eta reducible function:

lcaseLetters = map toLower. filter isAlpha Writing functions in this style is very common among advanced Haskell users. In fact it has a name: point-free programming (not to be confused with pointless programming). It is called point free because in the original definition of, we can think of the value  as a point on which the function is operating. By removing the point from the function definition, we have a point-free function.

A function similar to  is .  Whereas   is function composition,  is function application. The definition of  from the Prelude is very simple:

f $ x = f x

However, this function is given very low fixity, which means that it can be used to replace parentheses. For instance, we might write a function:

foo x y = bar y (baz (fluff (ork x))) However, using the function application function, we can rewrite this as:

foo x y = bar y $ baz $ fluff $ ork x

This moderately resembles the function composition syntax. The function is also useful when combined with other infix functions. For instance, we cannot write:

because this is interpreted as , which makes no sense. However, we can fix this by writing instead:

Which works fine.

Consider now the task of extracting from a list of tuples all the ones whose first component is greater than zero. One way to write this would be:

fstGt0 l = filter (\ (a,b) -> a>0) l We can first apply eta reduction to the whole function, yielding:

fstGt0 = filter (\ (a,b) -> a>0) Now, we can rewrite the lambda function to use the  function instead of the pattern matching:

fstGt0 = filter (\x -> fst x > 0) Now, we can use function composition between  and   to get:

fstGt0 = filter (\x -> ((>0). fst) x) And finally we can eta reduce:

fstGt0 = filter ((>0).fst) This definition is simultaneously shorter and easier to understand than the original. We can clearly see exactly what it is doing: we're filtering a list by checking whether something is greater than zero. What are we checking? The  element.

While converting to point free style often results in clearer code, this is of course not always the case. For instance, converting the following map to point free style yields something nearly uninterpretable:

foo = map (\x -> sqrt (3+4*(x^2))) foo = map (sqrt . (3+) . (4*) . (^2)) There are a handful of combinators defined in the Prelude which are useful for point free programming:

 * takes a function of type  and converts it into a function of type  .  This is useful, for example, when mapping across a list of pairs:

 * is the opposite of  and takes a function of type   and produces a function of type.

 * reverse the order of the first two arguments to a function. That is, it takes a function of type   and produces a function of type  .  For instance, we can sort a list in reverse order by using  :

This is the same as saying:

only shorter.

Of course, not all functions can be written in point free style. For instance:

square x = x*x Cannot be written in point free style, without some other combinators. For instance, if we can define other functions, we can write:

pair x = (x,x) square = uncurry (*). pair But in this case, this is not terribly useful.

Pattern Matching
Pattern matching is one of the most powerful features of Haskell (and most functional programming languages). It is most commonly used in conjunction with <tt>case</tt> expressions, which we have already seen in the section on Functions. Let's return to our example from the section on Datatypes. I'll repeat the definition we already had for the datatype:

data Color = Red | Orange | Yellow | Green | Blue | Purple | White | Black | Custom Int Int Int -- R G B components deriving (Show,Eq) We then want to write a function that will convert between something of type  and a triple of  s, which correspond to the RGB values, respectively. Specifically, if we see a  which is, we want to return  , since this is the RGB value for red. So we write that (remember that piecewise function definitions are just <tt>case</tt> statements):

colorToRGB Red = (255,0,0) If we see a  which is , we want to return ; and if we see, we want to return , and so on. Finally, if we see a custom color, which is comprised of three components, we want to make a triple out of these, so we write:

colorToRGB Orange = (255,128,0) colorToRGB Yellow = (255,255,0) colorToRGB Green = (0,255,0) colorToRGB Blue  = (0,0,255) colorToRGB Purple = (255,0,255) colorToRGB White = (255,255,255) colorToRGB Black = (0,0,0) colorToRGB (Custom r g b) = (r,g,b) Then, in our interpreter, if we type:

What is happening is this: we create a value, call it $$x$$, which has value. We then apply this to. We check to see if we can "match" $$x$$ against. This match fails because according to the definition of {Color},   is not equal to. We continue down the definitions of and try to match   against. This fails, too. We the try to match  against  , which succeeds, so we use this function definition, which simply returns the value, as expected.

Suppose instead, we used a custom color:

We apply the same matching process, failing on all values from to. We then get to try to match  against. We can see that the  part matches, so then we go see if the subelements match. In the matching, the variables,   and   are essentially wild cards, so there is no trouble matching   with 50,   with 200 and with 100. As a "side-effect" of this matching,  gets the value 50,  gets the value 200 and   gets the value 100. So the entire match succeeded and we look at the definition of this part of the function and bundle up the triple using the matched values of,   and.

We can also write a function to check to see if a  is a custom color or not:

isCustomColor (Custom _ _ _) = True isCustomColor _ = False

When we apply a value to  it tries to match that value against. This match will succeed if the value is  for any ,   and. The (underscore) character is a "wildcard" and will match anything, but will not do the binding that would happen if you put a variable name there. If this match succeeds, the function returns ; however, if this match fails, it goes on to the next line, which will match anything and then return.

For some reason we might want to define a function which tells us whether a given color is "bright" or not, where my definition of "bright" is that one of its RGB components is equal to 255 (admittedly an arbitrary definition, but it's simply an example). We could define this function as:

isBright = isBright'. colorToRGB where isBright' (255,_,_) = True isBright' (_,255,_) = True isBright' (_,_,255) = True isBright' _        = False Let's dwell on this definition for a second. The function is the composition of our previously defined function and a helper function, which tells us if a given RGB value is bright or not. We could replace the first line here with  but there is no need to explicitly write the parameter here, so we don't.  Again, this function composition style of programming takes some getting used to, so I will try to use it frequently in this tutorial.

The  helper function takes the RGB triple produced by .  It first tries to match it against which succeeds if the value has 255 in its first position. If this match succeeds,  returns   and so does . The second and third line of definition check for 255 in the second and third position in the triple, respectively. The fourth line, the fallthrough, matches everything else and reports it as not bright.

We might want to also write a function to convert between RGB triples and s.  We could simply stick everything in a  constructor, but this would defeat the purpose; we want to use the slot only for values which don't match the predefined colors. However, we don't want to allow the user to construct custom colors like (600,-40,99) since these are invalid RGB values. We could throw an error if such a value is given, but this can be difficult to deal with. Instead, we use the  datatype. This is defined (in the Prelude) as:

data Maybe a = Nothing | Just a The way we use this is as follows: our  function returns a value of type. If the RGB value passed to our function is invalid, we return, which corresponds to a failure. If, on the other hand, the RGB value is valid, we create the appropriate  value and return that. The code to do this is:

rgbToColor 255  0   0 = Just Red rgbToColor 255 128  0 = Just Orange rgbToColor 255 255  0 = Just Yellow rgbToColor  0 255   0 = Just Green rgbToColor  0   0 255 = Just Blue rgbToColor 255  0 255 = Just Purple rgbToColor 255 255 255 = Just White rgbToColor  0   0   0 = Just Black rgbToColor  r   g   b = if 0 <= r && r <= 255 && 0 <= g && g <= 255 && 0 <= b && b <= 255 then Just (Custom r g b)     else Nothing   -- invalid RGB value The first eight lines match the RGB arguments against the predefined values and, if they match,  returns   the appropriate color. If none of these matches, the last definition of matches the first argument against , the second against  and the third against   (which causes the side-effect of binding these values). It then checks to see if these values are valid (each is greater than or equal to zero and less than or equal to 255). If so, it returns ; if not, it returns  corresponding to an invalid color.

Using this, we can write a function that checks to see if a right RGB value is valid:

rgbIsValid r g b = rgbIsValid' (rgbToColor r g b)   where rgbIsValid' (Just _) = True rgbIsValid' _       = False Here, we compose the helper function  with our function. The helper function checks to see if the value returned by  is   anything (the wildcard). If so, it returns. If not, it matches anything and returns.

Pattern matching isn't magic, though. You can only match against datatypes; you cannot match against functions. For instance, the following is invalid:

f x = x + 1

g (f x) = x Even though the intended meaning of  is clear (i.e.,  ), the compiler doesn't know in general that   has an inverse function, so it can't perform matches like this.

Guards
Guards can be thought of as an extension to the pattern matching facility. They enable you to allow piecewise function definitions to be taken according to arbitrary boolean expressions. Guards appear after all arguments to a function but before the equals sign, and are begun with a vertical bar. We could use guards to write a simple function which returns a string telling you the result of comparing two elements:

comparison x y | x < y = "The first is less" | x > y = "The second is less" | otherwise = "They are equal" You can read the vertical bar as "such that." So we say that the value of  "such that" x is less than y is "The first is less." The value such that x is greater than y is "The second is less" and the value <tt>otherwise</tt> is "They are equal". The keyword  is simply defined to be equal to  and thus matches anything that falls through that far. So, we can see that this works:

Guards are applied in conjunction with pattern matching. When a pattern matches, all of its guards are tried, consecutively, until one matches. If none match, then pattern matching continues with the next pattern.

One nicety about guards is that <tt>where</tt> clauses are common to all guards. So another possible definition for our  function from the previous section would be:

isBright2 c | r == 255 = True | g == 255 = True | b == 255 = True | otherwise = False where (r,g,b) = colorToRGB c The function is equivalent to the previous version, but performs its calculation slightly differently. It takes a color,, and applies  to it, yielding an RGB triple which is matched (using pattern matching!) against. This match succeeds and the values,   and   are bound to their respective values. The first guard checks to see if  is 255 and, if so, returns true. The second and third guard check  and against 255, respectively and return true if they match. The last guard fires as a last resort and returns.

Instance Declarations
In order to declare a type to be an instance of a class, you need to provide an instance declaration for it. Most classes provide what's called a "minimal complete definition." This means the functions which must be implemented for this class in order for its definition to be satisfied. Once you've written these functions for your type, you can declare it an instance of the class.

The <tt>Eq</tt> Class
The  class has two members (i.e., two functions):

(==) :: Eq a => a -> a -> Bool (/=) :: Eq a => a -> a -> Bool The first of these type signatures reads that the function  is a function which takes two  s which are members of   and produces a. The type signature of  (not equal) is identical. A minimal complete definition for the  class requires that either one of these functions be defined (if you define, then  is defined automatically by negating the result of  , and vice versa). These declarations must be provided inside the instance declaration.

This is best demonstrated by example. Suppose we have our color example, repeated here for convenience:

data Color = Red | Orange | Yellow | Green | Blue | Purple | White | Black | Custom Int Int Int -- R G B components We can define  to be an instance of   by the following declaration:

instance Eq Color where Red == Red = True Orange == Orange = True Yellow == Yellow = True Green == Green = True Blue == Blue = True Purple == Purple = True White == White = True Black == Black = True (Custom r g b) == (Custom r' g' b') = r == r' && g == g' && b == b'   _ == _ = False The first line here begins with the keyword <tt>instance</tt> telling the compiler that we're making an instance declaration. It then specifies the class,, and the type,   which is going to be an instance of this class. Following that, there's the <tt>where</tt> keyword. Finally there's the method declaration.

The first eight lines of the method declaration are basically identical. The first one, for instance, says that the value of the expression  is equal to. Lines two through eight are identical. The declaration for custom colors is a bit different. We pattern match  on both sides of. On the left hand side, we bind,   and   to the components, respectively. On the right hand side, we bind , and  to the components. We then say that these two custom colors are equal precisely when,   and are all equal. The fallthrough says that any pair we haven't previously declared as equal are unequal.

The <tt>Show</tt> Class
The  class is used to display arbitrary values as strings. This class has three methods:

show :: Show a => a -> String showsPrec :: Show a => Int -> a -> String -> String showList :: Show a => [a] -> String -> String A minimal complete definition is either  or  (we will talk about   later -- it's in there for efficiency reasons). We can define our  datatype to be an instance of   with the following instance declaration:

instance Show Color where show Red = "Red" show Orange = "Orange" show Yellow = "Yellow" show Green = "Green" show Blue = "Blue" show Purple = "Purple" show White = "White" show Black = "Black" show (Custom r g b) = "Custom " ++ show r ++ " " ++ show g ++ " " ++ show b This declaration specifies exactly how to convert values of type to s.  Again, the first eight lines are identical and simply take a  and produce a string. The last line for handling custom colors matches out the RGB components and creates a string by concatenating the result of ing the components individually (with spaces in between and "Custom" at the beginning).

Other Important Classes
There are a few other important classes which I will mention briefly because either they are commonly used or because we will be using them shortly. I won't provide example instance declarations; how you can do this should be clear by now.

The <tt>Ord</tt> Class
The ordering class, the functions are:

compare :: Ord a => a -> a -> Ordering (<=) :: Ord a => a -> a -> Bool (>) :: Ord a => a -> a -> Bool (>=) :: Ord a => a -> a -> Bool (<) :: Ord a => a -> a -> Bool min :: Ord a => a -> a -> a max :: Ord a => a -> a -> a Almost any of the functions alone is a minimal complete definition; it is recommended that you implement  if you implement only one, though. This function returns a value of type which is defined as:

data Ordering = LT | EQ | GT So, for instance, we get:

In order to declare a type to be an instance of  you must already have declared it an instance of  (in other words,  is a subclass of   -- more about this in the section on Classes).

The <tt>Enum</tt> Class
The  class is for enumerated types; that is, for types where each element has a successor and a predecessor. Its methods are:

pred :: Enum a => a -> a succ :: Enum a => a -> a toEnum :: Enum a => Int -> a fromEnum :: Enum a => a -> Int enumFrom :: Enum a => a -> [a] enumFromThen :: Enum a => a -> a -> [a] enumFromTo :: Enum a => a -> a -> [a] enumFromThenTo :: Enum a => a -> a -> a -> [a] The minimal complete definition contains both  and , which converts from and to s.  The and  functions give the predecessor and successor, respectively. The  functions enumerate lists of elements. For instance,  lists all elements after  ; lists all elements starting at  in steps of size. The  functions end the enumeration at the given element.

The <tt>Num</tt> Class
The  class provides the standard arithmetic operations:

(-) :: Num a => a -> a -> a (*) :: Num a => a -> a -> a (+) :: Num a => a -> a -> a negate :: Num a => a -> a signum :: Num a => a -> a abs :: Num a => a -> a fromInteger :: Num a => Integer -> a All of these are obvious except for perhaps  which is the unary minus. That is,  means $$-x$$.

The <tt>Read</tt> Class
The  class is the opposite of the   class. It is a way to take a string and read in from it a value of arbitrary type. The methods for  are:

readsPrec :: Read a => Int -> String -> [(a, String)] readList :: String -> [([a], String)] The minimal complete definition is. The most important function related to this is, which uses   as:

read s = fst (head (readsPrec 0 s)) This will fail if parsing the string fails. You could define a function as:

maybeRead s = case readsPrec 0 s of     [(a,_)] -> Just a      _ -> Nothing How to write and use  directly will be discussed further in the examples.

Class Contexts
Suppose we are defining the  datatype from scratch. The definition would be something like:

data Maybe a = Nothing | Just a Now, when we go to write the instance declarations, for, say, , we need to know that  is an instance of   otherwise we can't write a declaration. We express this as:

instance Eq a => Eq (Maybe a) where Nothing == Nothing = True (Just x) == (Just x') = x == x' This first line can be read "That  is an instance of  implies  that   is an instance of ."

Deriving Classes
Writing obvious,  ,   and   classes like these is tedious and should be automated. Luckily for us, it is. If you write a datatype that's "simple enough" (almost any datatype you'll write unless you start writing fixed point types), the compiler can automatically derive some of the most basic classes. To do this, you simply add a <tt>deriving</tt> clause to after the datatype declaration, as in:

data Color = Red | ...   | Custom Int Int Int  -- R G B components deriving (Eq, Ord, Show, Read) This will automatically create instances of the  datatype of the named classes. Similarly, the declaration:

data Maybe a = Nothing | Just a            deriving (Eq, Ord, Show, Read) derives these classes just when  is appropriate.

All in all, you are allowed to derive instances of,  , ,,   and. There is considerable work in the area of "polytypic programming" or "generic programming" which, among other things, would allow for instance declarations for any class to be derived. This is much beyond the scope of this tutorial; instead, I refer you to the literature.

Datatypes Revisited
I know by this point you're probably terribly tired of hearing about datatypes. They are, however, incredibly important, otherwise I wouldn't devote so much time to them. Datatypes offer a sort of notational convenience if you have, for instance, a datatype that holds many many values. These are called named fields.

Named Fields
Consider a datatype whose purpose is to hold configuration settings. Usually when you extract members from this type, you really only care about one or possibly two of the many settings. Moreover, if many of the settings have the same type, you might often find yourself wondering "wait, was this the fourth or fifth element?" One thing you could do would be to write accessor functions. Consider the following made-up configuration type for a terminal program:

data Configuration = Configuration String         -- user name String         -- local host String         -- remote host Bool           -- is guest? Bool           -- is super user? String         -- current directory String         -- home directory Integer        -- time connected deriving (Eq, Show) You could then write accessor functions, like (I've only listed a few):

getUserName (Configuration un _ _ _ _ _ _ _) = un getLocalHost (Configuration _ lh _ _ _ _ _ _) = lh getRemoteHost (Configuration _ _ rh _ _ _ _ _) = rh getIsGuest (Configuration _ _ _ ig _ _ _ _) = ig ... You could also write update functions to update a single element. Of course, now if you add an element to the configuration, or remove one, all of these functions now have to take a different number of arguments. This is highly annoying and is an easy place for bugs to slip in. However, there's a solution. We simply give names to the fields in the datatype declaration, as follows:

data Configuration = Configuration { username     :: String, localhost    :: String, remotehost   :: String, isguest      :: Bool, issuperuser  :: Bool, currentdir   :: String, homedir      :: String, timeconnected :: Integer } This will automatically generate the following accessor functions for us:

username :: Configuration -> String localhost :: Configuration -> String ... Moreover, it gives us very convenient update methods. Here is a short example for a "post working directory" and "change directory" like functions that work on s:

changeDir :: Configuration -> String -> Configuration changeDir cfg newDir = -- make sure the directory exists if directoryExists newDir then -- change our current directory cfg{currentdir = newDir} else error "directory does not exist"

postWorkingDir :: Configuration -> String -- retrieve our current directory postWorkingDir cfg = currentdir cfg So, in general, to update the field  in a datatype   to, you write. You can change more than one; each should be separated by commas, for instance,.

You can of course continue to pattern match against s as you did before. The named fields are simply syntactic sugar; you can still write something like:

getUserName (Configuration un _ _ _ _ _ _ _) = un But there is little reason to. Finally, you can pattern match against named fields as in:

getHostData (Configuration {localhost=lh,remotehost=rh}) = (lh,rh) This matches the variable  against the   field on the   and the variable   against the field on the. These matches of course succeed. You could also constrain the matches by putting values instead of variable names in these positions, as you would for standard datatypes.

You can create values of  in the old way as shown in the first definition below, or in the named-field's type, as shown in the second definition below:

initCFG = Configuration "nobody" "nowhere" "nowhere" False False "/" "/" 0 initCFG' = Configuration { username="nobody", localhost="nowhere", remotehost="nowhere", isguest=False, issuperuser=False, currentdir="/", homedir="/", timeconnected=0 } Though the second is probably much more understandable unless you litter your code with comments.

More Lists
to do: put something here

Standard List Functions
Recall that the definition of the built-in Haskell list datatype is equivalent to:

data List a = Nil | Cons a (List a)

With the exception that  is called   and is called. This is simply to make pattern matching easier and code smaller. Let's investigate how some of the standard list functions may be written. Consider. A definition is given below:

map _ [] = [] map f (x:xs) = f x : map f xs Here, the first line says that when you  across an empty list, no matter what the function is, you get an empty list back. The second line says that when you  across a list with   as the head and   as the tail, the result is   applied to  consed onto the result of mapping   on.

The  can be defined similarly:

filter _ [] = [] filter p (x:xs) | p x = x : filter p xs               | otherwise = filter p xs How this works should be clear. For an empty list, we return an empty list. For a non empty list, we return the filter of the tail, perhaps with the head on the front, depending on whether it satisfies the predicate  or not.

We can define  as:

foldr _ z [] = z foldr f z (x:xs) = f x (foldr f z xs) Here, the best interpretation is that we are replacing the empty list with a particular value and the list constructor with some function. On the first line, we can see the replacement of for. Using backquotes to make  infix, we can write the second line as:

foldr f z (x:xs) = x `f` (foldr f z xs) From this, we can directly see how  is being replaced by.

Finally, :

foldl _ z [] = z foldl f z (x:xs) = foldl f (f z x) xs This is slightly more complicated. Remember,  can be thought of as the current state. So if we're folding across a list which is empty, we simply return the current state. On the other hand, if the list is not empty, it's of the form. In this case, we get a new state by applying  to the current state   and the current list element  and then recursively call   on  with this new state.

There is another class of functions: the  and functions, which respectively take multiple lists and make one or take one lists and split them apart. For instance,  does the following:

Basically, it pairs the first elements of both lists and makes that the first element of the new list. It then pairs the second elements of both lists and makes that the second element, etc. What if the lists have unequal length? It simply stops when the shorter one stops. A reasonable definition for  is:

zip [] _ = [] zip _ [] = [] zip (x:xs) (y:ys) = (x,y) : zip xs ys The  function does the opposite. It takes a zipped list and returns the two "original" lists:

There are a whole slew of  and   functions, named ,,  ,   and so on; the functions use triples instead of pairs; the functions use 4-tuples, etc.

Finally, the function  takes an integer $$n$$ and a list and returns the first $$n$$ elements off the list. Correspondingly, takes an integer $$n$$ and a list and returns the result of throwing away the first $$n$$ elements off the list. Neither of these functions produces an error; if $$n$$ is too large, they both will just return shorter lists.

List Comprehensions
There is some syntactic sugar for dealing with lists whose elements are members of the  class (see the section on Instances), such as   or .  If we want to create a list of all the elements from $$1$$ to $$10$$, we can simply write:

We can also introduce an amount to step by:

These expressions are short hand for  and , respectively. Of course, you don't need to specify an upper bound. Try the following (but be ready to hit Control+C to stop the computation!):

Probably yours printed a few thousand more elements than this. As we said before, Haskell is lazy. That means that a list of all numbers from 1 on is perfectly well formed and that's exactly what this list is. Of course, if you attempt to print the list (which we're implicitly doing by typing it in the interpreter), it won't halt. But if we only evaluate an initial segment of this list, we're fine:

This comes in useful if, say, we want to assign an ID to each element in a list. Without laziness we'd have to write something like this:

assignID :: [a] -> [(a,Int)] assignID l = zip l [1..length l] Which means that the list will be traversed twice. However, because of laziness, we can simply write:

assignID l = zip l [1..] And we'll get exactly what we want. We can see that this works:

Finally, there is some useful syntactic sugar for  and , based on standard set-notation in mathematics. In math, we would write something like $$\{ f(x) | x \in s \land p(x) \}$$ to mean the set of all values of $$f$$ when applied to elements of $$s$$ which satisfy $$p$$. This is equivalent to the Haskell statement . However, we can also use more math-like notation and write. While in math the ordering of the statements on the side after the pipe is free, it is not so in Haskell. We could not have put  before otherwise the compiler wouldn't know yet what  was. We can use this to do simple string processing. Suppose we want to take a string, keep only the uppercase letters and convert those to lowercase. We could do this in either of the following two equivalent ways:

These two are equivalent, and, depending on the exact functions you're using, one might be more readable than the other. There's more you can do here, though. Suppose you want to create a list of pairs, one for each point between (0,0) and (5,7) below the diagonal. Doing this manually with lists and maps would be cumbersome and possibly difficult to read. It couldn't be easier than with list comprehensions:

If you reverse the order of the  and   clauses, the order in which the space is traversed will be reversed (of course, in that case,  could no longer depend on   and you would need to make   depend on   but this is trivial).

Arrays
Lists are nice for many things. It is easy to add elements to the beginning of them and to manipulate them in various ways that change the length of the list. However, they are bad for random access, having average complexity $$\mathcal{O}(n)$$ to access an arbitrary element (if you don't know what $$\mathcal{O}(...)$$ means, you can either ignore it or take a quick detour and read the appendix chapter Complexity, a two-page introduction to complexity theory). So, if you're willing to give up fast insertion and deletion because you need random access, you should use arrays instead of lists.

In order to use arrays you must import the  module. There are a few methods for creating arrays, the  function, the function, and the  function. The function takes a pair which is the bounds of the array, and an association list which specifies the initial values of the array. The  function takes bounds and then simply a list of values. Finally, the  function takes an accumulation function, an initial value and an association list and accumulates pairs from the list into the array. Here are some examples of arrays being created:

When arrays are printed out (via the show function), they are printed with an association list. For instance, in the first example, the association list says that the value of the array at $$1$$ is $$2$$, the value of the array at $$2$$ is $$4$$, and so on.

You can extract an element of an array using the  function, which takes an array and an index, as in:

Moreover, you can update elements in the array using the function. This takes an array and an association list and updates the positions specified in the list:

There are a few other functions which are of interest:

If we define  to be , the result of these functions applied to  are:

Note that while arrays are $$\mathcal{O}(1)$$ access, they are not $$\mathcal{O}(1)$$ update. They are in fact $$\mathcal{O}(n)$$ update, since in order to maintain purity, the array must be copied in order to make an update. Thus, functional arrays are pretty much only useful when you're filling them up once and then only reading. If you need fast access and update, you should probably use s, which are discussed in the section on Finitemaps and have $$\mathcal{O}(\log n)$$ access and update.

Maps
The  datatype from the   module is a purely functional implementation of balanced trees. Maps can be compared to lists and arrays in terms of the time it takes to perform various operations on those datatypes of a fixed size, $$n$$. A brief comparison is:

As we can see, lists provide fast insertion (but slow everything else), arrays provide fast lookup (but slow everything else) and maps provide moderately fast everything.

The type of a map is for the form  where is the type of the keys and  is the type of the elements. That is, maps are lookup tables from type to type.

The basic map functions are:

empty :: Map k a insert :: k -> a -> Map k a -> Map k a delete :: k -> Map k a -> Map k a member :: k -> Map k a -> Bool lookup :: k -> Map k a -> a In all these cases, the type  must be an instance of  (and hence also an instance of  ).

There are also function  and   to convert lists to and from maps. Try the following:

The Final Word on Lists
You are likely tired of hearing about lists at this point, but they are so fundamental to Haskell (and really all of functional programming) that it would be terrible not to talk about them some more.

It turns out that  is actually quite a powerful function: it can compute a primitive recursive function. A primitive recursive function is essentially one which can be calculated using only "for" loops, but not "while" loops.

In fact, we can fairly easily define  in terms of  :

map2 f = foldr (\a b -> f a : b) [] Here,  is the accumulator (i.e., the result list) and   is the element being currently considered. In fact, we can simplify this definition through a sequence of steps:

foldr (\a b -> f a : b) [] ==> foldr (\a b ->  (f a) b) [] ==> foldr (\a ->  (f a)) [] ==> foldr (\a -> (. f) a) [] ==> foldr ( . f) [] This is directly related to the fact that  is the identity function on lists. This is because, as mentioned before, can be thought of as replacing the  in lists by  and the   by. In this case, we're keeping both the same, so it is the identity function.

In fact, you can convert any function of the following style into a :

myfunc [] = z myfunc (x:xs) = f x (myfunc xs) By writing the last line with  in infix form, this should be obvious:

myfunc [] = z myfunc (x:xs) = x `f` (myfunc xs) Clearly, we are just replacing  with   and   with . Consider the   function:

filter p [] = [] filter p (x:xs) = if p x   then x : filter p xs    else filter p xs This function also follows the form above. Based on the first line, we can figure out that  is supposed to be , just like in the   case. Now, suppose that we call the result of calling simply, then we can rewrite this as:

filter p [] = [] filter p (x:xs) = if p x then x : b else b Given this, we can transform  into a fold:

filter p = foldr (\a b -> if p a then a:b else b) [] Let's consider a slightly more complicated function:. The definition for  is:

(++) []    ys = ys (++) (x:xs) ys = x : (xs ++ ys) Now, the question is whether we can write this in fold notation. First, we can apply eta reduction to the first line to give:

(++) [] = id Through a sequence of steps, we can also eta-reduce the second line:

(++) (x:xs) ys = x : ((++) xs ys) ==> (++) (x:xs) ys = (x:) ((++) xs ys) ==> (++) (x:xs) ys = ((x:) . (++) xs) ys ==>  (++) (x:xs) = (x:). (++) xs Thus, we get that an eta-reduced definition of  is:

(++) []    = id (++) (x:xs) = (x:). (++) xs Now, we can try to put this into fold notation. First, we notice that the base case converts  into. Now, if we assume is called  and   is called , we can get the following definition in terms of :

(++) = foldr (\a b -> (a:) . b) id This actually makes sense intuitively. If we only think about applying  to one argument, we can think of it as a function which takes a list and creates a function which, when applied, will prepend this list to another list. In the lambda function, we assume we have a function  which will do this for the rest of the list and we need to create a function which will do this for  as well as the single element. In order to do this, we first apply and then further add  to the front.

We can further reduce this expression to a point-free style through the following sequence:

==> (++) = foldr (\a b -> (a:) . b) id ==>  (++) = foldr (\a b -> (.) (a:) b) id ==>  (++) = foldr (\a -> (.) (a:)) id ==>  (++) = foldr (\a -> (.) ( a)) id ==>  (++) = foldr (\a -> ((.). ) a) id ==> (++) = foldr ((.) . ) id This final version is point free, though not necessarily understandable. Presumbably the original version is clearer.

As a final example, consider. We can write this as:

concat []    = [] concat (x:xs) = x ++ concat xs It should be immediately clear that the  element for the fold is  and that the recursive function is , yielding:

concat = foldr (++) []

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Yet Another Haskell Tutorial/Type advanced

As you've probably ascertained by this point, the type system is integral to Haskell. While this chapter is called "Advanced Types", you will probably find it to be more general than that and it must not be skipped simply because you're not interested in the type system.

Type Synonyms
Type synonyms exist in Haskell simply for convenience: their removal would not make Haskell any less powerful.

Consider the case when you are constantly dealing with lists of three-dimensional points. For instance, you might have a function with type. Since you are a good software engineer, you want to place type signatures on all your top-level functions. However, typing  all the time gets very tedious. To get around this, you can define a type synonym:

type List3D = [(Double,Double,Double)] Now, the type signature for your functions may be written.

We should note that type synonyms cannot be self-referential. That is, you cannot have:

type BadType = Int -> BadType This is because this is an "infinite type." Since Haskell removes type synonyms very early on, any instance of  will be replaced by , which will result in an infinite loop.

To make a recursive type, one would use newtype

newtype GoodType = MakeGoodType (Int -> GoodType)

Type synonyms can also be parameterized. For instance, you might want to be able to change the types of the points in the list of 3D points. For this, you could define:

type List3D a = [(a,a,a)] Then your references to  would become .

Newtypes
Consider the problem in which you need to have a type which is very much like, but its ordering is defined differently. Perhaps you wish to order s first by even numbers then by odd numbers (that is, all odd numbers are greater than any even number and within the odd/even subsets, ordering is standard).

Unfortunately, you cannot define a new instance of  for because then Haskell won't know which one to use. What you want is to define a type which is isomorphic to.

One way to do this would be to define a new datatype:

data MyInt = MyInt Int We could then write appropriate code for this datatype. The problem (and this is very subtle) is that this type is not truly isomorphic to : it has one more value. When we think of the type , we usually think that it takes all values of integers, but it really has one more value: $$\bot$$ (pronounced "bottom"), which is used to represent erroneous or undefined computations. Thus, has not only values,   and so on, but also . However, since datatypes can themselves be undefined, it has an additional value: $$\bot$$ which differs from and this makes the types non-isomorphic. (See the section on Bottom for more information on bottom.)

Disregarding that subtlety, there may be efficiency issues with this representation: now, instead of simply storing an integer, we have to store a pointer to an integer and have to follow that pointer whenever we need the value of a.

To get around these problems, Haskell has a newtype construction. A newtype is a cross between a datatype and a type synonym: it has a constructor like a datatype, but it can have only one constructor and this constructor can have only one argument. For instance, we can define:

newtype MyInt = MyInt Int But we cannot define any of:

newtype Bad1 = Bad1a Int | Bad1b Double newtype Bad2 = Bad2 Int Double Of course, the fact that we cannot define  as above is not a big issue: we simply use type instead:

type Good2 = Good2 Int Double

or (almost equivalently) declare a newtype alias to the existing tuple type:

newtype Good2 = Good2 (Int,Double)

Now, suppose we've defined  as a newtype:

instance Ord MyInt where compare (MyInt i) (MyInt j)   | odd  i && odd  j = compare i j    | even i && even j = compare i j    | even i           = LT    | otherwise        = GT Like datatype, we can still derive classes like   and over newtypes (in fact, I'm implicitly assuming we have derived over   -- where is my assumption in the above code?).

Moreover, in recent versions of GHC (see the section on Ghc), on newtypes, you are allowed to derive any class of which the base type (in this case, ) is an instance. For example, we could derive  on   to provide arithmetic functions over it.

Pattern matching over newtypes is exactly as in datatypes. We can write constructor and destructor functions for  as follows:

mkMyInt i = MyInt i unMyInt (MyInt i) = i

Datatypes
We've already seen datatypes used in a variety of contexts. This section concludes some of the discussion and introduces some of the common datatypes in Haskell. It also provides a more theoretical underpinning to what datatypes actually are.

Strict Fields
One of the great things about Haskell is that computation is performed lazily. However, sometimes this leads to inefficiencies. One way around this problem is to use datatypes with strict fields. Before we talk about the solution, let's spend some time to get a bit more comfortable with how bottom works in to the picture (for more theory, see the section on Bottom).

Suppose we've defined the unit datatype (this one of the simplest datatypes you can define):

data Unit = Unit This datatype has exactly one constructor,, which takes no arguments. In a strict language like ML, there would be exactly one value of type : namely,. This is not quite so in Haskell. In fact, there are two values of type. One of them is. The other is bottom (written $$\bot$$).

You can think of bottom as representing a computation which won't halt. For instance, suppose we define the value:

foo = foo This is perfectly valid Haskell code and simply says that when you want to evaluate, all you need to do is evaluate. Clearly this is an "infinite loop."

What is the type of ? Simply. We cannot say anything more about it than that. The fact that  has type   in fact tells us that it must be an infinite loop (or some other such strange value). However, since  has type   and thus can have any type, it can also have type. We could write, for instance:

foo :: Unit foo = foo Thus, we have found a second value with type. In fact, we have found all values of type. Any other non-terminating function or error-producing function will have exactly the same effect as  (though Haskell provides some more utility with the function  ).

This means, for instance, that there are actually four values with type. They are: $$\bot$$, , and. However, it could be the fact that you, as a programmer, know that you will never come across the third of these. Namely, you want the argument to  to be strict. This means that if the argument to  is bottom, then the entire structure becomes bottom. You use an exclamation point to specify a constructor as strict. We can define a strict version of  as:

data SMaybe a = SNothing | SJust !a There are now only three values of. We can see the difference by writing the following program:

module Main where

import System

data SMaybe a = SNothing | SJust !a deriving Show

main = do [cmd] <- getArgs case cmd of   "a" -> printJust   undefined "b" -> printJust  Nothing "c" -> printJust (Just undefined) "d" -> printJust (Just )

"e" -> printSJust undefined "f" -> printSJust SNothing "g" -> printSJust (SJust undefined) "h" -> printSJust (SJust )

printJust :: Maybe -> IO printJust Nothing = putStrLn "Nothing" printJust (Just x) = do putStr "Just "; print x

printSJust :: SMaybe -> IO printSJust SNothing = putStrLn "Nothing" printSJust (SJust x) = do putStr "Just "; print x Here, depending on what command line argument is passed, we will do something different. The outputs for the various options are:

The thing worth noting here is the difference between cases "c" and "g". In the "c" case, the  is printed, because this is printed before the undefined value is evaluated. However, in the "g" case, since the constructor is strict, as soon as you match the, you also match the value. In this case, the value is undefined, so the whole thing fails before it gets a chance to do anything.

Classes
We have already encountered type classes a few times, but only in the context of previously existing type classes. This section is about how to define your own. We will begin the discussion by talking about Pong and then move on to a useful generalization of computations.

Pong
The discussion here will be motivated by the construction of the game Pong (see the appendix on Pong for the full code). In Pong, there are three things drawn on the screen: the two paddles and the ball. While the paddles and the ball are different in a few respects, they share many commonalities, such as position, velocity, acceleration, color, shape, and so on. We can express these commonalities by defining a class for Pong entities, which we call. We make such a definition as follows:

class Entity a where getPosition :: a -> (Int,Int) getVelocity :: a -> (Int,Int) getAcceleration :: a -> (Int,Int) getColor :: a -> Color getShape :: a -> Shape This code defines a typeclass. This class has five methods:,  ,  , and  with the corresponding types.

The first line here uses the keyword class to introduce a new typeclass. We can read this typeclass definition as "There is a typeclass 'Entity'; a type 'a' is an instance of Entity if it provides the following five functions: ...". To see how we can write an instance of this class, let us define a player (paddle) datatype:

data Paddle = Paddle { paddlePosX, paddlePosY, paddleVelX, paddleVelY, paddleAccX, paddleAccY :: Int, paddleColor :: Color, paddleHeight :: Int, playerNumber :: Int } Given this data declaration, we can define  to be an instance of  :

instance Entity Paddle where getPosition p = (paddlePosX p, paddlePosY p) getVelocity p = (paddleVelX p, paddleVelY p)  getAcceleration p = (paddleAccX p, paddleAccY p)  getColor = paddleColor getShape = Rectangle 5. paddleHeight The actual Haskell types of the class functions all have included the context. For example,  has type . However, it will turn out that many of our routines will need entities to also be instances of. We can therefore choose to make  a subclass of  : namely, you can only be an instance of  if you are already an instance of. To do this, we change the first line of the class declaration to:

class Eq a => Entity a where Now, in order to define s to be instances of   we will first need them to be instances of   -- we can do this by deriving the class.

Computations
Let's think back to our original motivation for defining the datatype from the section on Datatypes-maybe. We wanted to be able to express that functions (i.e., computations) can fail.

Let us consider the case of performing search on a graph. Allow us to take a small aside to set up a small graph library:

data Graph v e = Graph [(Int,v)] [(Int,Int,e)] The  datatype takes two type arguments which correspond to vertex and edge labels. The first argument to the constructor is a list (set) of vertices; the second is the list (set) of edges. We will assume these lists are always sorted and that each vertex has a unique id and that there is at most one edge between any two vertices.

Suppose we want to search for a path between two vertices. Perhaps there is no path between those vertices. To represent this, we will use the  datatype. If it succeeds, it will return the list of vertices traversed. Our search function could be written (naively) as follows:

search :: Graph v e -> Int -> Int -> Maybe [Int] search g@(Graph vl el) src dst | src == dst = Just [src] | otherwise = search' el    where search' [] = Nothing search' ((u,v,_):es) | src == u = case search g v dst of                 Just p  -> Just (u:p) Nothing -> search' es             | otherwise = search' es This algorithm works as follows (try to read along): to search in a graph   from   to , first we check to see if these are equal. If they are, we have found our way and just return the trivial solution. Otherwise, we want to traverse the edge-list. If we're traversing the edge-list and it is empty, we've failed, so we return. Otherwise, we're looking at an edge from to. If  is our source, then we consider this step and recursively search the graph from  to. If this fails, we try the rest of the edges; if this succeeds, we put our current position before the path found and return. If  is not our source, this edge is useless and we continue traversing the edge-list.

This algorithm is terrible: namely, if the graph contains cycles, it can loop indefinitely. Nevertheless, it is sufficient for now. Be sure you understand it well: things only get more complicated.

Now, there are cases where the  datatype is not sufficient: perhaps we wish to include an error message together with the failure. We could define a datatype to express this as:

data Failable a = Success a | Fail String Now, failures come with a failure string to express what went wrong. We can rewrite our search function to use this datatype:

search2 :: Graph v e -> Int -> Int -> Failable [Int] search2 g@(Graph vl el) src dst | src == dst = Success [src] | otherwise = search' el    where search' [] = Fail "No path" search' ((u,v,_):es) | src == u = case search2 g v dst of                 Success p -> Success (u:p) _        -> search' es              | otherwise = search' es This code is a straightforward translation of the above.

There is another option for this computation: perhaps we want not just one path, but all possible paths. We can express this as a function which returns a list of lists of vertices. The basic idea is the same:

search3 :: Graph v e -> Int -> Int -> Int search3 g@(Graph vl el) src dst | src == dst = src | otherwise = search' el    where search' [] = [] search' ((u,v,_):es) | src == u = map (u:) (search3 g v dst) ++ search' es             | otherwise = search' es The code here has gotten a little shorter, thanks to the standard prelude  function, though it is essentially the same.

We may ask ourselves what all of these have in common and try to gobble up those commonalities in a class. In essence, we need some way of representing success and some way of representing failure. Furthermore, we need a way to combine two successes (in the first two cases, the first success is chosen; in the third, they are strung together). Finally, we need to be able to augment a previous success (if there was one) with some new value. We can fit this all into a class as follows:

class Computation c where success :: a -> c a   failure :: String -> c a    augment :: c a -> (a -> c b) -> c b    combine :: c a -> c a -> c a In this class declaration, we're saying that   is an instance of the class   if it provides four functions: ,,   and. The function takes a value of type  and returns it wrapped up in , representing a successful computation. The function takes a  and returns a computation representing a failure. The  function takes two previous computations and produces a new one which is the combination of both. The  function is a bit more complex.

The  function takes some previously given computation (namely, ) and a function which takes the value of that computation (the ) and returns a   and produces a  inside of that computation. Note that in our current situation, giving  the type   would have been sufficient, since  is always , but we make it more general this time just for generality.

How  works is probably best shown by example. We can define,   and   to be instances of  as:

instance Computation Maybe where success = Just failure = const Nothing augment (Just x) f = f x   augment Nothing  _ = Nothing combine Nothing y = y   combine x _ = x Here, success is represented with   and   ignores its argument and returns. The  function takes the first success we found and ignores the rest. The function checks to see if we succeeded before (and thus had a something) and, if we did, applies   to it. If we failed before (and thus had a ), we ignore the function and return.

instance Computation Failable where success = Success failure = Fail augment (Success x) f = f x   augment (Fail s) _ = Fail s    combine (Fail _) y = y    combine x _ = x These definitions are obvious. Finally:

instance Computation [] where success a = [a] failure = const [] augment l f = concat (map f l)   combine = (++) Here, the value of a successful computation is a singleton list containing that value. Failure is represented with the empty list and to combine previous successes we simply catenate them. Finally, augmenting a computation amounts to mapping the function across the list of previous computations and concatenate them. we apply the function to each element in the list and then concatenate the results.

Using these computations, we can express all of the above versions of search as:

searchAll g@(Graph vl el) src dst | src == dst = success [src] | otherwise = search' el    where search' [] = failure "no path" search' ((u,v,_):es) | src == u = (searchAll g v dst `augment`                             (success. (u:))) `combine` search' es             | otherwise = search' es In this, we see the uses of all the functions from the class .

If you've understood this discussion of computations, you are in a very good position as you have understood the concept of monads, probably the most difficult concept in Haskell. In fact, the  class is almost exactly the class, except that  is called ,   is called   and   is called   (read "bind"). The  function isn't actually required by monads, but is found in the   class for reasons which will become obvious later.

If you didn't understand everything here, read through it again and then wait for the proper discussion of monads in the chapter Monads.

Instances
We have already seen how to declare instances of some simple classes; allow us to consider some more advanced classes here. There is a class defined in the   module.

The definition of the functor class is:

class Functor f where fmap :: (a -> b) -> f a -> f b The type definition for  (not to mention its name) is very similar to the function  over lists. In fact,  is essentially a generalization of   to arbitrary structures (and, of course, lists are already instances of  ). However, we can also define other structures to be instances of functors. Consider the following datatype for binary trees:

data BinTree a = Leaf a              | Branch (BinTree a) (BinTree a) We can immediately identify that the   type essentially "raises" a type  into trees of that type. There is a naturally associated functor which goes along with this raising. We can write the instance:

instance Functor BinTree where fmap f (Leaf a) = Leaf (f a)   fmap f (Branch left right) = Branch (fmap f left) (fmap f right) Now, we've seen how to make something like  an instance of  by using the deriving keyword, but here we will do it by hand. We want to make s instances of   but obviously we cannot do this unless  is itself an instance of .  We can specify this dependence in the instance declaration:

instance Eq a => Eq (BinTree a) where Leaf a == Leaf b = a == b   Branch l r == Branch l' r' = l == l' && r == r'    _ == _ = False The first line of this can be read "if  is an instance of, then   is also an instance of  ". We then provide the definitions. If we did not include the  part, the compiler would complain because we're trying to use the  function on  s in the second line.

The " " part of the definition is called the "context." We should note that there are some restrictions on what can appear in the context and what can appear in the declaration. For instance, we're not allowed to have instance declarations that don't contain type constructors on the right hand side. To see why, consider the following declarations:

class MyEq a where myeq :: a -> a -> Bool

instance Eq a => MyEq a where myeq = (==) As it stands, there doesn't seem to be anything wrong with this definition. However, if elsewhere in a program we had the definition:

instance MyEq a => Eq a where (==) = myeq In this case, if we're trying to establish if some type is an instance of, we could reduce it to trying to find out if that type is an instance of  , which we could in turn reduce to trying to find out if that type is an instance of  , and so on. The compiler protects itself against this by refusing the first instance declaration.

This is commonly known as the closed-world assumption. That is, we're assuming, when we write a definition like the first one, that there won't be any declarations like the second. However, this assumption is invalid because there's nothing to prevent the second declaration (or some equally evil declaration). The closed world assumption can also bite you in cases like:

class OnlyInts a where foo :: a -> a -> Bool

instance OnlyInts Int where foo = (==)

bar :: OnlyInts a => a -> Bool bar = foo 5

We've again made the closed-world assumption: we've assumed that the only instance of  is , but there's no reason another instance couldn't be defined elsewhere, ruining our definition of.

Kinds
Let us take a moment and think about what types are available in Haskell. We have simple types, like,  , and so on. We then have type constructors like  which take a type (like ) and produce a new type,. Similarly, the type constructor  (lists) takes a type (like ) and produces. We have more complex things like (function arrow) which takes two types (say and  ) and produces a new type.

In a sense, these types themselves have type. Types like have some sort of basic type. Types like  have a type which takes something of basic type and returns something of basic type. And so forth.

Talking about the types of types becomes unwieldy and highly ambiguous, so we call the types of types "kinds." What we have been calling "basic types" have kind " ". Something of kind is something which can have an actual value. There is also a single kind constructor,  with which we can build more complex kinds.

Consider. This takes something of kind  and produces something of kind. Thus, the kind of  is. Recall the definition of  from the section on Datatypes-pairs:

data Pair a b = Pair a b Here,  is a type constructor which takes two arguments, each of kind  and produces a type of kind. Thus, the kind of is. However, we again assume associativity so we just write.

Let us make a slightly strange datatype definition:

data Strange c a b = MkStrange (c a) (c b) Before we analyze the kind of, let's think about what it does. It is essentially a pairing constructor, though it doesn't pair actual elements, but elements within another constructor. For instance, think of  as. Then  pairs s of the two types  and. However, need not be  but could instead by , or many other things.

What do we know about, though? We know that it must have kind . This is because we have   on the right hand side. The type variables  and   each have kind   as before. Thus, the kind of  is. That is, it takes a constructor of kind together with two types of kind  and produces something of kind .

A question may arise regarding how we know  has kind   and not some other kind. In fact, the inferred kind for is. However, this requires polymorphism on the kind level, which is too complex, so we make a default assumption that.

The notation of kinds suggests that we can perform partial application, as we can for functions. And, in fact, we can. For instance, we could have:

type MaybePair = Strange Maybe The kind of  is, not surprisingly,.

We should note here that all of the following definitions are acceptable:

type MaybePair1    = Strange Maybe type MaybePair2 a  = Strange Maybe a type MaybePair3 a b = Strange Maybe a b These all appear to be the same, but they are in fact not identical as far as Haskell's type system is concerned. The following are all valid type definitions using the above:

type MaybePair1a = MaybePair1 type MaybePair1b = MaybePair1 Int type MaybePair1c = MaybePair1 Int Double

type MaybePair2b = MaybePair2 Int type MaybePair2c = MaybePair2 Int Double

type MaybePair3c = MaybePair3 Int Double But the following are not valid:

type MaybePair2a = MaybePair2

type MaybePair3a = MaybePair3 type MaybePair3b = MaybePair3 Int This is because while it is possible to partially apply type constructors on datatypes, it is not possible on type synonyms. For instance, the reason  is invalid is because is defined as a type synonym with one argument and we have given it none. The same applies for the invalid definitions.

Default
what is it?