text:
Yet Another Haskell Tutorial/Monads

The most difficult concept to master while learning Haskell is that of understanding and using monads. We can distinguish two subcomponents here: (1) learning how to use existing monads and (2) learning how to write new ones. If you want to use Haskell, you must learn to use existing monads. On the other hand, you will only need to learn to write your own monads if you want to become a "super Haskell guru." Still, if you can grasp writing your own monads, programming in Haskell will be much more pleasant.

So far we've seen two uses of monads. The first use was IO actions: We've seen that, by using monads, we can get away from the problems plaguing the RealWorld solution to IO presented in the chapter IO. The second use was representing different types of computations in the section on Classes-computations. In both cases, we needed a way to sequence operations and saw that a sufficient definition (at least for computations) was:

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 Let's see if this definition will enable us to also perform IO. Essentially, we need a way to represent taking a value out of an action and performing some new operation on it (as in the example from the section on Functions-io, rephrased slightly):

main = do s <- readFile "somefile" putStrLn (show (f s)) But this is exactly what  does. Using, we can write the above code as:

main = -- note the lack of a "do" readFile "somefile" `augment` \s -> putStrLn (show (f s)) This certainly seems to be sufficient. And, in fact, it turns out to be more than sufficient.

The definition of a monad is a slightly trimmed-down version of our class. The  class has four methods (but the fourth method can be defined in terms of the third):

class Monad m where return :: a -> m a    fail    :: String -> m a    (>>=)   :: m a -> (a -> m b) -> m b    (>>)    :: m a -> m b -> m b In this definition,   is equivalent to our  ; is equivalent to our ; and   (read: "bind" ) is equivalent to our. The (read: "then" ) method is simply a version of that ignores the. This will turn out to be useful; although, as mentioned before, it can be defined in terms of :

a >> x = a >>= \_ -> x

Do Notation
We have hinted that there is a connection between monads and the notation. Here, we make that relationship concrete. There is actually nothing magic about the  notation – it is simply "syntactic sugar" for monadic operations.

As we mentioned earlier, using our  class, we could define our above program as:

main = readFile "somefile" `augment` \s -> putStrLn (show (f s)) But we now know that  is called   in the monadic world. Thus, this program really reads:

main = readFile "somefile" >>= \s -> putStrLn (show (f s)) And this is completely valid Haskell at this point: if you defined a function, you could compile and run this program)

This suggests that we can translate:

x <- f g x into. This is exactly what the compiler does. Talking about  becomes easier if we do not use implicit layout (see the section on Layout for how to do this). There are four translation rules:

 * 1)    →
 * 2)    →
 * 3)    →
 * 4)    →

Again, we will elaborate on these one at a time:

Translation Rule 1
The first translation rule,  → , states (as we have stated before) that when performing a single action, having a  or not is irrelevant. This is essentially the base case for an inductive definition of. The base case has one action (namely  here); the other three translation rules handle the cases where there is more than one action.

Translation Rule 2
This states that  →. This tells us what to do if we have an action followed by a list of actions. Here, we make use of the  function, defined earlier. This rule simply states that to  , we first perform the action  , throw away the result, and then.

For instance, if  is   for some string  , then the translation of  is to perform   (i.e., print the string) and then. This is clearly what we want.

Translation Rule 3
This states that →. This rule tells us how to deal with s inside of a   statement. We lift the declarations within the  out and   whatever comes after the declarations.

Translation Rule 4
This states that  →. Again, it is not exactly obvious what is going on here. However, an alternate formulation of this rule, which is roughly equivalent, is:  → . Here, it is clear what is happening. We run the action, and then send the results into  , but first give the result the name.

The reason for the complex definition is that  doesn't need to simply be a variable; it could be some complex pattern. For instance, the following is valid code:

foo = do ('a':'b':'c':x:xs) <- getLine putStrLn (x:xs) In this, we're assuming that the results of the action will begin with the string "abc" and will have at least one more character. The question becomes what should happen if this pattern match fails. The compiler could simply throw an error, like usual, for failed pattern matches. However, since we're within a monad, we have access to a special  function, and we'd prefer to fail using that function, rather than the "catch all" function. Thus, the translation, as defined, allows the compiler to fill in the   with an appropriate error message about the pattern matching having failed. Apart from this, the two definitions are equivalent.

Definition
There are three rules that all monads must obey called the "Monad Laws" (and it is up to you to ensure that your monads obey these rules) :

 * 1)    ≡
 * 2)    ≡
 * 3)    ≡

Let's look at each of these individually:

Law 1
This states that  ≡. Suppose we think about monads as computations. This means that if we create a trivial computation that simply returns the value  regardless of anything else (this is the   part); and then bind it together with some other computation , then this is equivalent to simply performing the computation  on   directly.

For example, suppose  is the function   and is the string "Hello World." This rule states that binding a computation whose result is "Hello World" to  is the same as simply printing it to the screen. This seems to make sense.

In  notation, this law states that the following two programs are equivalent:

law1a = do x <- return a  f x

law1b = do f a

Law 2
The second monad law states that  ≡   for some computation. In other words, the law states that if we perform the computation  and then pass the result on to the trivial function, then all we have done is to perform the computation.

That this law must hold should be obvious. To see this, think of as   (reads a string from the keyboard). This law states that reading a string and then returning the value read is exactly the same as just reading the string.

In  notation, the law states that the following two programs are equivalent:

law2a = do x <- f  return x

law2b = do f

Law 3
This states that  ≡. At first glance, this law is not as easy to grasp as the other two. It is essentially an associativity law for monads.

If we throw away the messiness with the lambdas, we see that this law states:  ≡. The intuition behind this law is that when we string together actions, it doesn't matter how we group them.

For a concrete example, take  to be. Take to be an action which takes a value as input, prints it to the screen, reads another string via, and then returns that newly read string. Take  to be.

Let's consider what  does. It takes a value called, and runs   on it, feeding the results into. In this instance, this means that it's going to take a value, print it, read another value and then print that. Thus, the entire left hand side of the law first reads a string and then does what we've just described.

On the other hand, consider. This action reads a string from the keyboard, prints it, and then reads another string, returning that newly read string as a result. When we bind this with as on the right hand side of the law, we get an action that does the action described by, and then prints the results.

Clearly, these two actions are the same.

While this explanation is quite complicated, and the text of the law is also quite complicated, the actual meaning is simple: if we have three actions, and we compose them in the same order, it doesn't matter where we put the parentheses. The rest is just notation.

In  notation, the law says that the following two programs are equivalent:

law3a = do x <- f  do y <- g x     h y

law3b = do y <- do x <- f          g x  h y

A Simple State Monad
One of the simplest monads that we can craft is a state-passing monad. In Haskell, all state information usually must be passed to functions explicitly as arguments. Using monads, we can effectively hide some state information.

Suppose we have a function  of type , and we need to add state to this function. In general, if state is of type , we can encode it by changing the type of  to. That is, the new version of  takes the original parameter of type  and a new state parameter. And, in addition to returning the value of type, it also returns an updated state, encoded in a tuple.

For instance, suppose we have a binary tree defined as:

data Tree a = Leaf a  | Branch (Tree a) (Tree a) Now, we can write a simple map function to apply some function to each value in the leaves:

mapTree :: (a -> b) -> Tree a -> Tree b mapTree f (Leaf a) = Leaf (f a) mapTree f (Branch lhs rhs) = Branch (mapTree f lhs) (mapTree f rhs) This works fine until we need to write a function that numbers the leaves left to right. In a sense, we need to add state, which keeps track of how many leaves we've numbered so far, to the function. We can augment the function to something like:

mapTreeState :: (a -> state -> (state, b)) -> Tree a -> state -> (state, Tree b) mapTreeState f (Leaf a) state = let (state', b) = f a state in (state', Leaf b) mapTreeState f (Branch lhs rhs) state = let (state', lhs') = mapTreeState f lhs state (state'', rhs') = mapTreeState f rhs state' in (state'', Branch lhs' rhs') This is beginning to get a bit unwieldy, and the type signature is getting harder and harder to understand. What we want to do is abstract away the state passing part. That is, the differences between  and   are: (1) the augmented type, (2) we replaced the type  with. Notice that both types changed in exactly the same way. We can abstract this away with a type synonym declaration:

type State st a = st -> (st, a) To go along with this type, we write two functions:

returnState :: a -> State st a returnState a = \st -> (st, a)

bindState :: State st a -> (a -> State st b) -> State st b bindState m k = \st -> let (st', a) = m st       m'       = k a    in  m' st' Let's examine each of these in turn. The first function, , takes a value of type  and creates something of type. If we think of the  as the state, and the value of type  as the value, then this is a function that doesn't change the state and returns the value.

The  function looks distinctly like the interior declarations in. It takes two arguments. The first argument is an action that returns something of type with state. The second is a function that takes this and produces something of type  also with the same state. The result of  is essentially the result of transforming the into a.

The definition of  takes an initial state,. It first applies this to the  argument called. This gives back a new state  and a value. It then lets the function  act on , producing something of type , called. We finally run  with the new state.

We write a new function,  and give it the type:

mapTreeStateM :: (a -> State st b) -> Tree a -> State st (Tree b) Using these "plumbing" functions ( and ) we can write this function without ever having to explicitly talk about the state:

mapTreeStateM f (Leaf a) = f a `bindState` \b -> returnState (Leaf b) mapTreeStateM f (Branch lhs rhs) = mapTreeStateM f lhs `bindState` \lhs' -> mapTreeStateM f rhs `bindState` \rhs' -> returnState (Branch lhs' rhs') In the  case, we apply   to   and then bind the result to a function that takes the result and returns a with the new value.

In the  case, we recurse on the left-hand-side, binding the result to a function that recurses on the right-hand-side, binding that to a simple function that returns the newly created.

As you have probably guessed by this point,  is a monad, is analogous to the overloaded  method, and is analogous to the overloaded  method. In fact, we can verify that  obeys the monad laws:

Law 1 states:  ≡. Let's calculate on the left hand side, substituting our names:

returnState a `bindState` f ==> \st -> let (st', a) = (returnState a) st               m'       = f a            in  m' st' ==>    \st -> let (st', a) = (\st -> (st, a)) st            in  (f a) st' ==>    \st -> let (st', a) = (st, a)            in  (f a) st' ==>    \st -> (f a) st ==> f a In the first step, we simply substitute the definition of . In the second step, we simplify the last two lines and substitute the definition of. In the third step, we apply  to the lambda function. In the fourth step, we rename  to   and remove the. In the last step, we eta reduce.

Moving on to Law 2, we need to show that ≡. This is shown as follows:

f `bindState` returnState ==>    \st -> let (st', a) = f st            in  (returnState a) st' ==>    \st -> let (st', a) = f st            in  (\st -> (st, a)) st' ==>    \st -> let (st', a) = f st            in  (st', a) ==> \st -> f st ==> f Finally, we need to show that  obeys the third law:   ≡. This is much more involved to show, so we will only sketch the proof here. Notice that we can write the left-hand-side as:

\st -> let (st', a) = f st           in  (\x -> g x `bindState` h) a st' ==>    \st -> let (st', a) = f st            in  (g a `bindState` h) st' ==>    \st -> let (st', a) = f st            in  (\st' -> let (st, b) = g a                         in  h b st) st' ==>    \st -> let (st', a) = f st                (st'', b) = g a st' (st',c) = h b st in (st''',c) The interesting thing to note here is that we have both action applications on the same  level. Since  is associative, this means that we can put whichever bracketing we prefer and the results will not change. Of course, this is an informal, "hand waving" argument and it would take us a few more derivations to actually prove, but this gives the general idea.

Now that we know that  is actually a monad, we'd like to make it an instance of the   class. Unfortunately, the straightforward way of doing this doesn't work. We can't write:

instance Monad (State st) where { ... } This is because you cannot make instances out of non-fully-applied type synonyms. Instead, what we need to do instead is convert the type synonym into a, as:

newtype State st a = State (st -> (st, a)) Unfortunately, this means that we need to do some packing and unpacking of the  constructor in the   instance declaration, but it's not terribly difficult:

instance Monad (State state) where return a = State (\state -> (state, a)) State run >>= action = State run' where run' st = let (st', a)   = run st                      State run = action a                  in  run st' Now, we can write our  function as:

mapTreeM :: (a -> State state b) -> Tree a -> State state (Tree b) mapTreeM f (Leaf a) = do b <- f a  return (Leaf b) mapTreeM f (Branch lhs rhs) = do  lhs' <- mapTreeM f lhs rhs' <- mapTreeM f rhs return (Branch lhs' rhs') which is significantly cleaner than before. In fact, if we remove the type signature, we get the more general type:

mapTreeM :: Monad m => (a -> m b) -> Tree a -> m (Tree b) That is,  can be run in any monad, not just our monad.

Now, the nice thing about encapsulating the stateful aspect of the computation like this is that we can provide functions to get and change the current state. These look like:

getState :: State state state getState = State (\state -> (state, state))

putState :: state -> State state putState new = State (\_ -> (new, )) Here,  is a monadic operation that takes the current state, passes it through unchanged, and then returns it as the value. The  function takes a new state and produces an action that ignores the current state and inserts the new one.

Now, we can write our  function as:

numberTree :: Tree a -> State Int (Tree (a, Int)) numberTree tree = mapTreeM number tree where number v = do           cur <- getState putState (cur+1) return (v,cur) Finally, we need to be able to run the action by providing an initial state:

runStateM :: State state a -> state -> a runStateM (State f) st = snd (f st) Now, we can provide an example Tree:

testTree = Branch (Branch     (Leaf 'a')      (Branch (Leaf 'b') (Leaf 'c'))) (Branch     (Leaf 'd')      (Leaf 'e')) and number it:

This may seem like a large amount of work to do something simple. However, note the new power of. We can also print out the leaves of the tree in a left-to-right fashion as:

This crucially relies on the fact that  has the more general type involving arbitrary monads -- not just the state monad. Furthermore, we can write an action that will make each leaf value equal to its old value as well as all the values preceding:

fluffLeaves tree = mapTreeM fluff tree where fluff v = do           cur <- getState putState (v:cur) return (v:cur) and can see it in action:

In fact, you don't even need to write your own monad instance and datatype. All this is built in to the module. There, our  is called  ; our is called ; and our   is called .

This module also contains a state transformer monad, which we will discuss in the section on Transformer.

Common Monads
It turns out that many of our favorite datatypes are actually monads themselves. Consider, for instance, lists. They have a monad definition that looks something like:

instance Monad [] where return x = [x] l >>= f = concatMap f l    fail _   = [] This enables us to use lists in do notation. For instance, given the definition:

cross l1 l2 = do x <- l1  y <- l2  return (x,y) we get a cross-product function:

It is not a coincidence that this looks very much like the list comprehension form:

List comprehension form is simply an abbreviated form of a monadic statement using lists. In fact, in older versions of Haskell, the list comprehension form could be used for any monad -- not just lists. However, in the current version of Haskell, this is no longer allowed.

The  type is also a monad, with failure being represented as  and with success as. We get the following instance declaration:

instance Monad Maybe where return a     = Just a    Nothing >>= f = Nothing Just x >>= f = f x    fail _        = Nothing We can use the same cross product function that we did for lists on s.  This is because the   notation works for any monad, and there's nothing specific to lists about the function.

What this means is that if we write a function (like from the section on Classes) only in terms of monadic operators, we can use it with any monad, depending on what we mean. Using real monadic functions (not  notation), the function looks something like:

searchAll g@(Graph vl el) src dst | src == dst = return [src] | otherwise = search' el    where search' [] = fail "no path" search' ((u,v,_):es) | src == u = searchAll g v dst >>= \path -> return (u:path) | otherwise = search' es The type of this function is. This means that no matter what monad we're using at the moment, this function will perform the calculation. Suppose we have the following graph:

gr = Graph [(0, 'a'), (1, 'b'), (2, 'c'), (3, 'd')] [(0,1,'l'), (0,2,'m'), (1,3,'n'), (2,3,'m')] This represents a graph with four nodes, labelled  and. There is an edge from  to both   and. There is also an edge from both  and   to. Using the  monad, we can compute the path from   to  :

We provide the type signature, so that the interpreter knows what monad we're using. If we try to search in the opposite direction, there is no path. The inability to find a path is represented as in the   monad:

Note that the string "no path" has disappeared since there's no way for the  monad to record this.

If we perform the same impossible search in the list monad, we get the empty list, indicating no path:

If we perform the possible search, we get back a list containing the first path:

You may have expected this function call to return all paths, but, as coded, it does not. See the section on Plus for more about using lists to represent nondeterminism.

If we use the IO monad, we can actually get at the error message, since IO knows how to keep track of error messages:

In the first case, we needed to type  to get GHCi to actually evaluate the search.

There is one problem with this implementation of : if it finds an edge that does not lead to a solution, it won't be able to backtrack. This has to do with the recursive call to inside of. Consider, for instance, what happens if doesn't find a path. There's no way for this implementation to recover. For instance, if we remove the edge from node  to node , we should still be able to find a path from  to , but this algorithm can't find it. We define:

gr2 = Graph [(0, 'a'), (1, 'b'), (2, 'c'), (3, 'd')] [(0,1,'l'), (0,2,'m'), (2,3,'m')] and then try to search:

To fix this, we need a function like  from our class. We will see how to do this in the section on Plus.

Monadic Combinators
The /  library contains a few very useful monadic combinators, which haven't yet been thoroughly discussed. The ones we will discuss in this section, together with their types, are:

In the above,  is always assumed to be an instance of.

In general, functions with an underscore at the end are equivalent to the ones without, except that they do not return any value.

The  function is exactly the same as , except it takes its arguments in the opposite order. For instance, in the IO monad, we can write either of the following:

The,   and are our old friends,   and wrapped up inside of monads. These functions are incredibly useful (particularly ) when working with monads. We can use, for instance, to print a list of things to the screen:

We can use  to sum a list and print the intermediate sum at each step:

The  and   functions simply "execute" a list of actions. For instance:

We can see that the underscored version doesn't return each value, while the non-underscored version returns the list of the return values.

The  function "lifts" a non-monadic function to a monadic function. (Do not confuse this with the function used for monad transformers in the section on Transformer.)  This is useful for shortening code (among other things). For instance, we might want to write a function that prepends each line in a file with its line number. We can do this with:

numberFile :: FilePath -> IO numberFile fp = do text <- readFile fp  let l = lines text let n = zipWith (\n t -> show n ++ ' ' : t) [1..] l mapM_ putStrLn n However, we can shorten this using  :

numberFile :: FilePath -> IO numberFile fp = do l <- lines `liftM` readFile fp  let n = zipWith (\n t -> show n ++ ' ' : t) [1..] l  mapM_ putStrLn n In fact, you can apply any sort of (pure) processing to a file using . For instance, perhaps we also want to split lines into words; we can do this with:

... w <- (map words . lines) `liftM` readFile fp  ... Note that the parentheses are required, since the  function has the same fixity has.

Lifting pure functions into monads is also useful in other monads. For instance  can be used to apply function inside of .  For instance:

Monads> liftM (+1) (Just 5) Just 6 Monads> liftM (+1) Nothing Nothing The  function executes a monadic action only if a condition is met. So, if we only want to print non-empty lines:

Of course, the same could be accomplished with, but sometimes  is more convenient.

Finally, the  function is the monadic equivalent of  on lists. In fact, when  is the list monad, is exactly. In other monads, it accomplishes a similar task:

These functions will turn out to be even more useful as we move on to more advanced topics in the chapter Io advanced.

MonadPlus
Given only the  and   functions, it is impossible to write a function like   with type. However, such a function is so generally useful that it exists in another class called . In addition to having a  function, instances of   also have a "zero" element that is the identity under the "plus" (i.e., combine) action. The definition is:

class Monad m => MonadPlus m where mzero :: m a mplus :: m a -> m a -> m a In order to gain access to , you need to import the module (or  in the hierarchical libraries).

In the section on Common, we showed that and list are both monads. In fact, they are also both instances of. In the case of, the zero element is ; in the case of lists, it is the empty list. The  operation on   is, if both elements are  ; otherwise, it is the first  value. For lists,  is the same as.

That is, the instance declarations look like:

instance MonadPlus Maybe where mzero = Nothing mplus Nothing y = y mplus x       _ = x

instance MonadPlus [] where mzero = [] mplus x y = x ++ y We can use this class to reimplement the search function we've been exploring, such that it will explore all possible paths. The new function looks like:

searchAll2 g@(Graph vl el) src dst | src == dst = return [src] | otherwise = search' el    where search' [] = fail "no path" search' ((u,v,_):es) | src == u = (searchAll2 g v dst >>= \path ->                 return (u:path)) `mplus` search' es             | otherwise = search' es

Now, when we're going through the edge list in, and we come across a matching edge, not only do we explore this path, but we also continue to explore the out-edges of the current node in the recursive call to.

The IO monad is not an instance of ; we're not able to execute the search with this monad. We can see that when using lists as the monad, we (a) get all possible paths in  and (b) get a path in.

You might be tempted to implement this as:

searchAll2 g@(Graph vl el) src dst | src == dst = return [src] | otherwise = search' el    where search' [] = fail "no path" search' ((u,v,_):es) | src == u = do                 path <- searchAll2 g v dst rest <- search' es                return ((u:path) `mplus` rest) | otherwise = search' es But note that this doesn't do what we want. Here, if the recursive call to  fails, we don't try to continue and execute . The call to   must be at the top level in order for it to work.

Monad Transformers
Often we want to "piggyback" monads on top of each other. For instance, there might be a case where you need access to both IO operations through the IO monad and state functions through some state monad. In order to accomplish this, we introduce a class, which essentially "lifts" the operations of one monad into another. You can think of this as stacking monads on top of each other. This class has a simple method:. The class declaration for is:

class MonadTrans t where lift :: Monad m => m a -> t m a The idea here is that  is the outer monad and that   lives inside of it. In order to execute a command of type, we first   it into the transformer.

The simplest example of a transformer (and arguably the most useful) is the state transformer monad, which is a state monad wrapped around an arbitrary monad. Before, we defined a state monad as:

newtype State state a = State (state -> (state, a)) Now, instead of using a function of type  as the monad, we assume there's some other monad   and make the internal action into something of type. This gives rise to the following definition for a state transformer:

newtype StateT state m a = StateT (state -> m (state, a)) For instance, we can think of  as IO. In this case, our state transformer monad is able to execute actions in the IO monad. First, we make this an instance of :

instance MonadTrans (StateT state) where lift m = StateT (\s -> do a <- m                             return (s,a)) Here, lifting a function from the realm of  to the realm of  simply involves keeping the state (the   value) constant and executing the action.

Of course, we also need to make  a monad, itself. This is relatively straightforward, provided that  is already a monad:

instance Monad m => Monad (StateT state m) where return a = StateT (\s -> return (s,a)) StateT m >>= k = StateT (\s -> do   (s', a) <- m s    let StateT m' = k a    m' s') fail s = StateT (\_ -> fail s) The idea behind the definition of  is that we keep the state constant and simply return the state/a pair in the enclosed monad. Note that the use of  in the definition of  refers to the enclosed monad, not the state transformer.

In the definition of bind, we create a new  that takes a state   as an argument. First, it applies this state to the first action and gets the new state and answer as a result. It then runs the  action on this new state and gets a new transformer. It finally applies the new state to this transformer. This definition is nearly identical to the definition of bind for the standard (non-transformer)  monad described in the section on State.

The  function passes on the call to   in the enclosed monad, since state transformers don't natively know how to deal with failure.

Of course, in order to actually use this monad, we need to provide function ,    and . These are analogous to,   and   from the section on State:

getT :: Monad m => StateT s m s getT = StateT (\s -> return (s, s))

putT :: Monad m => s -> StateT s m putT s = StateT (\_ -> return (s, ))

evalStateT :: Monad m => StateT s m a -> s -> m a evalStateT (StateT m) state = do (s', a) <- m state return a These functions should be straightforward. Note, however, that the result of  is actually a monadic action in the enclosed monad. This is typical of monad transformers: they don't know how to actually run things in their enclosed monad (they only know how to actions). Thus, what you get out is a monadic action in the inside monad (in our case, IO), which you then need to run yourself.

We can use state transformers to reimplement a version of our function from the section on State. The only change here is that when we get to a leaf, we print out the value of the leaf; when we get to a branch, we just print out "Branch."

mapTreeM action (Leaf a) = do lift (putStrLn ("Leaf " ++ show a)) b <- action a return (Leaf b) mapTreeM action (Branch lhs rhs) = do  lift (putStrLn "Branch") lhs' <- mapTreeM action lhs rhs' <- mapTreeM action rhs return (Branch lhs' rhs') The only difference between this function and the one from the section on State is the calls to  as the first line. The  tells us that we're going to be executing a command in an enclosed monad. In this case, the enclosed monad is, since the command lifted is.

The type of this function is relatively complex:

mapTreeM :: (MonadTrans t, Monad (t IO), Show a) => (a -> t IO a1) -> Tree a -> t IO (Tree a1) Ignoring, for a second, the class constraints, this says that takes an action and a tree and returns a tree. This just as before. In this, we require that  is a monad transformer (since we apply  in it); we require that   is a monad, since we use   we know that the enclosed monad is ; finally, we require that   is an instance of show -- this is simply because we use   to show the value of leaves.

Now, we simply change  to use this version of, and the new versions of   and  , and we end up with:

numberTree tree = mapTreeM number tree where number v = do           cur <- getT putT (cur+1) return (v,cur) Using this, we can run our monad:

One problem not specified in our discussion of  is that our search algorithm will fail to terminate on graphs with cycles. Consider:

gr3 = Graph [(0, 'a'), (1, 'b'), (2, 'c'), (3, 'd')] [(0,1,'l'), (1,0,'m'), (0,2,'n'), (1,3,'o'), (2,3,'p')] In this graph, there is a back edge from node b back to node a. If we attempt to run, regardless of what monad we use, it will fail to terminate. Moreover, if we move this erroneous edge to the end of the list (and call this ), the result of  will contain an infinite number of paths: presumably we only want paths that don't contain cycles.

In order to get around this problem, we need to introduce state. Namely, we need to keep track of which nodes we have visited, so that we don't visit them again.

We can do this as follows:

searchAll5 g@(Graph vl el) src dst | src == dst = do     visited <- getT putT (src:visited) return [src] | otherwise = do      visited <- getT putT (src:visited) if src `elem` visited then mzero else search' el where search' [] = mzero search' ((u,v,_):es) | src == u = (do path <- searchAll5 g v dst             return (u:path)) `mplus` search' es       | otherwise = search' es Here, we implicitly use a state transformer (see the calls to  and  ) to keep track of visited states. We only continue to recurse, when we encounter a state we haven't yet visited. Furthermore, when we recurse, we add the current state to our set of visited states.

Now, we can run the state transformer and get out only the correct paths, even on the cyclic graphs:

Here, the empty list provided as an argument to  is the initial state (i.e., the initial visited list). In our case, it is empty.

We can also provide an  method that, instead of returning a result, returns the final state. This function looks like:

execStateT :: Monad m => StateT s m a -> s -> m s execStateT (StateT m) state = do (s', a) <- m state return s' This is not so useful in our case, as it will return exactly the reverse of  (try it and find out!), but can be useful in general (if, for instance, we need to know how many numbers are used in ).

Parsing Monads
It turns out that a certain class of parsers are all monads. This makes the construction of parsing libraries in Haskell very clean. In this chapter, we begin by building our own (small) parsing library in the section on A Simple Parsing Monad and then, in the final section, introduce the Parsec parsing library.

A Simple Parsing Monad
Consider the task of parsing. A simple parsing monad is much like a state monad, where the state is the unparsed string. We can represent this exactly as:

newtype Parser a = Parser { runParser :: String -> Either String (String, a) } We again use  to be an error condition. This yields standard instances of  and  :

instance Monad Parser where return a = Parser (\xl -> Right (xl,a)) fail  s = Parser (\xl -> Left  s)    Parser m >>= k = Parser $ \xl -> case m xl of       Left  s -> Left s        Right (xl', a) -> let Parser n = k a           in  n xl'

instance MonadPlus Parser where mzero = Parser (\xl -> Left "mzero") Parser p `mplus` Parser q = Parser $ \xl -> case p xl of       Right a -> Right a        Left  err -> case q xl of                       Right a -> Right a                       Left  _ -> Left err Now, we want to build up a library of parsing "primitives." The most basic primitive is a parser that will read a specific character. This function looks like:

char :: Char -> Parser Char char c = Parser char' where char' [] = Left ("expecting " ++ show c ++                          " got EOF") char' (x:xs) | x == c   = Right (xs, c)              | otherwise = Left  ("expecting " ++                                   show c ++ " got " ++                                   show x) Here, the parser succeeds only if the first character of the input is the expected character.

We can use this parser to build up a parser for the string "Hello":

helloParser :: Parser String helloParser = do char 'H'  char 'e'  char 'l'  char 'l'  char 'o'  return "Hello" This shows how easy it is to combine these parsers. We don't need to worry about the underlying string -- the monad takes care of that for us. All we need to do is combine these parser primitives. We can test this parser by using  and by supplying input:

We can have a slightly more general function, which will match any character fitting a description:

matchChar :: (Char -> Bool) -> Parser Char matchChar c = Parser matchChar' where matchChar' [] = Left ("expecting char, got EOF") matchChar' (x:xs) | c x      = Right (xs, x)              | otherwise = Left ("expecting char, got " ++                       show x) Using this, we can write a case-insensitive "Hello" parser:

ciHelloParser = do c1 <- matchChar (`elem` "Hh") c2 <- matchChar (`elem` "Ee") c3 <- matchChar (`elem` "Ll") c4 <- matchChar (`elem` "Ll") c5 <- matchChar (`elem` "Oo") return [c1,c2,c3,c4,c5] Of course, we could have used something like, but the above implementation works just as well. We can test this function:

Finally, we can have a function, which will match any character:

anyChar :: Parser Char anyChar = Parser anyChar' where anyChar' []    = Left ("expecting character, got EOF") anyChar' (x:xs) = Right (xs, x) On top of these primitives, we usually build some combinators. The combinator, for instance, will take a parser that parses entities of type  and will make it into a parser that parses entities of type  (this is a Kleene-star operator):

many :: Parser a -> Parser [a] many (Parser p) = Parser many' where many' xl = case p xl of               Left  err -> Right (xl, []) Right (xl',a) -> let Right (xl'', rest) = many' xl' in Right (xl'', a:rest) The idea here is that first we try to apply the given parser,. If this fails, we succeed but return the empty list. If succeeds, we recurse and keep trying to apply   until it fails. We then return the list of successes we've accumulated.

In general, there would be many more functions of this sort, and they would be hidden away in a library, so that users couldn't actually look inside the  type. However, using them, you could build up, for instance, a parser that parses (non-negative) integers:

int :: Parser Int int = do t1 <- matchChar isDigit tr <- many (matchChar isDigit) return (read (t1:tr)) In this function, we first match a digit (the  function comes from the module  / ) and then match as many more digits as we can. We then  the result and return it. We can test this parser as before:

Now, suppose we want to parse a Haskell-style list of s.  This becomes somewhat difficult because, at some point, we're either going to parse a comma or a close brace, but we don't know when this will happen. This is where the fact that  is an instance of  comes in handy: first we try one, then we try the other.

Consider the following code:

intList :: Parser [Int] intList = do char '[' intList' `mplus` (char ']' >> return []) where intList' = do           i <- int r <- (char ',' >> intList') `mplus` (char ']' >> return []) return (i:r) The first thing this code does is parse and open brace. Then, using , it tries one of two things: parsing using , or parsing a close brace and returning an empty list.

The  function assumes that we're not yet at the end of the list, and so it first parses an int. It then parses the rest of the list. However, it doesn't know whether we're at the end yet, so it again uses. On the one hand, it tries to parse a comma and then recurse; on the other, it parses a close brace and returns the empty list. Either way, it simply prepends the int it parsed itself to the beginning.

One thing that you should be careful of is the order in which you supply arguments to. Consider the following parser:

tricky = mplus (string "Hal") (string "Hall") You might expect this parser to parse both the words "Hal" and "Hall;" however, it only parses the former. You can see this with:

This is because it tries to parse "Hal," which succeeds, and then it doesn't bother trying to parse "Hall."

You can attempt to fix this by providing a parser primitive, which detects end-of-file (really, end-of-string) as:

eof :: Parser eof = Parser eof' where eof' [] = Right ([], ) eof' xl = Left ("Expecting EOF, got " ++                         show (take 10 xl)) You might then rewrite  using   as:

tricky2 = do s <- mplus (string "Hal") (string "Hall") eof return s But this also doesn't work, as we can easily see:

This is because, again, the  doesn't know that it needs to parse the whole input. So, when you provide it with "Hall," it parses just "Hal" and leaves the last "l" lying around to be parsed later. This causes  to produce an error message.

The correct way to implement this is:

tricky3 = mplus (do s <- string "Hal"           eof            return s)        (do s <- string "Hall"            eof            return s) We can see that this works:

This works precisely because each side of the  knows that it must read the end.

In this case, fixing the parser to accept both "Hal" and "Hall" was fairly simple, due to the fact that we assumed we would be reading an end-of-file immediately afterwards. Unfortunately, if we cannot disambiguate immediately, life becomes significantly more complicated. This is a general problem in parsing, and has little to do with monadic parsing. The solution most parser libraries (e.g., Parsec, see the section on Parsec) have adopted is to only recognize "LL(1)" grammars: that means that you must be able to disambiguate the input with a one token look-ahead.

Given this monadic parser, it is fairly easy to add information regarding source position. For instance, if we're parsing a large file, it might be helpful to report the line number on which an error occurred. We could do this simply by extending the  type and by modifying the instances and the primitives:

newtype Parser a = Parser { runParser :: Int -> String -> Either String (Int, String, a) }

instance Monad Parser where return a = Parser (\n xl -> Right (n,xl,a)) fail  s = Parser (\n xl -> Left  (show n ++ ": " ++ s)) Parser m >>= k = Parser $ \n xl -> case m n xl of     Left  s -> Left s      Right (n', xl', a) -> let Parser m2 = k a         in  m2 n' xl'

instance MonadPlus Parser where mzero = Parser (\n xl -> Left "mzero") Parser p `mplus` Parser q = Parser $ \n xl -> case p n xl of     Right a -> Right a      Left  err -> case q n xl of                     Right a -> Right a                     Left  _ -> Left err

matchChar :: (Char -> Bool) -> Parser Char matchChar c = Parser matchChar' where matchChar' n [] = Left ("expecting char, got EOF") matchChar' n (x:xs) | c x      = Right (n+if x=='\n' then 1 else 0                  , xs, x)            | otherwise = Left ("expecting char, got " ++                     show x) The definitions for   and   are not given, since they can be written in terms of. The function needs to be modified only to include the new state.

Now, when we run a parser and there is an error, it will tell us which line number contains the error:

We can use the  parser from the prior exercise to see that this does in fact work:

We can see that the line number, on which the error occurs, increases as we add additional newlines before the erroneous "a".

Parsec
As you continue developing your parser, you might want to add more and more features. Luckily, Graham Hutton and Daan Leijen have already done this for us in the Parsec library. This section is intended to be an introduction to the Parsec library; it by no means covers the whole library, but it should be enough to get you started.

Like our library, Parsec provides a few basic functions to build parsers from characters. These are:, which is the same as our  ;  , which is the same as our ; , which is the same as our ; , which takes a list of  s and matches any of them; and , which is the opposite of.

The primary function Parsec uses to run a parser is . However, in addition to a parser, this function takes a string that represents the name of the file you're parsing. This is so it can give better error messages. We can try parsing with the above functions:

Here, we can see a few differences between our parser and Parsec: first, the rest of the string isn't returned when we run. Second, the error messages produced are much better.

In addition to the basic character parsing functions, Parsec provides primitives for:, which is the same as ours; which parses a single space; , which parses a letter; , which parses a digit; , which is the same as ours; and a few others.

We can write our  and   functions in Parsec as:

int :: CharParser st Int int = do i1 <- digit ir <- many digit return (read (i1:ir))

intList :: CharParser st [Int] intList = do char '[' intList' `mplus` (char ']' >> return []) where intList' = do           i <- int r <- (char ',' >> intList') `mplus` (char ']' >> return []) return (i:r) First, note the type signatures. The  type variable is simply a state variable that we are not using. In the  function, we use the   function (built in to Parsec) together with the function (also built in to Parsec). The function is actually identical to the one we wrote before.

Note, however, that using  explicitly is not the preferred method of combining parsers: Parsec provides a  function that is a synonym of, but that looks nicer:

intList :: CharParser st [Int] intList = do char '[' intList' <|> (char ']' >> return []) where intList' = do           i <- int r <- (char ',' >> intList') <|> (char ']' >> return []) return (i:r) We can test this:

In addition to these basic combinators, Parsec provides a few other useful ones:

 * takes a list of parsers and performs an or operation between all of them.

 * takes a default value of type  and a parser that returns something of type  .  It then tries to parse with the parser, but it uses the default value as the return, if the parsing fails.

 * takes a parser that returns  and optionally runs it.

 * takes three parsers: an open parser, a close parser and a between parser. It runs them in order and returns the value of the between parser.  This can be used, for instance, to take care of the brackets on our   parser.

 * takes a parser and returns one that succeeds only if the given parser would have failed.

Suppose we want to parse a simple calculator language that includes only plus and times. Furthermore, for simplicity, assume each embedded expression must be enclosed in parentheses. We can give a datatype for this language as:

data Expr = Value Int | Expr :+: Expr | Expr :*: Expr deriving (Eq, Ord, Show) And then write a parser for this language as:

parseExpr :: Parser Expr parseExpr = choice [ do i <- int; return (Value i), between (char '(') (char ')') $ do      e1 <- parseExpr op <- oneOf "+*" e2 <- parseExpr case op of       '+' -> return (e1 :+: e2) '*' -> return (e1 :*: e2) ]

Here, the parser alternates between two options (we could have used, but I wanted to show the  combinator in action). The first simply parses an int and then wraps it up in the constructor. The second option uses  to parse text between parentheses. What it parses is first an expression, then one of plus or times, then another expression. Depending on what the operator is, it returns either  or.

We can modify this parser, so that instead of computing an , it simply computes the value:

parseValue :: Parser Int parseValue = choice [int ,between (char '(') (char ')') $ do    e1 <- parseValue op <- oneOf "+*" e2 <- parseValue case op of      '+' -> return (e1 + e2) '*' -> return (e1 * e2) ]

We can use this as:

Now, suppose we want to introduce bindings into our language. That is, we want to also be able to say "let x = 5 in" inside of our expressions and then use the variables we've defined. In order to do this, we need to use the and  (or ) functions built in to Parsec.

parseValueLet :: CharParser (FiniteMap Char Int) Int parseValueLet = choice [ int , do string "let " c <- letter char '=' e <- parseValueLet string " in " updateState (\fm -> addToFM fm c e)      parseValueLet , do c <- letter fm <- getState case lookupFM fm c of        Nothing -> unexpected ("variable " ++ show c ++                                " unbound") Just i -> return i , between (char '(') (char ')') $ do      e1 <- parseValueLet op <- oneOf "+*" e2 <- parseValueLet case op of       '+' -> return (e1 + e2) '*' -> return (e1 * e2) ]

The  and recursive cases remain the same. We add two more cases, one to deal with let-bindings, the other to deal with usages.

In the let-bindings case, we first parse a "let" string, followed by the character we're binding (the  function is a Parsec primitive that parses alphabetic characters), followed by its value (a ). Then, we parse the " in " and update the state to include this binding. Finally, we continue and parse the rest.

In the usage case, we simply parse the character and then look it up in the state. However, if it doesn't exist, we use the Parsec primitive  to report an error.

We can see this parser in action using the command, which enables us to provide an initial state:

Note that the bracketing does not affect the definitions of the variables. For instance, in the last example, the use of "x" is, in some sense, outside the scope of the definition. However, our parser doesn't notice this, since it operates in a strictly left-to-right fashion. In order to fix this omission, bindings would have to be removed (see the exercises).

title: Yet Another Haskell Tutorial/Monads


text: Yet Another Haskell Tutorial/Io advanced

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


text:
User:Alfmaster~enwikibooks

My name is Igor Habal an I come from Estonia. I study history in Tallinn University.

Did you know that The king of hearts is the only king without a moustache.

title: User:Alfmaster~enwikibooks


text:
Japanese/Dialects/Mikawa

Mikawa-ben (三河弁) is the dialect spoken in Mikawa Province (三河国 mikawa-no kuni), one of the old provinces of the Aichi prefecture (愛知県, Aichi-ken). Mikawa-ben is mainly spoken in western Aichi, while Nagoya-ben is spoken in the eastern half. Mikawa-ben is very similar to Hyojungo.

Vocabulary

 * Jan (じゃん): the dialect form of the Japanese word desu
 * Dara (だら): the dialect form of the Japanese word deshō
 * Rin (りん): the dialect form of the Japanese word shinasai

title: Japanese/Dialects/Mikawa


text:
Eclipse

 * /Using Eclipse/
 * /FAQ/

title: Eclipse


text:
User:EdiTor

Blue just looks cooler, don't ya think? :) .oO( I'm blue, da ba dee da ba di da ba dee da ba ... )

Thanks for your interest! You can mail me, if you like.

And/or, have a laugh!

title: User:EdiTor


text:
Mass Media/History

Johannes Gutenberg, the inventor of movable type, has been called "the most influential man of the millennium."

The first book printed in the colonies was in 1640. The first publisher was Lipincott.

Thomas Jefferson was considered a radical for his defense of Free Speech and opposition to the Alien and Sedition Acts. His criticism became so intense, that his supporters convinced him to prosecute under those same acts.

Justice Oliver Wendell Holmes argued that free speech must be upheld, except in cases of a "clear and present danger." He supported the prosecution of two anti-war socialists, because they discouraged citizens from fighting in World War I.

title: Mass Media/History


text:
Talk:Adventist Youth Honors Answer Book/Health and Science/First Aid, Basic

The "first aid" honors (Red Alert, Basic First Aid, Basic Rescue, Standard First Aid, CPR, and Advanced First Aid) all have a lot of common requirements. There are several recreational honors that require some first aid knowledge as well. In order to get the most bang for the buck, it is best to create small pages for common answers, and then include them in each honor where the requirement is found.

The way I usually do this is by adding a blank page to an honor like this:

Replace "TOPIC" with something appropriate, such as "bleeding" or "burns". Then I click the "Show Preview" (or "Save") button and click on the red link. This creates the page, which I then procede to edit. Finally, go back to the chapters that call out the page, and save them.

If you need to edit a section that has been "included", edit the page as normal - you will only see that the page is called out. At the bottom of the edit page, you should see a "Templates Used" section, and the included page will be listed there. Click on it and edit to your heart's content. Jim Thomas 01:22, 20 December 2006 (UTC)

contributing to the first aid wikibook
I see you have lots of first aid content here. Some of it is out-of-date, and some doesn't fall under the normal definition of Basic First Aid (although you may be using a different definition). Nevertheless, if you'd like to help with the First Aid book, we'd be happy to have you contribute. If you want to update the content on this page, you're welcome to take content from the wikibook, or ask specific questions. Mike.lifeguard 00:14, 24 June 2007 (UTC)

 * The requirements for the AY honors are set by various committees around the world, and we do not have the latitude to change them. Most of the answers given here were taken from a handful of U.S Navy Training Manuals.  I do not mind at all if the answers are updated, or even if the requirements are questioned in the answers themselves.  --Jomegat 02:05, 24 June 2007 (UTC)


text:
User talk:Davidhof

Hi
Will you be helping more with the Hebrew book? I hope so. I responded to your comment about Final Pe. --CocoaZen 02:34, 22 October 2006 (UTC)

title: User talk:Davidhof


text: Template:Hebrew/Aleph-Bet

title: Template:Hebrew/Aleph-Bet


text:
Template:Hebrew/Vocab

Advice for using this template
Use this template for listing Hebrew vocabulary. It has 5 parameters or parts. The first 2 are required. The rest are optional.  —
 * 1) the Hebrew spelling (with diacritic marks, if you can) required
 * 2) translation required
 * 3) part of speech (other notes, person, number, gender) optional
 * 4) phonetic spelling or transliteration optional
 * there can be multiple transliterations because of the way people spell or different dialects and pronounciations
 * 1) notes - including lessons where this vocabulary is introduced optional

title: Template:Hebrew/Vocab


text:
User:Poppafuze

My page.

My other page: Wikipedia:User:Poppafuze aka poppafuze's user page.

Refs
Help:How_does_one_edit_a_page Naming_policy /Subpage on the subject of section heading, featuring the equals sign. /Subpage/ can also be called prettier, if    precedes it, apparently. Slashes auto create uplinkage.
 * 1) /Subpage/ can be pound linked.

title: User:Poppafuze


text:
Bartending/Cocktails/Lady Killer

Recipe for a Lady Killer.

 * 3/10 Pineapple juice
 * 3/10 Passion fruit juice
 * 1/10 Apricot brandy
 * 1/10 Cointreau
 * 2/10 Gin Burnett
 * Garnish with green Mirabeau, sprig of mint and orange peel.

Lady Killer Cocktails/ Lady Killer

title: Bartending/Cocktails/Lady Killer


text:
User:Poppafuze/Subpage

^ Get back! ^ is not the right way. Better get that intro in now, coz here comes the TOC....

=Poppafuze Makes a Subpage= The big one

Two Equals
This right here, we got two of them

Three Equals
In instances of three...

Four Equals
The number four is usually present here, four times, in fours, quadratically.

Five Equals
Oh that actually does something

Six
Six? As in a minor subsection?

=Seven
= Scary number of equals there, no doubt.

title: User:Poppafuze/Subpage


text:
Muggles' Guide to Harry Potter/Characters/Warrington

Overview
Warrington (no first name) appears to be a Chaser in the Slytherin Quidditch team. He is physically largely-built and is two years ahead of Harry at Hogwarts.

Prisoner of Azkaban
Warrington is mentioned as being a Chaser in the Slytherin team and takes part in some Quidditch matches. No other details are given about him.

Goblet of Fire
There is a rumour that Warrington, "the big bloke who looks like a sloth", has put his name in the Goblet of Fire, to try to be a champion in the Triwizard Tournament. The rumour is never confirmed, but at least it gives some indication of his age.

Order of the Phoenix
After Fred and George depart the school, there are a number of attacks against Umbridge's Inquisitorial Squad, of which Warrington is a member. It is mentioned that he goes to the Hospital Wing with a skin condition that makes him look as if he were coated in cornflakes.

When Umbridge catches Harry in her office, where he has been trying to determine whether Sirius has gone to the Ministry, she also sets the Inquisitorial Squad to round up his helpers. Warrington reports that they had also brought Neville, because he interfered when they were trying to bring in Ginny.

Strengths
Warrington is strong and imposing, and as a Chaser on the Slytherin team, must be relatively skilled at Quidditch. As detailed in "Analysis" below, he is also one of the oldest students in the year.

Weaknesses
Warrington, along with the rest of the Squad, are overcome by the small consignment of DA members they are trying to hold in Umbridge's office. Ron's offhand tone seems to suggest this was quite easy.

Relationships with Other Characters
Warrington is familiar with the other members of Slytherin House, the Inquisitorial Squad, and the Slytherin Quidditch team, of which he is a member.

Analysis
Warrington (allegedly) puts his name into the Goblet of Fire, which indicates he must be 17 by this point, yet he is still at Hogwarts in the following year. This suggests that he must have a birthday in the early autumn, before the Goblet was revealed - otherwise he would have graduated by the end of the year, and certainly not be in the Inquisitorial Squad the following year.

Questions

 * 1) How old is Warrington?
 * 2) How long do you think he will be in the Quidditch team for?

Greater Picture
Unlike many of the other teams in the series, the Slytherin Quidditch team appears to have something of a "revolving door" policy when it comes to membership, with players coming and going quite rapidly throughout the five books in which we see Quidditch being played. In his first appearance, Warrington is just another one of those Slytherin Quidditch players, although since the reader has no idea how long he has been on the team for, he may well have been doing this for some time.


text:
Muggles' Guide to Harry Potter/Characters/Bole

Overview
Bole (no first name given) is mentioned as being one of the Beaters in the Slytherin Quidditch team.

Prisoner of Azkaban
Bole is one of two Beaters who attempts to injure Harry Potter in the Slytherin / Gryffindor final. (The other is Derrick.) He is unsuccessful, being out-maneuvered by Harry.

Order of the Phoenix
Angelina Johnson mentions Bole (and Derrick, too) in passing, saying that she always was surprised that Bole and Derrick could make it down to the Quidditch pitch without needing signs.


text:
Muggles' Guide to Harry Potter/Characters/Derrick

Overview
Peregrine Derrick is mentioned as being one of the Beaters in the Slytherin Quidditch team.

Prisoner of Azkaban
Derrick is one of two Beaters who attempts to injure Harry Potter in the Slytherin / Gryffindor final. (The other is Bole.) He is unsuccessful, being out-maneuvered by Harry.

Order of the Phoenix
Angelina Johnson mentions Derrick (and Bole, too) in passing, saying that she always was surprised that Derrick and Bole could make it down to the Quidditch pitch without needing signs.

Weaknesses
Angelina's comments indicate that she does not consider Derrick's intellect to be among the strongest. We can't be certain whether this is true judgement or simple inter-house rivalry, but the "traps" he and Bole try to lay for Harry do seem to be relatively easy for Harry to out-think.


text:
User:Javier Carro/es.wikiversity pages to be undeleted

The next pages have been undeleted in en.wikibooks and they should be imported into es.wikiversity, but due to technical problems it has not been done yet, ( http://bugzilla.wikipedia.org/show_bug.cgi?id=7891 )

Wikiversidad:Fundamentos de química

Wikiversidad:Formulación y nomenclatura en química inorgánica

Wikiversidad:Experimentación Química

Talk:Wikiversidad:Experimentación Química

Wikiversidad:Departamento de Tecnología Electrónica

Wikiversidad:Departamento de Química/Lista de artículos de la wikipedia solicitados

Wikiversidad:Departamento de Química/Lista de artículos de la wikipedia a mejorar

Wikiversidad:Departamento de Química

Wikiversidad:Departamento de Lenguajes y Sistemas Informáticos

Wikiversidad:Departamento de Ciencias de la Computación e Inteligencia Artificial

Wikiversidad:Departamento de Arquitectura y Tecnología de Computadores

Wikiversidad:Curso de Sintaxis transformacional

Wikiversidad:coordinación plurilingüe

Wikiversidad:Biblioteca de Lingüística

Wikiversidad:Área de Traducción

Talk:Wikiversidad:Química para niños

Wikiversidad:Química para niños

Wikiversidad:Química orgánica

Wikiversidad:Química inorgánica

Wikiversidad:Química general

Wikiversidad:Química física

Wikiversidad:Introducción a la química

Wikiversidad:Prácticas de traducción


text:
Yet Another Haskell Tutorial/Recursion

= Recursion and Induction =

Informally, a function is recursive if its definition depends on itself. The prototypical example is factorial, whose definition is:

$$ fact(n) = \begin{cases} 1 & n = 0 \\ n*fact(n-1) & n > 0 \\ \end{cases} $$

Here, we can see that in order to calculate $$fact(5)$$, we need to calculate $$fact(4)$$, but in order to calculate$$fact(4)$$, we need to calculate $$fact(3)$$, and so on.

Recursive function definitions always contain a number of non-recursive base cases and a number of recursive cases. In the case of factorial, we have one of each. The base case is when $$n=0$$ and the recursive case is when $$n>0$$.

One can actually think of the natural numbers themselves as recursive (in fact, if you ask set theorists about this, they'll say this is how it is). That is, there is a zero element and then for every element, it has a successor. That is  and so on forever. We can actually implement this system of natural numbers in Haskell:

data Nat = Zero | Succ Nat This is a recursive type definition. Here, we represent one as and three as. One thing we might want to do is be able to convert back and forth between s and s.  Clearly, we can write a base case as:

natToInt Zero = 0 In order to write the recursive case, we realize that we're going to have something of the form. We can make the assumption that we'll be able to take  and produce an. Assuming we can do this, all we need to do is add one to this result. This gives rise to our recursive case:

natToInt (Succ n) = natToInt n + 1 There is a close connection between recursion and mathematical induction. Induction is a proof technique which typically breaks problems down into base cases and "inductive" cases, very analogous to our analysis of recursion.

Let's say we want to prove the statement $$n! \geq n$$ for all $$n\geq 0$$. First we formulate a base case: namely, we wish to prove the statement when $$n=0$$. When $$n=0$$, $$n!=1$$ by definition. Since $$n!=1>0=n$$, we get that $$0! \geq 0$$ as desired.

Now, suppose that $$n>0$$. Then $$n=k+1$$ for some value $$k$$. We now invoke the inductive hypothesis and claim that the statement holds for $$n=k$$. That is, we assume that $$k! \geq k$$. Now, we use $$k$$ to formate the statement for our value of $$n$$. That is, $$n! \geq n$$ if and only iff $$(k+1)! \geq (k+1)$$. We now apply the definition of factorial and get $$(k+1)! = (k+1)*k!$$. Now, we know $$k! \geq k$$, so $$(k+1)*k! \geq k+1$$ if and only if $$k+1 \geq 1$$. But we know that $$k\geq 0$$, which means $$k+1 \geq 1$$. Thus it is proven.

It may seem a bit counter-intuitive that we are assuming that the claim is true for $$k$$ in our proof that it is true for $$n$$. You can think of it like this: we've proved the statement for the case when $$n=0$$. Now, we know it's true for $$n=0$$ so using this we use our inductive argument to show that it's true for $$n=1$$. Now, we know that it is true for $$n=1$$ so we reuse our inductive argument to show that it's true for $$n=2$$. We can continue this argument as long as we want and then see that it's true for all $$n$$.

It's much like pushing down dominoes. You know that when you push down the first domino, it's going to knock over the second one. This, in turn will knock over the third, and so on. The base case is like pushing down the first domino, and the inductive case is like showing that pushing down domino $$k$$ will cause the $$k+1$$st domino to fall.

In fact, we can use induction to prove that our  function does the right thing. First we prove the base case: does  evaluate to $$0$$? Yes, obviously it does. Now, we can assume that  evaluates to the correct value (this is the inductive hypothesis) and ask whether   produces the correct value. Again, it is obvious that it does, by simply looking at the definition.

Let's consider a more complex example: addition of s.  We can write this concisely as:

addNat Zero m = m addNat (Succ n) m = addNat n (Succ m) Now, let's prove that this does the correct thing. First, as the base case, suppose the first argument is. We know that $$0+m = m$$ regardless of what $$m$$ is; thus in the base case the algorithm does the correct thing. Now, suppose that  does the correct thing for all  and we want to show that does the correct thing. We know that $$(n+1) + m = n + (m+1)$$ and thus since  does the correct thing (by the inductive hypothesis), our program is correct.

title: Yet Another Haskell Tutorial/Recursion


text:
Yet Another Haskell Tutorial/Complexity

= Brief Complexity Theory =

Complexity Theory is the study of how long a program will take to run, depending on the size of its input. There are many good introductory books to complexity theory and the basics are explained in any good algorithms book. I'll keep the discussion here to a minimum.

The idea is to say how well a program scales with more data. If you have a program that runs quickly on very small amounts of data but chokes on huge amounts of data, it's not very useful (unless you know you'll only be working with small amounts of data, of course). Consider the following Haskell function to return the sum of the elements in a list:

sum [] = 0 sum (x:xs) = x + sum xs How long does it take this function to complete? That's a very difficult question; it would depend on all sorts of things: your processor speed, your amount of memory, the exact way in which the addition is carried out, the length of the list, how many other programs are running on your computer, and so on. This is far too much to deal with, so we need to invent a simpler model. The model we use is sort of an arbitrary "machine step." So the question is "how many machine steps will it take for this program to complete?" In this case, it only depends on the length of the input list.

If the input list is of length $$0$$, the function will take either $$0$$ or $$1$$ or $$2$$ or some very small number of machine steps, depending exactly on how you count them (perhaps $$1$$ step to do the pattern matching and $$1$$ more to return the value $$0$$). What if the list is of length $$1$$. Well, it would take however much time the list of length $$0$$ would take, plus a few more steps for doing the first (and only element).

If the input list is of length $$n$$, it will take however many steps an empty list would take (call this value $$y$$) and then, for each element it would take a certain number of steps to do the addition and the recursive call (call this number $$x$$). Then, the total time this function will take is $$nx+y$$ since it needs to do those additions $$n$$ many times. These $$x$$ and $$y$$ values are called ''constant values'', since they are independent of $$n$$, and actually dependent only on exactly how we define a machine step, so we really don't want to consider them all that important. Therefore, we say that the complexity of this  function is $$\mathcal{O}(n)$$ (read "order $$n$$"). Basically saying something is $$\mathcal{O}(n)$$ means that for some constant factors $$x$$ and $$y$$, the function takes $$nx+y$$ machine steps to complete.

Consider the following sorting algorithm for lists (commonly called "insertion sort"):

sort [] = [] sort [x] = [x] sort (x:xs) = insert (sort xs) where insert [] = [x] insert (y:ys) | x <= y   = x : y : ys                        | otherwise = y : insert ys The way this algorithm works is as follow: if we want to sort an empty list or a list of just one element, we return them as they are, as they are already sorted. Otherwise, we have a list of the form . In this case, we sort   and then want to insert in the appropriate location. That's what the function does. It traverses the now-sorted tail and inserts wherever it naturally fits.

Let's analyze how long this function takes to complete. Suppose it takes $$f(n)$$ stepts to sort a list of length $$n$$. Then, in order to sort a list of $$n$$-many elements, we first have to sort the tail of the list first, which takes $$f(n-1)$$ time. Then, we have to insert into this new list. If  has to go at the end, this will take $$\mathcal{O}(n-1)=\mathcal{O}(n)$$ steps. Putting all of this together, we see that we have to do $$\mathcal{O}(n)$$ amount of work $$\mathcal{O}(n)$$ many times, which means that the entire complexity of this sorting algorithm is $$\mathcal{O}(n^2)$$. Here, the squared is not a constant value, so we cannot throw it out.

What does this mean? Simply that for really long lists, the function won't take very long, but that the  function will take quite some time. Of course there are algorithms that run much more slowly that simply $$\mathcal{O}(n^2)$$ and there are ones that run more quickly than $$\mathcal{O}(n)$$.

Consider the random access functions for lists and arrays. In the worst case, accessing an arbitrary element in a list of length $$n$$ will take $$\mathcal{O}(n)$$ time (think about accessing the last element). However with arrays, you can access any element immediately, which is said to be in constant time, or $$\mathcal{O}(1)$$, which is basically as fast an any algorithm can go.

There's much more in complexity theory than this, but this should be enough to allow you to understand all the discussions in this tutorial. Just keep in mind that $$\mathcal{O}(1)$$ is faster than $$\mathcal{O}(n)$$ is faster than $$\mathcal{O}(n^2)$$, etc.

title: Yet Another Haskell Tutorial/Complexity


text:
User talk:Hunterbears

Paleolithic Art

Paleolithic Cave Paintings

Paleolithic Venus Figurines

Mesolithic Art

title: User talk:Hunterbears


text:
Harmonica/Recording

As of now, there are no detail Wikibooks on home recording, but I will just go with what I have:

With the advent of computers, it's entirely possible to do multitrack recording right at the comfort of the home, with only additional equipment of a mic and a good software then can cost less than $20.

Microphone
If you have a bullet mic, cool — but you don't really need something that expensive. The one that I used is a simple uni-directional moving coil (dynamic) mic, with the impedance of 600 ohm. The key point here is mainly the direction of the mic: it's uni-directional, which captures only the sound of the harmonica.

Lapel mic is not a bad choice, but do watch out that it's omnidirectional, making it suspectible to outside noise. Also, it's common for it to use poor quality wiring, making it suspectible to statics — and your normal home computer (not one designed specifically for recording) generally generates lots of statics.

Software
The few good software that can be used are as follows: I would recommend Audacity if possible. Yes, I do know that Audacity is not perfect, and many commercial software ARE better. However, there are a few reasons why I would recommend Audacity: Get version 1.3.2b. for the most part, it is stable enough. The user manual for Audacity is located at here.
 * DK Hit Kit ($15 CDN). Cheap, comes with a lite version of emagic Logic. Can edit 8 audio track and 16 midi track. Comes with a good quality mic too, easily the price of the Hit Kit itself. For Win and OS X.
 * Audacity: Released under the GNU GPL (meaning free and libre). As many audio tracks as your computer can handle, and have lots of effects and plugin. For Windows, OS X, Linux, BSD, and Solaris.
 * Ardour: Released under the GNU GPL (meaning free and libre). 64 audio tracks and 16 MIDI tracks available. For Linux and OS X
 * Dyne:bolic Multimedia oriented LiveCD Linux that includes Audacity, Ardour, drum machine, and audio streaming engine, as well as tools to edit videos. Version 1.4.1 Can run on any 586+ PC (with CD reader) with 64mb RAM and X-Box; version 2.2 can run on most computer made within last 2 years.
 * 1) It's free and libre, and suitable for home recording... and semi-professional graded too if needed
 * 2) It can be used for any operating system, not just Windows or Linux or Mac. This allow any computers that have Audacity program to open Audacity project files, without the need for a Live CD (which is useless on a Mac, as far as i know).

Recording tips, and other ideas

 * Holding the mic will introduce handling noise.
 * Since Audacity Project file retain information such as separate track, it allows collaborations of musicians who may not have met; instead of merely sending numerous dissatisfactory setted audio files that cannot be edited properly, musicians can send the project and associated audio files, and can listen and decide what to keep, and etc.
 * A further extension would be "chain-letter jamming", where, one musician record a track and pass it down, and keep going among the circle.

title: Harmonica/Recording


text:
User:Wj32

Books I've worked on

 * X86 Assembly - Added some IDT and GDT code plus some examples...
 * X86 Disassembly - Fixed some misinformation
 * C Sharp Programming - See below
 * Windows Programming - Rewrite of User Mode vs Kernel Mode.

title: User:Wj32


text:
Talk:Windows Programming/Key Combinations

shift+del will permanent delete it will not go to recyclebin


text:
User:Tannertsf/Historical Documents

 * /Pre 18th Century/
 * /18th Century/
 * /19th Century/
 * /20th Century/
 * /21st Century/
 * /Major Collections/
 * /Glossary/

title: User:Tannertsf/Historical Documents


text:
Yet Another Haskell Tutorial/Language basics/Solutions

Arithmetic
It binds more tightly; actually, function application binds more tightly than anything else. To see this, we can do something like:

If multiplication bound more tightly, the result would have been 3.

Pairs, Triples and More
Solution:. This is because first we want to take the first half the tuple:  and then out of this we want to take the second half, yielding just.

If you tried  you will have gotten a type error. This is because the application of  will leave you with. However, the string "foo" isn't a tuple, so you cannot apply  to it.

Simple List Functions
Solution:

Solution:

Solution:.

You could also use. The foldr case is easier to explain: we replace each cons with an application of  and the empty list with 0. Thus, the inner-most application will take the maximum of 0 and the last element of the list (if it exists). Then, the next-most inner application will return the maximum of whatever was the maximum before and the second-to-last element. This will continue on, carrying to current maximum all the way back to the beginning of the list.

In the foldl case, we can think of this as looking at each element in the list in order. We start off our "state" with 0. We pull off the first element and check to see if it's bigger than our current state. If it is, we replace our current state with that number and the continue. This happens for each element and thus eventually returns the maximal element.

Solution:

Recursion
We can define a fibonacci function as:

fib 1 = 1 fib 2 = 1 fib n = fib (n-1) + fib (n-2) We could also write it using explicit if statements, like:

fib n = if n == 1 || n == 2 then 1 else fib (n-1) + fib (n-2) Either is acceptable, but the first is perhaps more natural in Haskell.

We can define:

$$ a*b = \begin{cases} - ( a*(-b) ) & b < 0 \\ 0 & b = 0 \\ a & b = 1 \\ a + a*(b-1) & \mbox{otherwise} \\ \end{cases} $$

And then type out code:

mult a 0 = 0 mult a 1 = a mult a b = if b < 0 then 0 - mult a (-b) else a + mult a (b-1) Note that it doesn't matter that of $$a$$ and $$b$$ we do the recursion on. We could just as well have defined it as:

mult 0 b = 0 mult 1 b = b mult a b = if a < 0 then 0 - mult (-a) b       else b + mult (a-1) b

We can define  as:

my_map f [] = [] my_map f (x:xs) = f x : my_map f xs Recall that the  function is supposed to apply a function to every element in the list. In the case that the list is empty, there are no elements to apply the function to, so we just return the empty list.

In the case that the list is non-empty, it is an element followed by a list. Assuming we've already properly applied to, then all we're left to do is apply   to  and then stick the results together. This is exactly what the second line does.

Interactivity
The code below appears in. The only tricky parts are the recursive calls in  and.

module Main where

import System.IO

main = do nums <- getNums putStrLn ("The sum is " ++ show (sum nums)) putStrLn ("The product is " ++ show (product nums)) showFactorials nums

getNums = do putStrLn "Give me a number (or 0 to stop):" num <- getLine if read num == 0 then return [] else do rest <- getNums return ((read num :: Int):rest)

showFactorials []    = return showFactorials (x:xs) = do putStrLn (show x ++ " factorial is " ++            show (factorial x)) showFactorials xs

factorial 1 = 1 factorial n = n * factorial (n-1) The idea for  is just as spelled out in the hint. For , we consider first the recursive call. Suppose we have a list of numbers, the first of which is. First we print out the string showing the factorial. Then we print out the rest, hence the recursive call. But what should we do in the case of the empty list? Clearly we are done, so we don't need to do anything at all, so we simply.

Note that this must be  instead of just   because if we simply wrote  then this wouldn't be an IO action, as it needs to be. For more clarification on this, you should probably just keep reading the tutorial.


text:
Yet Another Haskell Tutorial/Type basics/Solutions

Simple Types

 * 1)    or
 * 2)  type error: lists are homogenous
 * 3)   {a}
 * 4)  type error: cannot add values of different types
 * 1)  type error: cannot add values of different types

Polymorphic Types
The types:

Functional Arguments
The types:

 * 1)   .  This function takes an element and returns the list containing only that element.
 * 2)   .  The second and third argument must be of the same type, since they go into the same list.  The first element can be of any type.
 * 3)   .  Since we apply   to , it must be an instance of.
 * , or .  This ignores the first argument, so it can be any type.
 * 1)   .  In this expression,   must be a function which takes a   as an argument.  We don't know anything about what it produces, though, so we call it.
 * 2)  Type error.  Here, we assume   has type  .  But   is applied to itself, so it must have type  .  But then it must have type , but then it must have type   and so on, leading to an infinite type.
 * 3)   .  Again, since we apply , this must be an instance of.

Pairs
The definitions will be something like: data Triple a b c = Triple a b c

tripleFst (Triple x y z) = x tripleSnd (Triple x y z) = y tripleThr (Triple x y z) = z

The code, with type signatures, is: data Quadruple a b = Quadruple a a b b

firstTwo :: Quadruple a b -> [a] firstTwo (Quadruple x y z t) = [x,y]

lastTwo :: Quadruple a b -> [b] lastTwo (Quadruple x y z t) = [z,t] We note here that there are only two type variables,  and associated with.

Multiple Constructors
The code:

data Tuple a b c d = One a                    | Two a b                     | Three a b c                     | Four a b c d

tuple1 (One  a      ) = Just a tuple1 (Two   a b    ) = Just a tuple1 (Three a b c  ) = Just a tuple1 (Four  a b c d) = Just a

tuple2 (One  a      ) = Nothing tuple2 (Two  a b    ) = Just b tuple2 (Three a b c  ) = Just b tuple2 (Four  a b c d) = Just b

tuple3 (One  a      ) = Nothing tuple3 (Two  a b    ) = Nothing tuple3 (Three a b c ) = Just c tuple3 (Four  a b c d) = Just c

tuple4 (One  a      ) = Nothing tuple4 (Two  a b    ) = Nothing tuple4 (Three a b c ) = Nothing tuple4 (Four a b c d) = Just d

The code:

fromTuple :: Tuple a b c d -> Either (Either a (a,b)) (Either (a,b,c) (a,b,c,d)) fromTuple (One  a      ) = Left  (Left  a        ) fromTuple (Two  a b    ) = Left  (Right (a,b)    ) fromTuple (Three a b c ) = Right (Left  (a,b,c)  ) fromTuple (Four a b c d) = Right (Right (a,b,c,d)) Here, we use embedded s to represent the fact that there are four (instead of two) options.

Recursive Datatypes
The code:

listHead (Cons x xs) = x listTail (Cons x xs) = xs

listFoldl f y Nil = y listFoldl f y (Cons x xs) = listFoldl f (f y x) xs

listFoldr f y Nil = y listFoldr f y (Cons x xs) = f x (listFoldr f y xs)

Binary Trees
The code: elements (Leaf x) = [x] elements (Branch lhs x rhs) = elements lhs ++ [x] ++ elements rhs

The code:

treeFoldr :: (a -> b -> b) -> b -> BinaryTree a -> b treeFoldr f i (Leaf x) = f x i treeFoldr f i (Branch left x right) = treeFoldr f (f x (treeFoldr f i right)) left

elements2 = treeFoldr []

or:

elements2 tree = treeFoldr (\a b -> a:b) [] tree The first  is simply a more compact version of the second.

The code: treeFoldl :: (a -> b -> a) -> a -> BinaryTree b -> a treeFoldl f i (Leaf x) = f i x treeFoldl f i (Branch left x right) = treeFoldl f (f (treeFoldl f i left) x) right

elements3 t = treeFoldl (\i a -> i ++ [a]) [] t

Continuation Passing Style
It mimicks neither exactly. Its behavior most closely resembles , but differs slightly in its treatment of the initial value. We can observe the difference in an interpreter:

Clearly it behaves differently. By writing down the derivations of and   we can see exactly where they diverge:

foldr (-) 0 [1,2,3] ==> 1 - foldr (-) 0 [2,3] ==> ... ==>  1 - (2 - (3 - foldr (-) 0 [])) ==> 1 - (2 - (3 - 0)) ==>  2

fold (-) 0 [1,2,3] ==> fold' (-) (\y -> 0 - y) [1,2,3] ==> 0 - fold' (-) (\y -> 1 - y) [2,3] ==> 0 - (1 - fold' (-) (\y -> 2 - y) [3]) ==> 0 - (1 - (2 - 3)) ==>  -2 Essentially, the primary difference is that in the   case, the "initial value" is used at the end (replacing ), whereas in the CPS case, the initial value is used at the beginning.

The function  in CPS: map' :: (a -> [b] -> [b]) -> [a] -> [b] map' f [] = [] map' f (x:xs) = f x (map' f xs)

map2 :: (a -> b) -> [a] -> [b] map2 f l = map' (\x y -> f x : y) l Point elimination: map2 f = map' (\x y -> (f x) y) map2 f = map' (\x ->  (f x)) map2 f = map' (\x -> (. f) x) map2 f = map' ( . f)

The function  in CPS: (needs to be double checked) filter' :: (a -> [b] -> [b]) -> [a] -> [b] filter' f [] = [] filter' f (x:xs) = f x (filter' f xs)

filter2 :: (a -> Bool) -> [a] -> [a] filter2 f l = filter' (\x y -> if (f x) then x:y else y) l


text:
Yet Another Haskell Tutorial/Io/Solutions

Actions
Using if, we get something like:

main = do hSetBuffering stdin LineBuffering putStrLn "Please enter your name:" name <- getLine if name == "Simon" || name == "John" || name == "Phil" then putStrLn "Haskell is great!" else if name == "Koen" then putStrLn "Debugging Haskell is fun!" else putStrLn "I don't know who you are." Note that we don't need to repeat the dos inside the ifs, since these are only one action commands.

We could also be a bit smarter and use the  command which is built in to the Prelude:

main = do hSetBuffering stdin LineBuffering putStrLn "Please enter your name:" name <- getLine if name `elem` ["Simon", "John", "Phil"] then putStrLn "Haskell is great!" else if name == "Koen" then putStrLn "Debugging Haskell is fun!" else putStrLn "I don't know who you are." Of course, we needn't put all the s inside the if statements. We could instead write:

main = do hSetBuffering stdin LineBuffering putStrLn "Please enter your name:" name <- getLine putStrLn (if name `elem` ["Simon", "John", "Phil"]      then "Haskell is great!"       else if name == "Koen"              then "Debugging Haskell is fun!"              else "I don't know who you are.")

Using case, we get something like:

main = do hSetBuffering stdin LineBuffering putStrLn "Please enter your name:" name <- getLine case name of   "Simon" -> putStrLn "Haskell is great!" "John" -> putStrLn "Haskell is great!" "Phil" -> putStrLn "Haskell is great!" "Koen" -> putStrLn "Debugging Haskell is fun!" _      -> putStrLn "I don't know who you are." Which, in this case, is actually not much cleaner.

A File Reading Program
The code might look something like:

module DoFile where

import IO

main = do hSetBuffering stdin LineBuffering putStrLn "Do you want to [read] a file, ...?" cmd <- getLine case cmd of   "quit"  -> do putStrLn ("Goodbye!") return "read" -> do doRead; main "write" -> do doWrite; main _      -> do putStrLn ("I don't understand the command "                    ++ cmd ++ ".") main

doRead = do putStrLn "Enter a file name to read:" fn <- getLine bracket (openFile fn ReadMode) hClose (\h -> do txt <- hGetContents h                   putStrLn txt)

doWrite = do putStrLn "Enter a file name to write:" fn <- getLine bracket (openFile fn WriteMode) hClose (\h -> do putStrLn                     "Enter text (dot on a line by itself to end):"                    writeLoop h)

writeLoop h = do l <- getLine if l == "." then return else do hPutStrLn h l           writeLoop h The only interesting things here are the calls to , which ensure the that the program lives on, regardless of whether there's a failure or not; and the  function. Note that we need to pass the handle returned by  (through   to this function, so it knows where to write the input to).

Alternatively, we can make a version with  and   that doesn't use  : doRead = do putStrLn "Enter a file name to read:" fn <- getLine txt <- readFile fn putStr txt

doWrite = do putStrLn "Enter a file name to write:" fn <- getLine txt <- getWriteLines writeFile fn txt

getWriteLines = do l <- getLine if l == "." then return "" else do lines <- getWriteLines return (line++"\n"++lines)


text: Yet Another Haskell Tutorial/Modules/Solutions


text:
Yet Another Haskell Tutorial/Language advanced/Solutions

Partial Application
Function  cannot be converted into point-free style. The others look something like: func1 x = map (*x)

func2 f g = filter f. map g

func4 = map (+2). filter (`elem` [1..10]). (5:)

func5 = flip foldr 0. flip. curry

You might have been tempted to try to write  as , trying to eta-reduce off the. In this case, this isn't possible. This is because the function composition operator has type. In this case, we're trying to use  as the second argument. But takes two arguments, while  expects a function which takes only one.

The Final Word on Lists
We can start out with a recursive definition:

and [] = True and (x:xs) = x && and xs From here, we can clearly rewrite this as:

and = foldr (&&) True

We can write this recursively as:

concatMap f [] = [] concatMap f (x:xs) = f x ++ concatMap f xs This hints that we can write this as:

concatMap f = foldr (\a b -> f a ++ b) [] Now, we can do point elimination to get:

foldr (\a b -> f a ++ b) [] ==> foldr (\a b -> (++) (f a) b) [] ==> foldr (\a -> (++) (f a)) [] ==> foldr (\a -> ((++). f) a) [] ==> foldr ((++) . f) []


text: Yet Another Haskell Tutorial/Type advanced/Solutions


text:
Yet Another Haskell Tutorial/Monads/Solutions

Common Monads
The first law is:  ≡. In the case of, we get:

return a >>= f ==> Just a   >>= \x -> f x ==>  (\x -> f x) a ==>  f a The second law is:   ≡. Here, we get:

f >>= return ==> f >>= \x -> return x ==>  f >>= \x -> Just x At this point, there are two cases depending on whether   is  or not. In the first case, we get:

==> Nothing >>= \x -> Just x ==>  Nothing ==> f In the second case,   is. Then, we get:

==> Just a >>= \x -> Just x ==>  (\x -> Just x) a ==>  Just a ==>  f And the second law is shown. The third law states:  ≡.

If  is , then the left-hand-side clearly reduces to .  The right-hand-side reduces to   which in turn reduces to, so they are the same.

Suppose  is. Then the LHS reduces to and the RHS reduces to   which in turn reduces to, so these two are the same.

The idea is that we wish to use the  constructor to represent errors on the  constructor to represent successes. This leads to an instance declaration like:

instance Monad (Either String) where return x     = Right x    Left  s >>= _ = Left s    Right x >>= f = f x    fail  s       = Left s If we try to use this monad to do search, we get:

which is exactly what we want.

MonadPlus
The order to  essentially determins the search order. When the recursive call to  comes first, we are doing depth-first search. When the recursive call to  comes first, we are doing breadth-first search. Thus, using the list monad, we expect the solutions to come in the other order:

Just as we expected.

Monad Transformers
This is a very difficult problem; if you found that you were stuck immediately, please just read as much of this solution as you need to try it yourself.

First, we need to define a list transformer monad. This looks like:

newtype ListT m e = ListT { unListT :: m [e] } The  constructor simply wraps a monadic action (in monad ) which returns a list.

We now need to make this a monad:

instance Monad m => Monad (ListT m) where return x = ListT (return [x]) fail  s = ListT (return [] ) ListT m >>= k = ListT $ do     l  <- m      l' <- mapM (unListT . k) l      return (concat l')

Here, success is designated by a monadic action which returns a singleton list. Failure (like in the standard list monad) is represented by an empty list: of course, it's actually an empty list returned from the enclosed monad. Binding happens essentially by running the action which will result in a list. This has type . We now need to apply   to each of these elements (which will result in something of type .  We need to get rid of the  s around this (by using  ) and then concatenate them to make a single list.

Now, we need to make it an instance of

instance Monad m => MonadPlus (ListT m) where mzero = ListT (return []) ListT m1 `mplus` ListT m2 = ListT $ do     l1 <- m1      l2 <- m2      return (l1 ++ l2)

Here, the zero element is a monadic action which returns an empty list. Addition is done by executing both actions and then concatenating the results.

Finally, we need to make it an instance of :

instance MonadTrans ListT where lift x = ListT (do a <- x; return [a]) Lifting an action into  simply involves running it and getting the value (in this case, ) out and then returning the singleton list.

Once we have all this together, writing  is fairly straightforward:

searchAll6 g@(Graph vl el) src dst | src == dst = do     lift $ putStrLn $ "Exploring " ++ show src ++ " -> " ++ show dst return [src] | otherwise = do      lift $ putStrLn $ "Exploring " ++ show src ++ " -> " ++ show dst search' el where search' [] = mzero search' ((u,v,_):es) | src == u = (do path <- searchAll6 g v dst             return (u:path)) `mplus` search' es       | otherwise = search' es The only change (besides changing the recursive call to call  instead of  ) here is that we call with appropriate arguments, lifted into the monad.

If we look at the type of, we see that the result (i.e., after applying a graph and two ints) has type. In theory, we could use this with any appropriate monad transformer; in our case, we want to use . Thus, we can run this by:

This is precisely what we were looking for. This exercise is actually simpler than the previous one. All we need to do is incorporate the calls to  and   into and add an extra lift to the IO calls. This extra lift is required because now we're stacking two transformers on top of IO instead of just one.

searchAll7 g@(Graph vl el) src dst | src == dst = do     lift $ lift $ putStrLn $ "Exploring " ++ show src ++ " -> " ++ show dst visited <- getT putT (src:visited) return [src] | otherwise = do      lift $ lift $ putStrLn $ "Exploring " ++ show src ++ " -> " ++ show dst visited <- getT putT (src:visited) if src `elem` visited then mzero else search' el where search' [] = mzero search' ((u,v,_):es) | src == u = (do path <- searchAll7 g v dst             return (u:path)) `mplus` search' es       | otherwise = search' es The type of this has grown significantly. After applying the graph and two ints, this has type.

Essentially this means that we've got something that's a state transformer wrapped on top of some other arbitrary transformer which itself sits on top of. In our case,  is going to be. Thus, we run this beast by saying:

And it works, even on.

A Simple Parsing Monad
First we write a function  which will parse out whitespaces:

spaces :: Parser spaces = many (matchChar isSpace) >> return Now, using this, we simply sprinkle calls to  through to get :

intListSpace :: Parser [Int] intListSpace = do char '[' spaces intList' `mplus` (char ']' >> return []) where intList' = do           i <- int spaces r <- (char ',' >> spaces >> intList') `mplus` (char ']' >> return []) return (i:r) We can test that this works:

=== Parsec === We do this by replacing the state functions with push and pop functions as follows:

parseValueLet2 :: CharParser (FiniteMap Char [Int]) Int parseValueLet2 = choice [ int , do string "let " c <- letter char '=' e <- parseValueLet2 string " in " pushBinding c e      v <- parseValueLet2 popBinding c      return v , do c  <- letter fm <- getState case lookupFM fm c of        Nothing    -> unexpected ("variable " ++                                   show c ++                                   " unbound") Just (i:_) -> return i, between (char '(') (char ')') $ do      e1 <- parseValueLet2 op <- oneOf "+*" e2 <- parseValueLet2 case op of       '+' -> return (e1 + e2) '*' -> return (e1 * e2) ] where pushBinding c v = do     fm <- getState case lookupFM fm c of       Nothing -> setState (addToFM fm c [v]) Just l -> setState (addToFM fm c (v:l)) popBinding c = do     fm <- getState case lookupFM fm c of       Just [_]   -> setState (delFromFM fm c)        Just (_:l) -> setState (addToFM fm c l)

The primary difference here is that instead of calling , we use two local functions,  and . The   function takes a variable name and a value and adds the value onto the head of the list pointed to in the state. The  function looks at the value and if there is only one element on the stack, it completely removes the stack from the ; otherwise it just removes the first element. This means that if something is in the , the stack is never empty.

This enables us to modify only slightly the usage case; this time, we simply take the top element off the stack when we need to inspect the value of a variable.

We can test that this works: