Functional Parser example from Programming in Haskell

Question

On page 76 we define a function item as parser -- a function that takes a String and returns [(Char, String)] or [] if failed.

On page 78 we define a function sat that takes a predicate p and "wraps" a parser construction around that

p :: (Char -> Bool) -> Parser Char
sat p = do x <- item
           if p x then return x else failure

What I don't understand is the magic of <-? If the result of item is not empty then this operator should unwrap the list and fetch the first item from the tuple, otherwise it should produce something that won't choke the predicate. What am I missing?

It looks like you are using Graham Hutton's book "Programming in Haskell". Graham uses a simplification in this chapter that isn't strictly Haskell - see the closing remarks of the chapter (section 8.9) and the online code on Graham's web page for directly executable Haskell. — stephen tetley
– stephen tetley, Commented Sep 29, 2012 at 16:25

dave4420 · Accepted Answer · 2012-09-29 13:23:11Z

3

do x <- item
   if p x then return x else failure

This is syntactic sugar for

item >>= (\x -> if p x then return x else failure)

>>= is the monadic bind operator.

What you're missing is: what is the definition of >>= for the Parser type? (Where in the book is the Monad instance for Parser defined? It will start instance Monad Parser where.)

answered Sep 29, 2012 at 13:23

dave4420

47.2k6 gold badges121 silver badges153 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Jan Christiansen · Accepted Answer · 2012-09-29 13:26:11Z

The do notation is desugared to applications of the monad operator (>>=). More precisely, the definition of sat is desugared to the following definition.

sat p :: (Char -> Bool) -> Parser Char
sat p =
  item >>= \x -> if p x then return x else failure

The operator (>>=) first applies the item parser to the input. As you correctly observed this parser yields the first character. Then, (>>=) passes the result of the first parser to its second argument, that is, to the function \x -> if p x then return x else failure. This function checks whether the predicate is satisfied for the first character of the input stream. If it is satisfied, the function yields a parser (return x) that does not consume any input and simply yields x as result. If it does not satisfied the predicate, the function yields a parser that fails for any input (failure).

Collectives™ on Stack Overflow

Functional Parser example from Programming in Haskell

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related