Archivi Categorie: Haskell

Haskell – 195 – un nuovo tutorial

Riprendo da qui, ma con cose completamente nuove.

Ultimamente ho avuto qualche momento di sconforto con Haskell (e tutto il resto), ma cose passate 😎 probabilmente 😁 forse 😐

Haskell è diverso. E tra i miei conoscenti nessuno lo usa (e se lo nomini tanti ti guardano strano). E anch’io quando devo fare qualcosa uso Python. E ci sarebbe un (grosso) interesse per Rust (alternativo a C++), non è detto che non ci metta le mani; “è maturo?” ho chiesto a un über-rockz che mi ha risposto “diciamo che lo considero ancora un adolescente, però sta crescendo alla svelta“, certo che escono aggiornamenti a scadenza mensile (o quasi, sapete che la mia memoria…).

Tornando a Haskell ho rispolverato i post-its (pizzini) che ho accumulato, eccone una sintesi:

Il corso è stato tenuto da Brent Yorgey che lo presenta così:

An introduction to the design and implementation of modern programming languages, from small domain-specific languages to large-scale general purpose languages. Topics include abstraction, interpreters, compilers, type checking, embedded domain-specific languages, language design as problem-solving strategy and social aspects of language design, adoption, and use. As a final project, each student will create and implement a language of their own design.

Ho sbirciato in qualche doc, random e mi sembra OK, insomma pronto a ripartire 😁

Haskell – 194 – complessità

Continuo da qui, copio qui.

Teoria della complessità – cenni
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 n * x + 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 sum function is O(n) (read “order n”). Basically saying something is O(n) means that for some constant factors x and y, the function takes n * x + 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 x:xs. In this case, we sort xs and then want to insert x in the appropriate location. That’s what the insert function does. It traverses the now-sorted tail and inserts x 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 x into this new list. If x has to go at the end, this will take O(n − 1) = O(n) steps. Putting all of this together, we see that we have to do O(n) amount of work O(n) many times, which means that the entire complexity of this sorting algorithm is O(n2). 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 sum function won’t take very long, but that the sort function will take quite some time. Of course there are algorithms that run much more slowly that simply O(n2) and there are ones that run more quickly than 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 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 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 O(1) is faster than O(n) is faster than O(n2), etc.

Finisce qui il tutorial di Hal Daumé III ma di Haskell ci sono ancora cose da vedere, prossimamente 😐 forse 😁


Haskell – 193 – ricorsione

Continuo da qui, copio qui.

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

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 1=succ(0), 2=succ(1), …, 573=succ(572), … 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 Succ Zero and three as Succ (Succ (Succ Zero)). One thing we might want to do is be able to convert back and forth beween Nats and Ints. 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 Succ n. We can make the assumption that we’ll be able to take n and produce an Int. 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! ≥ n for all n ≥ 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! ≥ 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! ≥ k. Now, we use k to formate the statement for our value of n. That is, n! ≥ n if and only if (k + 1)! ≥ (k + 1). We now apply the definition of factorial and get (k + 1)! = (k + 1) ∗ k!. Now, we know k! ≥ k, so (k + 1) ∗ k! ≥ k + 1 if and only if k + 1 ≥ 1. But we know that k ≥ 0, which means k + 1 ≥ 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 domino to fall.

In fact, we can use induction to prove that our natToInt function does the right thing. First we prove the base case: does natToInt Zero evaluate to 0? Yes, obviously it does. Now, we can assume that natToInt n evaluates to the correct value (this is the inductive hypothesis) and ask whether natToInt (Succ n) 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 Nats. 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 Zero. 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 addNat n m does the correct thing for all m and we want to show that addNat (Succ n) m does the correct thing. We know that (n + 1) + m = n + (m + 1) and thus since addNat n (Succ m) does the correct thing (by the inductive hypothesis), our program is correct.


Haskell – 192 – monadi – 13

Continuo da qui, copio qui.

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: char, which is the same as our char; anyChar, which is the same as our anyChar; satisfy, which is the same as our matchChar; oneOf, which takes a list of Chars and matches any of them; and noneOf, which is the opposite of oneOf.

The primary function Parsec uses to run a parser is parse. 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:

ParsecI> parse (char 'a') "stdin" "a"
Right 'a'
ParsecI> parse (char 'a') "stdin" "ab"
Right 'a'
ParsecI> parse (char 'a') "stdin" "b"
Left "stdin" (line 1, column 1):
unexpected "b"
expecting "a"
ParsecI> parse (char 'H' >> char 'a' >> char 'l')
            "stdin" "Hal"
Right 'l'
ParsecI> parse (char 'H' >> char 'a' >> char 'l')
            "stdin" "Hap"
Left "stdin" (line 1, column 3):
unexpected "p"
expecting "l"

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

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

We can write our int and intList 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 st type variable is simply a state variable that we are not using. In the int function, we use the many function (built in to Parsec) together with the digit function (also built in to Parsec). The intList function is actually identical to the one we wrote before.

Note, however, that using mplus explicitly is not the preferred method of combining parsers: Parsec provides a <|> function that is a synonym of mplus, 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:

ParsecI> parse intList "stdin" "[3,5,2,10]"
Right [3,5,2,10]
ParsecI> parse intList "stdin" "[3,5,a,10]"
Left "stdin" (line 1, column 6):
unexpected "a"
expecting digit

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

  • choice takes a list of parsers and performs an or operation (<|>) between all of them.
  • option takes a default value of type a and a parser that returns something of type a. It then tries to parse with the parser, but it uses the default value as the return, if the parsing fails.
  • optional takes a parser that returns () and optionally runs it.
  • between 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 intList parser.
  • notFollowedBy 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 choice combinator in action). The first simply parses an int and then wraps it up in the Value constructor. The second option uses between 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 e1 :+: e2 or e1 :*: e2.

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

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

We can use this as:

ParsecI> parse parseValue "stdin" "(3*(4+3))"
Right 21

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 getState and setState (or updateState) 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)
  , 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 int 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 letter function is a Parsec primitive that parses alphabetic characters), followed by its value (a parseValueLet). 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 unexpected to report an error.

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

ParsecI> runParser parseValueLet emptyFM "stdin"
                 "let c=5 in ((5+4)*c)"
Right 45
*ParsecI> runParser parseValueLet emptyFM "stdin"
                 "let c=5 in ((5+4)*let x=2 in (c+x))"
Right 63
*ParsecI> runParser parseValueLet emptyFM "stdin"
                 "((let x=2 in 3+4)*x)"
Right 14

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

Qui ci sarebbe un esercizio che non faccio perché mi sono perso. Ho (solo io?) un problema con l’import dei moduli; si può usare hoogle ma sono ancora troppo niubbo.


Haskell – 191 – monadi – 12

Continuo da qui, copio qui, scrollare fino a “Given this monadic parser“.

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 Parser 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 char and anyChar are not given, since they can be written in terms of matchChar. The many 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:

Parsing2> runParser helloParser 1 "Hello"
Right (1,"","Hello")
Parsing2> runParser int 1 "a54"
Left "1: expecting char, got 'a'"
Parsing2> runParser intList 1 "[1,2,3,a]"
Left "1: expecting ']' got '1'"

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

Parsing2> runParser intListSpace 1
               "[1 ,2 , 4  \n\n ,a\n]"
Left "3: expecting char, got 'a'"
Parsing2> runParser intListSpace 1
               "[1 ,2 , 4  \n\n\n ,a\n]"
Left "4: expecting char, got 'a'"
Parsing2> runParser intListSpace 1
               "[1 ,\n2 , 4  \n\n\n ,a\n]"
Left "5: expecting char, got 'a'"

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


Haskell – 190 – monadi – 11

Enrico Bo

Continuo da qui, copio qui.

Analizzare (parsing) monadi
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.

Un semplice parser
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 Left err to be an error condition. This yields standard instances of Monad and MonadPlus:

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 runParser and by supplying input:

Parsing> runParser helloParser "Hello"
Right ("","Hello")
Parsing> runParser helloParser "Hello World!"
Right (" World!","Hello")
Parsing> runParser helloParser "hello World!"
Left "expecting 'H' got 'h'"

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 matchChar ((=='h'). toLower), but the above implementation works just as well. We can test this function:

Parsing> runParser ciHelloParser "hELlO world!"
Right (" world!","hELlO")

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 many combinator, for instance, will take a parser that parses entities of type a and will make it into a parser that parses entities of type [a] (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, p. If this fails, we succeed but return the empty list. If p succeeds, we recurse and keep trying to apply p 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 Parser 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 isDigit function comes from the module Char/Data.Char) and then match as many more digits as we can. We then read the result and return it. We can test this parser as before:

Parsing> runParser int "54"
Right ("",54)
*Parsing> runParser int "54abc"
Right ("abc",54)
*Parsing> runParser int "a54abc"
Left "expecting char, got 'a'"

Now, suppose we want to parse a Haskell-style list of Ints. 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 Parser is an instance of MonadPlus 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 mplus, it tries one of two things: parsing using intList', or parsing a close brace and returning an empty list.

The intList' 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 mplus. 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 mplus. 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:

Parsing> runParser tricky "Hal"
Right ("","Hal")
Parsing> runParser tricky "Hall"
Right ("l","Hal")

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 tricky using eof as:

tricky2 = do
  s <- mplus (string "Hal") (string "Hall")
  return s

But this also doesn’t work, as we can easily see:

Parsing> runParser tricky2 "Hal"
Right ("",())
Parsing> runParser tricky2 "Hall"
Left "Expecting EOF, got \"l\""

This is because, again, the mplus 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 eof to produce an error message.

The correct way to implement this is:

tricky3 =
  mplus (do s <- string "Hal"
            return s)
        (do s <- string "Hall"
            return s)

We can see that this works:

Parsing> runParser tricky3 "Hal"
Right ("","Hal")
Parsing> runParser tricky3 "Hall"
Right ("","Hall")

This works precisely because each side of the mplus 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 [prossimamente]) 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.

Write a parser intListSpace that will parse int lists but will allow arbitrary white space (spaces, tabs or newlines) between the commas and brackets.

La soluzione è qui. Non lo riporto, devo capire se ha senso.


Haskell – 189 – monadi – 10

Continuo da qui, copio qui, scrollare agli esercizi in fondo al capitolo.

1. Write a function searchAll6, based on the code for searchAll2, that, at every entry to the main function (not the recursion over the edge list), prints the search being conducted. For instance, the output generated for searchAll6 gr 0 3 should look like:

Exploring 0 -> 3
Exploring 1 -> 3
Exploring 3 -> 3
Exploring 2 -> 3
Exploring 3 -> 3
MTrans> it

In order to do this, you will have to define your own list monad transformer and make appropriate instances of it.

Naturalmente copio la soluzione, qui.

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 ListT constructor simply wraps a monadic action (in monad m) 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 l. This has type [e]. We now need to apply k to each of these elements (which will result in something of type ListT m [e2]. We need to get rid of the ListTs around this (by using unListT) and then concatenate them to make a single list.

Now, we need to make it an instance of MonadPlus

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 MonadTrans:

instance MonadTrans ListT where
  lift x = ListT (do a <- x; return [a])

Lifting an action into ListT simply involves running it and getting the value (in this case, a) out and then returning the singleton list.

Once we have all this together, writing searchAll6 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
  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 searchAll6 instead of searchAll2) here is that we call putStrLn with appropriate arguments, lifted into the monad.

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

MTrans> unListT (searchAll6 gr 0 3)
Exploring 0 -> 3
Exploring 1 -> 3
Exploring 3 -> 3
Exploring 2 -> 3
Exploring 3 -> 3
MTrans> it

2. Combine the searchAll5 function (from this section) with the searchAll6 function (from the previous exercise) into a single function called searchAll7. This function should perform IO as in searchAll6 but should also keep track of state using a state transformer.

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 putT and getT into searchAll6 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
    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 Monad (t IO), MonadTrans t, MonadPlus (StateT [Int] (t IO)) => StateT [Int] (t IO) [Int].

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

MTrans> unListT (evalStateT (searchAll7 gr4 0 3) [])
Exploring 0 -> 3
Exploring 1 -> 3
Exploring 3 -> 3
Exploring 0 -> 3
Exploring 2 -> 3
Exploring 3 -> 3
MTrans> it

And it works, even on gr4.

OK, panico 😯


Haskell – 188 – monadi – 9

Continuo da qui, copio qui.

Trasformatore di monadi
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 MonadTrans 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: lift. The class declaration for MonadTrans is:

class MonadTrans t where
  lift :: Monad m => m a -> t m a

The idea here is that t is the outer monad and that m lives inside of it. In order to execute a command of type Monad m => m a, we first lift 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 state -> (state, a) as the monad, we assume there’s some other monad m and make the internal action into something of type state -> m (state, a). 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 m 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 MonadTrans:

instance MonadTrans (StateT state) where
  lift m = StateT (\s -> do a <- m
                            return (s,a))

Here, lifting a function from the realm of m to the realm of StateT state simply involves keeping the state (the s value) constant and executing the action.

Of course, we also need to make StateT a monad, itself. This is relatively straightforward, provided that m 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 return is that we keep the state constant and simply return the state a pair in the enclosed monad. Note that the use of return in the definition of return refers to the enclosed monad, not the state transformer.

In the definition of bind, we create a new StateT that takes a state s as an argument. First, it applies this state to the first action (StateT m) and gets the new state and answer as a result. It then runs the k 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) State monad described in the section on State [qui].

The fail function passes on the call to fail 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 getT , putT and evalStateT. These are analogous to getState, putState and runStateM 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 evalStateT 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 lift 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 mapTreeM 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 lift (putStrLn ...) as the first line. The lift tells us that we’re going to be executing a command in an enclosed monad. In this case, the enclosed monad is IO, since the command lifted is putStrLn.

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 mapTreeM takes an action and a tree and returns a tree. This just as before. In this, we require that t is a monad transformer (since we apply lift in it); we require that t IO is a monad, since we use putStrLn we know that the enclosed monad is IO; finally, we require that a is an instance of show — this is simply because we use show to show the value of leaves.

Now, we simply change numberTree to use this version of mapTreeM, and the new versions of get and put, 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 (Nota: non sufficientemente chiaro per me che codice devo inserire):

MTrans> evalStateT (numberTree testTree) 0
Leaf 'a'
Leaf 'b'
Leaf 'c'
Leaf 'd'
Leaf 'e'
*MTrans> it
Branch (Branch (Leaf ('a',0))
       (Branch (Leaf ('b',1)) (Leaf ('c',2))))
       (Branch (Leaf ('d',3)) (Leaf ('e',4)))

One problem not specified in our discussion of MonadPlus 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 searchAll2, 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 gr4), the result of searchAll2 gr4 0 3 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
    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 getT and putT) 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:

MTrans> evalStateT (searchAll5 gr3 0 3) [] :: [[Int]]
MTrans> evalStateT (searchAll5 gr4 0 3) [] :: [[Int]]

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

We can also provide an execStateT 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 evalStateT (try it and find out!), but can be useful in general (if, for instance, we need to know how many numbers are used in numberTree).

Oviamente mi sono perso 😡 Prossimamente gli esercizi.


Haskell – 187 – monadi – 8

Continuo da qui, copio qui.

Given only the >>= and return functions, it is impossible to write a function like combine with type c a -> c a -> c a. However, such a function is so generally useful that it exists in another class called MonadPlus. In addition to having a combine function, instances of MonadPlus 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 the section on Common [qui], we showed that Maybe and list are both monads. In fact, they are also both instances of MonadPlus. In the case of Maybe, the zero element is Nothing; in the case of lists, it is the empty list. The mplus operation on Maybe is Nothing, if both elements are Nothing; otherwise, it is the first Just value. For lists, mplus 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 search', 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 search'.

The IO monad is not an instance of MonadPlus; we 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 gr and (b) get a path in gr2.

Uh! al solito, non trovo MonadPlus. Problema non solo mio, qui. Da risolvere, prossimamente.

MPlus> searchAll2 gr 0 3 :: [[Int]]
MPlus> searchAll2 gr2 0 3 :: [[Int]]

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 searchAll2 fails, we don’t try to continue and execute search' es. The call to mplus must be at the top level in order for it to work.

Suppose that we changed the order of arguments to mplus. I.e., the matching case of search’ looked like:

search' es `mplus`
(searchAll2 g v dst >>= \path ->
  return (u:path))

How would you expect this to change the results when using the list monad on gr? Why?

La soluzione è qui.

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

MPlus> searchAll3 gr 0 3 :: [[Int]]

Just as we expected.

Post tutto da rivedere 😡


Haskell – 186 – monadi – 7

Continuo da qui, copio qui.

Combinatori monadici
The Monad/Control.Monad 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:

Nota: non ho trovato Monad, solo Control.Monad; altro caso di cambiamento e deprecazione, forse.

    (=<<) :: (a -> m b) -> m a -> m b
    mapM  :: (a -> m b) -> [a] -> m [b]
    mapM_  :: (a -> m b) -> [a] -> m ()
    filterM  :: (a -> m Bool) -> [a] -> m [a]
    foldM  :: (a -> b -> m a) -> a -> [b] -> m a
    sequence  :: [m a] -> m [a]
    sequence_ :: [m a] -> m ()
    liftM  :: (a -> b) -> m a -> m b
    when  :: Bool -> m () -> m ()
    join  :: m (m a) -> m a

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

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:

Prelude> :m Control.Monad
Prelude Control.Monad> writeFile "foo" "hello world!" >> (readFile "foo" >>= putStrLn)
hello world!
Prelude Control.Monad> writeFile "foo" "hello world!" >> (putStrLn =<< readFile "foo")
hello world!

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

Prelude Control.Monad> mapM_ print [1,2,3,4,5]

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

foldM (\a b ->
       putStrLn (show a ++ "+" ++ show b ++
                 "=" ++ show (a+b)) >>
       return (a+b)) 0 [1..5]


Prelude> import Control.Monad
Prelude Control.Monad> foldM (\a b -> putStrLn (show a ++ "+" ++ show b ++ "=" ++ show (a+b)) >> return (a+b)) 0 [1..5]

GHCi mi obbliga a scrivere l’espressione tutta su una sola riga.

The sequence and sequence_ functions simply “execute” a list of actions. For instance:

Prelude Control.Monad> sequence [print 1, print 2, print 'a']
Prelude Control.Monad> it

Al solito la versione che uso è diversa da quella del tutorial.

Prelude Control.Monad> sequence_ [print 1, print 2, print 'a']
Prelude Control.Monad> it

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 liftM function “lifts” a non-monadic function to a monadic function. (Do not confuse this with the lift function used for monad transformers in the section on Transformer [prossimamente].) 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 liftM:

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 liftM. 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 `liftM`.

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

Prelude Control.Monad> liftM (+1) (Just 5)
Just 6
Prelude Control.Monad> liftM (+1) Nothing

The when function executes a monadic action only if a condition is met. So, if we only want to print non-empty lines:

Prelude Control.Monad> mapM_ (\l -> when (not $ null l) (putStrLn l)) ["","abc","def","","","ghi"]

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

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

Prelude Control.Monad> join (Just (Just 'a'))
Just 'a'
Prelude Control.Monad> join (Just (Nothing :: Maybe Char))
Prelude Control.Monad> join (Nothing :: Maybe (Maybe Char))
Prelude Control.Monad> join (return (putStrLn "hello"))
Prelude Control.Monad> return (putStrLn "hello")
Prelude Control.Monad> join [[1,2,3],[4,5]]

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