How jectivity corresponds to morphisms

“Jectivity” may or may not be a real word in the dictionary and my command of the English language is not adequate for me to make such a discussion.

But “jectivity” is indeed a valid mathematical word and it concerns the classification of functions into injective, surjective, and bijective ones.

But before we discuss jectivity, let us discuss functions. What is a function and what is not a function?

A function maps all elements from its domain to its codomain. Any element from the domain is mapped to only one element from the codomain.

This is a function:

Slide1

This is not a function, because an element from the domain is not mapped:

Slide2

This is not a function, because an element from the domain is mapped to more than one element in the codomain:

Slide3

Now let us classify functions into injective, surjective, and bijective ones.

Please note that the following analysis is based on numerous Wikipedia articles on functions and morphisms.

An injective function (or injection) maps any element of the domain to a different element in the codomain.

A surjective function (or surjection) maps to all elements of the codomain.

A bijective function (or bijection) is both injective and surjective.

Example:

Slide4

A function f: A -> B is injective if and only if f is left-invertible; that is, there is a function g: f(A) -> A such that g o f = identity function on A.
A function f: X -> Y is injective if and only if it is left-cancellative; that is, given any functions g1 ,g2 : Y -> Z, f o g1 = f o g2 => g1 = g2.

A function f: A -> B is surjective if and only if it is right-invertible; that is, there is a function g: B -> A such that f o g = identity function on B.
A function f: X -> Y is surjective if and only if it is right-cancellative; that is, given any functions g1, g2 : Y -> Z, g1 o f = g2 o f => g1 = g2.

A function f: A -> B is bijective if and only if it is invertible; that is, there is a function g: B -> A such that g o f = identity function on A and f o g = identity function on B.

The composition of two bijections is again a bijection, but if g o f is a bijection, then it can only be concluded that f is injective and g is surjective.

Injections, surjections, and bijections loosely correspond to Category Theory’s monomorphisms, epimorphisms, and isomorphisms, respectively.

A monomorphism (also called a monic morphism or a mono) is a morphism f: X -> Y that is left-cancellative in the sense that, for all morphisms g1, g2 : Z -> X, f o g1 = f o g2 => g1 = g2.

An epimorphism (also called an epic morphism or an epi) is a morphism f: X -> Y that is right-cancellative in the sense that, for all morphisms g1, g2 : Y -> Z, g1 o f = g2 o f => g1 = g2.

An isomorphism is both a monomorphism and an epimorphism.

A morphism f : X -> Y in a category is an isomorphism if it has a two-sided inverse; that is, there is another morphism g : Y -> X in that category such that g o f = 1X and f o g = 1Y, where 1X and 1Y are the identity morphisms of X and Y, respectively.

I think that this analysis could be used as the introduction to a primer in Category Theory.

Posted in Science

Absolute URLs vs. relative URLs vs. protocol relative URLs

Examples

Absolute URL:
http://yoursite.com/folder/subfolder/file.html
Relative URL:
/folder/subfolder/file.html
Protocol relative URL:
//anothersite.com/anotherfolder/anothersubfolder/anotherfile.html

Tips

  • Try to avoid absolute URLs.
  • Try to use relative URLs for links inside your site.
  • Try to use protocol relative URLs for links outside your site.
Posted in Web design

Venn diagrams vs. Euler diagrams

In Venn diagrams, all areas (subsets) are shown. Areas that contain no elements (empty subsets) are filled with black color.

In Euler diagrams, only areas that contain elements (non-empty subsets) are shown.

If we want to depict all areas, irrespectively of whether they contain elements or not, We should choose to make a Venn diagram.

If we want to avoid depicting areas that contain no elements, and instead focus only on the areas that are non-empty, we should choose to make an Euler diagram.

Venn diagrams vs. Euler diagrams

Posted in Science

Arrow talk

On the Stack Overflow site, I found a great question titled Monads vs. Arrows. Essentially the OP (original poster) asks: “… When should I use monads and when should I use arrows?”.

I answered the question and since I believe that I raise some important points in my answer, I decided to duplicate my answer here as well. My answer follows:

The short answer is that Arrows are more general than Monads and are also more cumbersome to use. Thus you should use Monads whenever you can, leaving the use of Arrows for the cases where Monads are not applicable.

The “scenic route” answer follows.

John Hughes, the person who introduced Arrows, has published two great papers that I recommend: “Generalising monads to arrows” and “Programming with Arrows”. These two articles are easy to read and provide the answer to your question. Even if some people do not understand all the details or the code in these two articles, they will certainly find lots of information and very helpful explanations about Monads and Arrows.

I will now highlight the main points from these articles that pertain to your question.

When Monads were introduced, people thought that they were all-powerful. Indeed, Monads pack a lot of power. But at some point, it was found that there are cases where Monads cannot be applied. These cases have to do with multiple inputs, especially when some of the inputs are static and some of the inputs are dynamic. So, John Hughes stepped up and introduced Arrows.

Arrows are more general than Monads. Arrows are a superset of Monads. They can do all that Monads do and more. But they are also more difficult to use. John Hughes recommends that you should use Monads whenever you can and that you should use Arrows when you cannot use Monads.

I agree with John Hughes. I am also reminded of Einstein’s quote “Everything should be made as simple as possible, but not simpler”.

Of course, it all depends on the particular situation at hand. Let me explain. Let us suppose that you are learning Haskell. Then it would be a great task to do each program using a monadic approach and redo it using an arrow-based approach. When you learn, you should strive to explore all possibilities and implement all kinds of approaches. This way, you obtain great insight and you are able to compare different solutions first-hand.

Now let us suppose that you want to provide a library to the community. Well, you owe it to the people that will read your code that you should use the approach that is easiest to understand and still gets the job done. You also owe it to the people that will use your code that your solution lacks unnecessary complexity. This way, your solution is more easily maintainable and less prone to errors and bugs.

But what if you are in a borderline case? Let us suppose that you are not sure whether or not you will need the extra power of Arrows. Then what should you do? Should you start with a monadic approach and later switch to an arrow-based one if the need arises? Or should you start with Arrows from the get-go, avoiding a costly switch halfway through the project?

Again, my answer is to try the first approach: try to use Monads if you can. If you later find out that you cannot use Monads, you will have to endure a costly switch, where you will have to restart and redo the project in order to use Arrows. This approach will certainly require more time and other resources from your part. But you will know that you did the correct thing, which was to try to provide the simplest, clearest, less complex solution possible.

Avoiding unnecessary complexity is the most important thing. Believe it or not, this is the reason concepts (such as function composition, Monads and Arrows) from Category Theory were introduced to Computer Science. Ironic?

Posted in Development

Cheat sheet for Monads in Haskell

Let M be a Type Constructor, Functor, and Monad.

As a Type Constructor, M can map a type a to the type M a.

As a Functor, M can also map a function f to the function M f, using M’s fmap function that we must provide.

As a Monad, M has a Natural Transformation μ :: M2 -> M, where M2 = M o M. We will see how this makes possible the composition of a function a – > M b and a function b -> M c.

If we have a function g :: a -> b and a function f :: b -> c, then we can compose these two functions. Their composition is the function f o g :: a -> c.

f o g is calculated as follows: a -> b -> c. In other words, the input of function g is the input of f o g, the output of function g is used as input to the function f, and the output of function f is the output of f o g.

But we cannot use “normal” composition when the functions g and f are of the following form:

g :: a -> M b
f :: b -> M c

In this case, to “compose” these two functions we need to define a “special” composition. Let us call this special composition “bind” and let its symbol be >>= so that g >>= f is this special composition. Thus, bind takes the output of function g, passes it function f, and produces as output the output of function f. Thus (>>=) :: M b -> (b -> M c) -> M c. Since b and c are any types, we can use a and b instead of b and c. Thus: ( >>=) :: M a -> (a -> M b) -> M b.

Thus, bind is defined as M a -> (a -> M b) -> M b. Now let us see what bind is equal to. Let:

g :: a -> M b
f :: b -> M c

Thus M f :: M b -> M2 c, where M2 = M o M.

In the previous line, M was used as a Functor. M f is also known as fmap f.

As a Monad, M has a Natural Transformation μ­­a :: M2 a -> M a. Since this holds true for any type, we use c instead of a, thus μ­­­c :: M2 c -> M c. μ is also known as join.

We can now find the result of the special composition between g and f and what bind is equal to.

g >>= f is calculated as follows: a -> M b -> M2 c -> M c.

Thus >>= is equal to μc o (M f) o g.

Thus bind = join o (fmap f) o g.

By using the special composition bind (>>=), we are able to compose two functions that are NOT of types a-> b and b -> c, but are of types a -> M b and b -> M c.

Posted in Development

The most significant FAQs about Haskell

Question: Function application and composition versus bind (>>=)

Answer: For the following discussion, a, b, and c are built in Haskell data types.

We use normal function composition when we compose a function a -> b with a function b -> c. The result is a function with a type signature of a -> c and with an output of type c.

We use bind when we compose a function a -> M b with a function b -> M c. The result is a function a -> M c. M is a Monad and bind is a function that a Monad has to have and that instructs on how such a composition is to be made. Someone has to provide the code for bind. The type signature for bind is M a -> (a -> M b) -> M b. Since a, b, and c are arbitrary types, this can be written equivalently as M b -> (b -> M c) -> M c. Thus we see that bind takes the output of a function a -> M b and a function b -> M c and composes them producing the output M c.

Question: let versus <-

Answer: First of all, let and <- are not interchangeable; they perform differently.

The <- statement has to have a Monad on its right side and it will extract the value from that Monad.

The let statement is just assignment. It does not extract anything from its right side and its right side can have any type (even a Monad).

Here is a program that demonstrates the use of the <- operator:

module Main where

import Data.Typeable

myFunction   :: String -> IO Int
myFunction xs =
   do
     putStrLn "Inside the function that returns the length of a string plus 10."
     return ((length xs) + 10) 

main :: IO ()
main  =
   do
     putStrLn "Program begins."

     a <- myFunction "Dimitrios Kalemis"
     print a
     print (typeOf a)
     print (typeOf myFunction)

     putStrLn "Program ends."

The <- statement is syntactic sugar used in the do notation. The following two programs are equivalent:

First program:

module Main where 

main :: IO ()
main  =
   do
     nameVariable <- getLine
     putStrLn ("You typed: " ++ nameVariable)

Second program:

module Main where 

main :: IO ()
main  = getLine >>= \nameVariable -> putStrLn ("You typed: " ++ nameVariable)

The StackOverflow entry “<-” bindings in do notation has excellent answers concerning this matter.

Question: data versus type versus newtype

Answer: The data declaration is used for the creation of new types.

The type declaration is used for the creation of type synonyms for existing types.

The newtype declaration is almost like the data declaration. The newtype declaration and the data declaration have some differences.

The underlying reason for these differences is that types declared with the data keyword are lifted – that is, they contain their own bottom (⊥) value that is distinct from all the others. (The term bottom refers to a computation which never completes successfully.) Thus, Haskell provides the newtype keyword, for the construction of unlifted types.

This fact leads to the following two differences:

  • Although you can replace the newtype keyword with the data keyword, the converse is not true: the data keyword can only be replaced with newtype if the type has exactly one value constructor with exactly one field inside it.
  • The value constructor introduced by data is lazy (thus carries more overhead) than the value constructor introduced by newtype which is strict (thus faster).

For more information I recommend the following two sources:

More insight on this issue can be found in John Hughes’ excellent paper “Generalising monads to arrows”. In paragraph 2.2, John Hughes describes the State Monad. He writes:

In this case we represent a computation with result type a and a state of type s by a value of the type
newtype StateMonad s a = SM (s -> (a,s))

For the newtype declaration, John Hughes provides following footnote:

The Haskell newtype declaration introduces a new type isomorphic to an existing one, where the constructor names the isomorphism. Its purpose is to enable us to define overloaded operations which behave differently on the new type and the old. In this case, we will define the monad operations for StateMonad quite independently of any definition that may be given for functions. The difference between a newtype and data declaration is subtle, but quite important for efficiency: at run-time, a value of a type defined by newtype is represented in exactly the same way as the type it is isomorphic to – the constructor is not represented at all – whereas the constructors of a data type are always represented explicitly.

Posted in Development

The examples in the Parsec users guide

Parsec is a free, industrial strength, monadic parser combinator library for Haskell, by Daan Leijen. You can find the users guide in the Parsec documentation. In this blog post, I am going to list the examples that Daan Leijen includes in the Parsec users guide. All programs in this blog post are his copyright, not mine. All I do is change the indenting and take care of small details, in order to make the programs more familiar to the readers of my blog who have become accustomed to the way I present Haskell programs.

The purpose of this blog post is to introduce the readers of my blog to parsing in Haskell and to a parser library for Haskell. I chose Parsec, because it is a great parser library and very well documented. I also recommend the following material:

  • The Parsec page in Haskell.org
  • The Parsec documentation, titled “Parsec, a fast combinator parser“, by Daan Leijen
  • The Wikipedia article titled “Parser combinator
  • The paper titled “Monadic Parsing in Haskell“, by Graham Hutton and Erik Meijer
  • The paper titled “Monadic Parser Combinators“, by Graham Hutton and Erik Meijer
  • The paper titled “Parsec: Direct Style Monadic Parser Combinators For The Real World“, by Daan Leijen and Erik Meijer”

Again, everything in this blog post is Daan Leijen’s copyright. But I am responsible for anything that you may find wrong, incorrect, inappropriate, and for any mistakes.

I compiled the programs with Haskell Platform 2012.4.0.0, which includes Parsec. Specifically, I used the following tool:

WinGHCi

In the following, I list each program along with its output.

So, here are the examples that are included in the Parsec documentation:

Example 01, code

module Main where

import Text.ParserCombinators.Parsec

simple :: Parser Char
simple  = letter

run        :: Show a => Parser a -> String -> IO ()
run p input =
   case (parse p "" input) of
      Left err ->
         do
            putStr "parse error at "
            print err          
      Right x ->
         print x

main :: IO ()
main  =
   do
      putStrLn "Program begins."
      putStrLn ""
      
      run simple "a"

      putStrLn ""

      run simple ""
      
      putStrLn ""
      
      run simple "123"

      putStrLn ""
      putStrLn "Program ends."

Example 01, output

Program begins.

'a'

parse error at (line 1, column 1):
unexpected end of input
expecting letter

parse error at (line 1, column 1):
unexpected "1"
expecting letter

Program ends.

Example 02, code

module Main where

import Text.ParserCombinators.Parsec

parens :: Parser ()
parens  =
      do  
         char '('
         parens
         char ')'
         parens
   <|>
      return ()

run        :: Show a => Parser a -> String -> IO ()
run p input =
   case (parse p "" input) of
      Left err ->
         do
            putStr "parse error at "
            print err          
      Right x ->
         print x

main :: IO ()
main  =
   do
      putStrLn "Program begins."
      putStrLn ""

      run parens "(())()"

      putStrLn ""

      run parens "(()()"

      putStrLn ""
      putStrLn "Program ends."

Example 02, output

Program begins.

()

parse error at (line 1, column 6):
unexpected end of input
expecting "(" or ")"

Program ends.

Example 03, code

module Main where

import Text.ParserCombinators.Parsec

testOr :: Parser String
testOr  =
      string "(a)"
   <|>
      string "(b)"

testOr1 :: Parser Char
testOr1 =
   do
      char '('
      char 'a' <|> char 'b'
      char ')'

testOr2 :: Parser String
testOr2  =
      try (string "(a)")
   <|>
      string "(b)"

testOr3 :: Parser String
testOr3  =
      do
         try (string "(a")
         char ')'
         return "(a)"
   <|>
      string "(b)"

run        :: Show a => Parser a -> String -> IO ()
run p input =
   case (parse p "" input) of
      Left err ->
         do
            putStr "parse error at "
            print err          
      Right x ->
         print x

main :: IO ()
main  =
   do
      putStrLn "Program begins."
      putStrLn ""

      run testOr "(b)"

      putStrLn ""

      run testOr1 "(b)"

      putStrLn ""

      run testOr2 "(b)"

      putStrLn ""

      run testOr3 "(b)"

      putStrLn ""
      putStrLn "Program ends."

Example 03, output

Program begins.

parse error at (line 1, column 1):
unexpected "b"
expecting "(a)"

')'

"(b)"

"(b)"

Program ends.

Example 04, code

module Main where

import Text.ParserCombinators.Parsec

nesting :: Parser Int
nesting  =
      do
         char '('
         n <- nesting
         char ')'
         m <- nesting
         return (max (n+1) m)
   <|>
      return 0

run        :: Show a => Parser a -> String -> IO ()
run p input =
   case (parse p "" input) of
      Left err ->
         do
            putStr "parse error at "
            print err          
      Right x ->
         print x

main :: IO ()
main  =
   do
      putStrLn "Program begins."
      putStrLn ""

      run nesting "(())()"

      putStrLn ""

      run nesting "(()(()))"

      putStrLn ""

      run nesting "(()(())"

      putStrLn ""
      putStrLn "Program ends."

Example 04, output

Program begins.

2

3

parse error at (line 1, column 8):
unexpected end of input
expecting "(" or ")"

Program ends.

Example 05, code

module Main where

import Text.ParserCombinators.Parsec

word :: Parser String
word =
   do
      c <- letter
      do  
            cs <- word
            return (c:cs)
         <|>
            return [c]

sentence :: Parser [String]
sentence  =
   do
      words <- sepBy1 word separator
      oneOf ".?!"
      return words

separator :: Parser ()
separator = skipMany1 (space <|> char ',')

run        :: Show a => Parser a -> String -> IO ()
run p input =
   case (parse p "" input) of
      Left err ->
         do
            putStr "parse error at "
            print err          
      Right x ->
         print x

main :: IO ()
main  =
   do
      putStrLn "Program begins."
      putStrLn ""

      run sentence "hi,di,hi."

      putStrLn ""

      run sentence "hi,di hi!"

      putStrLn ""

      run sentence "hi,123"

      putStrLn ""
      putStrLn "Program ends."

Example 05, output

Program begins.

["hi","di","hi"]

["hi","di","hi"]

parse error at (line 1, column 4):
unexpected "1"
expecting space, "," or letter

Program ends.

Example 06, code

module Main where

import Text.ParserCombinators.Parsec

word :: Parser String
word  = many1 letter

sentence :: Parser [String]
sentence  =
   do
      words <- sepBy1 word separator
      oneOf ".?!"
      return words

separator :: Parser ()
separator  = skipMany1 (space <|> char ',')

run        :: Show a => Parser a -> String -> IO ()
run p input =
   case (parse p "" input) of
      Left err ->
         do
            putStr "parse error at "
            print err          
      Right x ->
         print x

main :: IO ()
main  =
   do
      putStrLn "Program begins."
      putStrLn ""

      run sentence "hi,di,hi."

      putStrLn ""

      run sentence "hi,di hi!"

      putStrLn ""

      run sentence "hi,123"

      putStrLn ""
      putStrLn "Program ends."

Example 06, output

Program begins.

["hi","di","hi"]

["hi","di","hi"]

parse error at (line 1, column 4):
unexpected "1"
expecting space, "," or letter

Program ends.

Example 07, code

module Main where

import Text.ParserCombinators.Parsec

word :: Parser String
word  = many1 letter <?> "word"

sentence :: Parser [String]
sentence  =
   do
      words <- sepBy1 word separator
      oneOf ".?!"
      return words

separator :: Parser ()
separator = skipMany1 (space <|> char ',')

run        :: Show a => Parser a -> String -> IO ()
run p input =
   case (parse p "" input) of
      Left err ->
         do
            putStr "parse error at "
            print err          
      Right x ->
         print x

main :: IO ()
main  =
   do
      putStrLn "Program begins."
      putStrLn ""

      run sentence "hi,123"

      putStrLn ""
      putStrLn "Program ends."

Example 07, output

Program begins.

parse error at (line 1, column 4):
unexpected "1"
expecting space, "," or word

Program ends.

Example 08, code

module Main where

import Text.ParserCombinators.Parsec

word :: Parser String
word  = many1 letter <?> "word"

sentence :: Parser [String]
sentence  =
   do
      words <- sepBy1 word separator
      oneOf ".?!"
      return words

separator :: Parser ()
separator  = skipMany1 (space <|> char ',' <?> "")

run        :: Show a => Parser a -> String -> IO ()
run p input =
   case (parse p "" input) of
      Left err ->
         do
            putStr "parse error at "
            print err          
      Right x ->
         print x

main :: IO ()
main  =
   do
      putStrLn "Program begins."
      putStrLn ""

      run sentence "hi,123"

      putStrLn ""
      putStrLn "Program ends."

Example 08, output

Program begins.

parse error at (line 1, column 4):
unexpected "1"
expecting word

Program ends.

Example 09, code

module Main where

import Text.ParserCombinators.Parsec

word :: Parser String
word  = many1 letter <?> "word"

sentence :: Parser [String]
sentence  =
   do
      words <- sepBy1 word separator
      oneOf ".?!" <?> "end of sentence"
      return words

separator :: Parser ()
separator  = skipMany1 (space <|> char ',' <?> "")

run        :: Show a => Parser a -> String -> IO ()
run p input =
   case (parse p "" input) of
      Left err ->
         do
            putStr "parse error at "
            print err          
      Right x ->
         print x

main :: IO ()
main  =
   do
      putStrLn "Program begins."
      putStrLn ""

      run sentence "hi,di"

      putStrLn ""
      putStrLn "Program ends."

Example 09, output

Program begins.

parse error at (line 1, column 6):
unexpected end of input
expecting end of sentence

Program ends.

Example 10, code

module Main where

import Text.ParserCombinators.Parsec

word :: Parser String
word  = many1 (letter <?> "") <?> "word"

sentence :: Parser [String]
sentence  =
   do
      words <- sepBy1 word separator
      oneOf ".?!" <?> "end of sentence"
      return words

separator :: Parser ()
separator  = skipMany1 (space <|> char ',' <?> "")

run        :: Show a => Parser a -> String -> IO ()
run p input =
   case (parse p "" input) of
      Left err ->
         do
            putStr "parse error at "
            print err          
      Right x ->
         print x

main :: IO ()
main  =
   do
      putStrLn "Program begins."
      putStrLn ""

      run sentence "hi di"

      putStrLn ""

      run sentence "hi di,"

      putStrLn ""
      putStrLn "Program ends."

Example 10, output

Program begins.

parse error at (line 1, column 6):
unexpected end of input
expecting end of sentence

parse error at (line 1, column 7):
unexpected end of input
expecting word

Program ends.

Example 11, code

module Main where

import Text.ParserCombinators.Parsec
import Text.ParserCombinators.Parsec.Expr

expr :: Parser Integer
expr  =
      buildExpressionParser table factor
   <?>
      "expression"

table :: OperatorTable Char () Integer
table  = [[op "*" (*) AssocLeft, op "/" div AssocLeft]
         ,[op "+" (+) AssocLeft, op "-" (-) AssocLeft]
         ]
         where
            op s f assoc = Infix (do {string s; return f}) assoc

factor :: Parser Integer
factor  =
      do
         char '('
         x <- expr
         char ')'
         return x
   <|>
      number
   <?>
      "simple expression"

number :: Parser Integer
number  =
      do
         ds <- many1 digit
         return (read ds)
   <?>
      "number"

run        :: Show a => Parser a -> String -> IO ()
run p input =
   case (parse p "" input) of
      Left err ->
         do
            putStr "parse error at "
            print err          
      Right x ->
         print x

main :: IO ()
main  =
   do
      putStrLn "Program begins."
      putStrLn ""

      run expr "1+2*3" -- '*' has higher priority

      putStrLn ""

      run expr "(1+2)*3"

      putStrLn ""
   
      run expr "8/4/2" -- '/' is left associative
      
      putStrLn ""
   
      run expr "8/(4/2)"
      
      putStrLn ""
   
      run expr "1 + 2" -- wrong!
      
      putStrLn ""
   
      run expr "1+ 2" -- wrong!

      putStrLn ""
      putStrLn "Program ends."

Example 11, output

Program begins.

7

9

1

4

1

parse error at (line 1, column 3):
unexpected " "
expecting simple expression

Program ends.

Example 12, code

module Main where

import Text.ParserCombinators.Parsec
import Text.ParserCombinators.Parsec.Expr
import qualified Text.ParserCombinators.Parsec.Token as P
import Text.ParserCombinators.Parsec.Language

whiteSpace = P.whiteSpace lexer
lexeme     = P.lexeme lexer
symbol     = P.symbol lexer
natural    = P.natural lexer
parens     = P.parens lexer
semi       = P.semi lexer
identifier = P.identifier lexer
reserved   = P.reserved lexer
reservedOp = P.reservedOp lexer

lexer :: P.TokenParser ()
lexer  = P.makeTokenParser (haskellDef {reservedOpNames = ["*","/","+","-"]})

expr :: Parser Integer
expr  =
      buildExpressionParser table factor
   <?>
      "expression"

table :: OperatorTable Char () Integer
table  = [[op "*" (*) AssocLeft, op "/" div AssocLeft]
         ,[op "+" (+) AssocLeft, op "-" (-) AssocLeft]
         ]
         where
            op s f assoc = Infix (do{ reservedOp s; return f} <?> "operator") assoc

factor :: Parser Integer
factor  =
       parens expr
   <|> natural
   <?> "simple expression"

runLex        :: Show a => Parser a -> String -> IO ()
runLex p input = run (do { whiteSpace
                         ; x <- p
                         ; eof
                         ; return x
                         }) input

run        :: Show a => Parser a -> String -> IO ()
run p input =
   case (parse p "" input) of
      Left err ->
         do
            putStr "parse error at "
            print err          
      Right x ->
         print x

main :: IO ()
main  =
   do
      putStrLn "Program begins."
      putStrLn ""

      runLex expr "1 + 2"
      
      putStrLn ""

      runLex expr "1 + {- comment -} 2 * 3 --multiply has higher priority"
      
      putStrLn ""

      runLex expr " 0xAA / 0o37 / 2"
      
      putStrLn ""

      runLex expr "0xAA / 0o37 2 "

      putStrLn ""
      putStrLn "Program ends."

Example 12, output

Program begins.

3

7

2

parse error at (line 1, column 13):
unexpected '2'
expecting operator or end of input

Program ends.

Example 13, code

module Main where

import Text.ParserCombinators.Parsec
import Text.ParserCombinators.Parsec.Expr
import qualified Text.ParserCombinators.Parsec.Token as P
import Text.ParserCombinators.Parsec.Language
import Data.Char

whiteSpace = P.whiteSpace lexer
lexeme     = P.lexeme lexer
symbol     = P.symbol lexer
natural    = P.natural lexer
parens     = P.parens lexer
semi       = P.semi lexer
identifier = P.identifier lexer
reserved   = P.reserved lexer
reservedOp = P.reservedOp lexer

lexer :: P.TokenParser ()
lexer  = P.makeTokenParser (haskellDef { reservedOpNames = ["*","/","+","-"]})

expr :: Parser Integer
expr  =
      buildExpressionParser table factor
   <?>
      "expression"

table :: OperatorTable Char () Integer
table  = [[op "*" (*) AssocLeft, op "/" div AssocLeft]
         ,[op "+" (+) AssocLeft, op "-" (-) AssocLeft]
         ]
         where
            op s f assoc = Infix (do {reservedOp s; return f} <?> "operator") assoc

factor :: Parser Integer
factor  =
       parens expr
   <|> natural
   <?> "simple expression"

receipt :: Parser Bool
receipt  =
   do
      ps <- many produkt
      p <- total
      return (sum ps == p)
              
produkt :: Parser Int
produkt  =
      do
         symbol "return"
         p <- price
         semi
         return (-p)    
   <|>
      do
         identifier
         p <- price
         semi
         return p
   <?>
      "produkt"

total :: Parser Int
total  =
   do
      p <- price
      symbol "total"
      return p

price :: Parser Int -- price in cents
price  = lexeme (do { ds1 <- many1 digit
                    ; char '.'
                    ; ds2 <- count 2 digit
                    ; return (convert 0 (ds1 ++ ds2))
                    })
                <?> "price"
                where
                   convert n []     = n
                   convert n (d:ds) = convert (10*n + digitToInt d) ds

runLex        :: Show a => Parser a -> String -> IO ()
runLex p input = run (do { whiteSpace
                         ; x <- p
                         ; eof
                         ; return x
                         }) input

run        :: Show a => Parser a -> String -> IO ()
run p input =
   case (parse p "" input) of
      Left err ->
         do
            putStr "parse error at "
            print err          
      Right x ->
         print x

main :: IO ()
main  =
   do
      putStrLn "Program begins."
      putStrLn ""

      runLex receipt "book 12.00; plant 2.55; 14.55 total"
      
      putStrLn ""

      runLex receipt "book 12.00; plant 2.55; 12.55 total"
      
      putStrLn ""

      runLex receipt "book 12.00; plant 2; 12.55 total"
      
      putStrLn ""

      runLex receipt "book 12.00; return 2.00; plant 2.55; 12.55 total"

      putStrLn ""

      runLex receipt "book 12.00; reader 2.00; plant 1.00; 15.00 total"

      putStrLn ""
      putStrLn "Program ends."

Example 13, output

Program begins.

True

False

parse error at (line 1, column 20):
unexpected ";"
expecting digit or "."

True

parse error at (line 1, column 13):
unexpected "a"
expecting "return"

Program ends.

Example 14, code

module Main where

import Text.ParserCombinators.Parsec
import Text.ParserCombinators.Parsec.Expr
import qualified Text.ParserCombinators.Parsec.Token as P
import Text.ParserCombinators.Parsec.Language
import Data.Char

whiteSpace = P.whiteSpace lexer
lexeme     = P.lexeme lexer
symbol     = P.symbol lexer
natural    = P.natural lexer
parens     = P.parens lexer
semi       = P.semi lexer
identifier = P.identifier lexer
reserved   = P.reserved lexer
reservedOp = P.reservedOp lexer

lexer :: P.TokenParser ()
lexer  = P.makeTokenParser (haskellDef { reservedOpNames = ["*","/","+","-"]})

expr :: Parser Integer
expr  =
      buildExpressionParser table factor
   <?>
      "expression"

table :: OperatorTable Char () Integer
table  = [[op "*" (*) AssocLeft, op "/" div AssocLeft]
         ,[op "+" (+) AssocLeft, op "-" (-) AssocLeft]
         ]
         where
            op s f assoc = Infix (do {reservedOp s; return f} <?> "operator") assoc

factor :: Parser Integer
factor  =
       parens expr
   <|> natural
   <?> "simple expression"

receipt :: Parser Bool
receipt  =
   do
      ps <- many produkt
      p <- total
      return (sum ps == p)

produkt :: Parser Int
produkt  =
      do
         try (symbol "return")
         p <- price
         semi
         return (-p)
   <|>
      do
         identifier
         p <- price
         semi
         return p
   <?>
      "produkt"

total :: Parser Int
total  =
   do
      p <- price
      symbol "total"
      return p

price :: Parser Int -- price in cents
price  = lexeme (do { ds1 <- many1 digit
                    ; char '.'
                    ; ds2 <- count 2 digit
                    ; return (convert 0 (ds1 ++ ds2))
                    })
                <?> "price"
                where
                   convert n []     = n
                   convert n (d:ds) = convert (10*n + digitToInt d) ds

runLex        :: Show a => Parser a -> String -> IO ()
runLex p input = run (do { whiteSpace
                         ; x <- p
                         ; eof
                         ; return x
                         }) input

run        :: Show a => Parser a -> String -> IO ()
run p input =
   case (parse p "" input) of
      Left err ->
         do
            putStr "parse error at "
            print err          
      Right x ->
         print x

main :: IO ()
main  =
   do
      putStrLn "Program begins."
      putStrLn ""

      runLex receipt "book 12.00; plant 2.55; 14.55 total"
      
      putStrLn ""

      runLex receipt "book 12.00; plant 2.55; 12.55 total"
      
      putStrLn ""

      runLex receipt "book 12.00; plant 2; 12.55 total"
      
      putStrLn ""

      runLex receipt "book 12.00; return 2.00; plant 2.55; 12.55 total"

      putStrLn ""

      runLex receipt "book 12.00; reader 2.00; plant 1.00; 15.00 total"

      putStrLn ""      

      runLex receipt "book 12.00; returns 2.00; plant 1.00; 15.00 total"

      putStrLn ""
      putStrLn "Program ends."

Example 14, output

Program begins.

True

False

parse error at (line 1, column 20):
unexpected ";"
expecting digit or "."

True

True

parse error at (line 1, column 19):
unexpected "s"
expecting price

Program ends.

Example 15, code

module Main where

import Text.ParserCombinators.Parsec
import Text.ParserCombinators.Parsec.Expr
import qualified Text.ParserCombinators.Parsec.Token as P
import Text.ParserCombinators.Parsec.Language
import Data.Char

whiteSpace = P.whiteSpace lexer
lexeme     = P.lexeme lexer
symbol     = P.symbol lexer
natural    = P.natural lexer
parens     = P.parens lexer
semi       = P.semi lexer
identifier = P.identifier lexer
reserved   = P.reserved lexer
reservedOp = P.reservedOp lexer

lexer :: P.TokenParser ()
lexer  = P.makeTokenParser (haskellDef
   { reservedNames = ["return","total"]
   , reservedOpNames = ["*","/","+","-"]
   })

expr :: Parser Integer
expr  =
      buildExpressionParser table factor
   <?>
      "expression"

table :: OperatorTable Char () Integer
table  = [[op "*" (*) AssocLeft, op "/" div AssocLeft]
         ,[op "+" (+) AssocLeft, op "-" (-) AssocLeft]
         ]
         where
            op s f assoc = Infix (do {reservedOp s; return f} <?> "operator") assoc

factor :: Parser Integer
factor  =
       parens expr
   <|> natural
   <?> "simple expression"

receipt :: Parser Bool
receipt  =
   do
      ps <- many produkt
      p <- total
      return (sum ps == p)

produkt :: Parser Int
produkt  =
      do
         reserved "return"
         p <- price
         semi
         return (-p)
   <|>
      do
         identifier
         p <- price
         semi
         return p
   <?>
      "produkt"

total :: Parser Int
total  =
   do
      p <- price
      reserved "total"
      return p

price :: Parser Int -- price in cents
price  = lexeme (do { ds1 <- many1 digit
                    ; char '.'
                    ; ds2 <- count 2 digit
                    ; return (convert 0 (ds1 ++ ds2))
                    })
                <?> "price"
                where
                   convert n [] = n
                   convert n (d:ds) = convert (10*n + digitToInt d) ds

runLex        :: Show a => Parser a -> String -> IO ()
runLex p input = run (do { whiteSpace
                         ; x <- p
                         ; eof
                         ; return x
                         }) input

run        :: Show a => Parser a -> String -> IO ()
run p input =
   case (parse p "" input) of
      Left err ->
         do
            putStr "parse error at "
            print err          
      Right x ->
         print x

main :: IO ()
main  =
   do
      putStrLn "Program begins."
      putStrLn ""

      runLex receipt "book 12.00; returns 2.00; plant 1.00; 15.00 total"
      
      putStrLn ""

      runLex receipt "book 12.00; total 2.00; plant 1.00; 15.00 total"
      
      putStrLn ""

      runLex receipt "book 12.00; totals 2.00; return 1.00; 13.00 total"
      
      putStrLn ""
      putStrLn "Program ends."

Example 15, output

Program begins.

True

parse error at (line 1, column 18):
unexpected reserved word "total"
expecting produkt

True

Program ends.

Example 16, code

module Main where

import Text.ParserCombinators.Parsec
import Text.ParserCombinators.Parsec.Perm

perm0 :: Parser [Char]
perm0  = permute (f <$$> char 'a'
                    <||> char 'b'
                    <||> char 'c')
         where
            f a b c = [a,b,c]

run        :: Show a => Parser a -> String -> IO ()
run p input =
   case (parse p "" input) of
      Left err ->
         do
            putStr "parse error at "
            print err          
      Right x ->
         print x

main :: IO ()
main  =
   do
      putStrLn "Program begins."
      putStrLn ""

      run perm0 "abc"
      
      putStrLn ""

      run perm0 "cba"
      
      putStrLn ""

      run perm0 "b"
      
      putStrLn ""
      putStrLn "Program ends."

Example 16, output

Program begins.

"abc"

"abc"

parse error at (line 1, column 2):
unexpected end of input
expecting "c" or "a"

Program ends.

Example 17, code

module Main where

import Text.ParserCombinators.Parsec
import Text.ParserCombinators.Parsec.Perm

perm1 :: Parser (String,Char,Char)
perm1  = permute (tuple <$?> ("",many1 (char 'a'))
                        <||> char 'b'
                        <|?> (' ',char 'c'))
         where
            tuple a b c = (a,b,c)

run        :: Show a => Parser a -> String -> IO ()
run p input =
   case (parse p "" input) of
      Left err ->
         do
            putStr "parse error at "
            print err          
      Right x ->
         print x

main :: IO ()
main  =
   do
      putStrLn "Program begins."
      putStrLn ""

      run perm1 "caaaaab"

      putStrLn ""

      run perm1 "cb"

      putStrLn ""

      run perm1 "b"

      putStrLn ""

      run perm1 ""

      putStrLn ""

      run perm1 "c"

      putStrLn ""

      run perm1 "ca"
      
      putStrLn ""
      putStrLn "Program ends."

Example 17, output

Program begins.

("aaaaa",'b','c')

("",'b','c')

("",'b',' ')

parse error at (line 1, column 1):
unexpected end of input

expecting "c", "b" or "a"

parse error at (line 1, column 2):
unexpected end of input
expecting "b" or "a"

parse error at (line 1, column 3):
unexpected end of input
expecting "a" or "b"

Program ends.
Posted in Development