Parselets :: safe, single expression parser/pretty-printer serializer/deserializer

I want to express  the parse and pretty-print of a data structure with a single, declarative expression. I also want to make the syntax general enough to adapt to any serialization/deserialization format, binary or textual, and for any string format.

The first is done. I used the idea of Formlets and applied it to parse-print. This is the resulting expression for an  example datatype:

data P = I {getInt :: Int} | S {getString :: String} deriving (Show)

This is the instance of  Parselet for P to parse/print from/to Strings (see the class definition below)  :

instance ParseLet P String where

    parse mpx  =   I <$> (str "I" *> pString (sel getInt mpx ))
              <|>  S <$> (str "S" *> pString (sel getString mpx ))

The single expression produces the text serialization and deserialization:

main =  do
   putStrLn . serial $ S "hi"
   print (deserial "I 2" :: Maybe P )

This is the output:

e>runghc demos\parselets.hs
S {getString="hi"}
Just (I 2)


To do this,I  coded some applicative instance that wraps both a non monadic parser and a non-monadic serializer. I also found a way to express  conditional serialization as an Alternative expression within an Applicative expression (sel), so that it mimic the shape of an applicative parser expression


Because there is a single expression for serialization and deserializartion,  it can be guaranteed  that the first will produce a result that will be read without errors by the second:

This is the complete source of parselets.hs:

{-# LANGUAGE ScopedTypeVariables ,TypeSynonymInstances ,FlexibleInstances ,MultiParamTypeClasses #-} import Control.Applicative import Data.Monoid import System.IO.Unsafe import Control.Exception as CE import Data.List(isPrefixOf) import Data.Maybe import Debug.Trace (!>)= flip trace data RS v a= RS v (Maybe a) newtype RSView v a= RSView{runRSView :: (v -> (RS v a,v))} instance Functor (RSView v) where fmap f (RSView p)=RSView $ \v -> let (RS v1 x, r)= p v in (RS v1 (fmap f x),r) instance Monoid v => Applicative( RSView v) where pure a = RSView ( \v -> (RS mempty $ Just a,v)) RSView f <*> RSView g= RSView ( \v -> let (RS v1 k,r) = f v (RS v2 x,r2) = g r in (RS (mappend v1 v2) (k <*> x),r2)) instance Monoid v => Alternative (RSView v) where empty= RSView $ \v -> (RS mempty Nothing, v) RSView f <|> RSView g= RSView ( \v -> let rs@(RS v1 k,r) = f v in case k of Just _ -> rs Nothing -> g v ) class Monoid v => ParseLet a v where parse :: Maybe a -> RSView v a -- must not use pattern match serial :: ParseLet a v => a -> v serial x = getSerial $ (runRSView $ parse (Just x)) mempty where getSerial (RS v _,_)= v deserial :: ParseLet a v => v -> Maybe a deserial str= getDeserial ( (runRSView ( parse Nothing)) str) where getDeserial (RS _ x,_)= x sel f mpx= unsafePerformIO $ CE.handle (\(e:: SomeException) -> return Nothing) $ let x= f $ fromJust mpx in x `seq` return (Just x) pString :: (Read a, Show a)=> Maybe a -> RSView String a pString (Just fpx)= RSView $ \str -> (RS (show$ fpx) (Just fpx),str) pString Nothing = RSView $ \str -> case readsPrec 1 str of [] -> (RS " " Nothing, str) (x,r):_ -> (RS " " (Just x), r) --str :: String -> RSView String () str s= RSView ( \st -> let readit= if isPrefixOf s st then Just() else Nothing in (RS (s++" ") readit , drop (length s) st)) data P = I Int | S String deriving (Read, Show) instance ParseLet P String where parse mpx = I <$> (str "I" *> pString (sel (\(I x) -> x) mpx )) <|> S <$> (str "S" *> pString (sel (\(S s) -> s) mpx )) main = do putStrLn . serial $ S "hi" print (deserial "I 2" :: Maybe P )

From Monads to Monoids in a small category

"A monad is just a monoid in the category of endofunctors"

(Added 06/09/12: clarification about the nature of ' m a' from the point of view of C.Theory)

Let's start with the definition of a small category with a morphism defined by 'm' between set of objects 'a' and 'm b'. The simplest category definition would be:

{-# LANGUAGE FlexibleInstances #-}
import Data.Monoid
import Control.Monad

class Category  m a b where
 morph:: a ->  m b

Here 'm b'  is the codomain of the morphism which depends on the category instance. More on this at the end of the post. .

The other two requisites for a category according with this are an identity operation and associativity of the morphism. The first is guaranteed in Haskell by the polymorphic function 'id'.

id :: a -> a
id x = x

Lett´s modify the signature of 'id' slightly to match the Category definition as such:

return :: a -> m a

The second condition, associativity, is guaranteed by the nature of the forward chaining of operations in any programming language. (if not where that way, it would be impossible the denotational semantics of imperative languages in terms of monads, I guess)

The definition of functor According to this :

Let C and D be categories. A functor F from C to D is a mapping that:

• associates to each object  an object ,
• associates to each morphism  a morphism
• 
  

So the morphism (a -> m b) may meet the first condition. This morphism  maps elements from the set ‘a’ to elements in the set ‘m b’. The second condition is the one defined in the Haskell instance of functor:

instance Functor a where

 fmap :: (a -> b) -> (m a ->  m b)

When a and b are the same, then we have a functor.which maps elements in ‘a’ to elements in ‘m a’  (a -> m a). But are 'a' and 'm a' the same? It seems that it is not the case, but I will talk about it later.

The functor category has functors as elements and natural transformations as morphisms, Additionally, the functors have a double nature as maps between points in ‘a’ (a -> ma) and as maps between morphisms (fmap) .  But a monoid is defined over elements of the set, and a monad works with morphisms (a -> m b), so we are interested on the set of elements with signature  (a -> m a) , to describe the Monoid instance for these elements.

If we try to construct the Monoid instance for any morphisms (a -> m a) . This instance demands that 'm' is a monad, that is, that the morphisms of m must  compose according with the monad laws:

instance Monad m => Monoid  (a -> m a) where

   mappend f g= \x -> do

                          y <-  f x

                          g y

   mempty=   \x -> return x

The definition of mappend is equivalent to the Kleisli operator in a Monad

(>=>) :: (a -> m b) -> (b -> m c) -> (a -> m c)

f >=> g = \x -> f x >>= g

In this case, a b and c are the same sets:

The Monoid instance e of morphisms that meet the Monad laws can be written as:

instance Monad m => Monoid  (a -> m a) where

   mappend = (>=>)

   mempty  = return

This typechecks in Haskell. But does this set (a -> m a) of maps between elements from the endofunctors have the necessary  reflexive and associative properties for being a Monoid? If you compare (1) the asociativite and identity laws of a Monoid, when applied to the morphisms between (a -> m a)  objects,  with (2) the monad laws you will conclude that (1) and (2)  are identical, and thus only the monadic morohisms form a Monoid,

The Monoid is defined within the subset of morphisms (a -> m a) which are part of the functor category, not with the set 'a' as such.  The return operation in a Monad correspond with the identity morphism in the set of such  morphisms. 

While in the IO monad, the morphisms (a -> IO a) refer to the same set ‘a’ in the domain and the codomain, (a -> Maybe a)  has one additional element (Nothing) which is terminal. 

In the case of List monad, the morphisms of the monad (a -> [a]) 'm a' is [a]. It sems quite different at first sight, But a list, as seen from the point of view of the list category, is a list of alternative arrows in the set 'a' (see the previous post).

for example the expression

f :: String -> [String]
f x= take 5 $ repeat x

can be considered as a endomorphism in the set of Strings that has five arrows. Then 'f' can be considered as a morphisn from 'a' to the set 'a' plus the empty list element (which is terminal)

'What is 'm a’ ?. Seen from the point of view of category theory, it is 'a' plus some terminal element(s).

What about the generalization for the morphisms of any ( a -> m b) being a and b of any kind? The Monoid instance can be extended to a larger class of morphisms between any Typeabe objects by assuming a of type Dynamic. So implicitly, to any a -> m b as long as a and b are Typeable:

instance Monad m => Monoid  (Dynamic -> m Dynamic) where

   mappend = (>=>)

   mempty  = return

If any 'a' with morphisms (a -> m a) is a Category, Then, I guess, the set of Typeable objects with the morphisms (Dynamic -> m Dynamic) is a Category

Even it can be extended to the endofunctors of the set of elements of any type:

data AllTypes = forall a . AllTypes a

instance Monad m => Monoid  (AllTypes-> m AllTypes) where

   mappend = (>=>)

   mempty  = return

Which implicity is a Monoid instance for any (a -> m b)

Am I wrong?. Did I miss something?

An intuitive view of Algorithms in terms of Category Theory

Inspired by this wonderful article : Why do monads matter?

A function gives one only value of the codomain for each element of the domain set (and thus it can be evaluated a single time for each input value, get its result and forgetting about doing this computation again, that is called graph reduction), 

A category (forget about laws and properties for a moment) is made of a "function generalization" that admita many arrows  from each element of the domain to many elements in the codomain. this wider concept is called a morphism (If I´m not wrong). for that matter, an statement like"getChar", that returns a different output each time can be understood mathematically only using category theory. This is the reason why Category Theory is so important for a mathematical understanding of any algorithm in any  programming language. Because an algorithm is a chain of statements, mathematically it is a chain of morphisms. Generally an algorithm has many statements like getChar that are impure , because it does something with the external world) so the algorithm when executed trough these morphisms travels different graphs on each execution.  To discover where the chain of arrows goes each time, it is necessary to execute the chain of sentences every time.

Imperative languages works "categorically" ever, so they don´t need an special syntax for doing so. It an imperative language find a pure function he will execute it again and again.. It does not know what is pure and what is not.. Haskell permits to discriminate functional code from "normal" "categorical/imperative" code, so the programmer and the compiler can make use of the mathematical properties of pure code with unique paths of execution. That permits equational reasoning and some optimizations. For example, graph reduction, explained above (equational reasoning may be considered as a mental form of graph reduction).


Because a function can not give a different result  haskell can execute it later in time in case it is needed, lazines is another optimization possible as result of the separation of pure functional code from impure code. Something that is not said about laziness is that it permits optimal coarse grained interfaces without losing performance. You can make a deserialized of a  database query result  and only the fields that you use will be deserialized when used.

Because haskell is lazy by default, it needs an special syntax for chaining impure morphisms of the type of getChar where the sequence of execution matters for the resulting output. This imperative execution model is not hardcoded in the language, but it is defined in the Monad instance, defined by a library programmer. And this execution model is not unique, but it is different for each category. The "Monad" instance of each category tell haskell how to compose morphisms for this category in order to traverse the path of execution. 

In the same way that '+' or '*' compose two numbers, the 'bind' method of the Monad instance for each category tell how to compose arrows until the path of execution is complete (that is the  sense of the akward sentence "a monad is a monoid in the category of endofunctors" . A monoid define the way of composing elements of a category. An endofunctor is a particular class of morphisms, but I said from the beginning that we must leave details aside.

Because its unique execution model, imperative languages work in a single category and have an unique execution model. Haskel mimick  other imperative languages by using the monad instance of the IO category. But new categories and execution models can be defined by the programmer.  There are some other Monadic execution models defined. The List category for example, work with all the graph paths of a morphism at the same time, not only a single result (see below). There are some categories defined to handle exceptional paths in a otherwise functional computation ( with the Maybe, Exception or Error monads of each respective category). Even there are executions that can restart graps until transactional completiion (STM) and so on.


Concerning the List category, a (pure) function  

f :: a -> [a]

that return a list can be understood alternatively as a morphism that has many graphs from each element of the domain to many elements of the  codomain. So this function can be considered a morhism in the List category and his corresponding monadic execution model. The monad instance of List permits to handle all graphs resulting from each morphism simultaneously. The computation is pure and imperative at the same time. the List monad operates with (ordered) sets instead of individual results.

Let´s look at the execution model of the list category:

instance Monad [] where m >>= k = concat (map k m) return x= [x]

In the bind (>>=) method, the morphism k is applied to all the results of the previous morphism m, (via map) resulting in a set for each value in m. Then these set of sets is unified in a single set with concat.

Oddy enough, the list monad is considered non-deterministic,. Actually, the List monad computes all possible graph simultaneously, while the IO monad traverse a different path of execution each time, so the IO should be the non-deterministic monad.

DISCLAIMER: Ths text is provided "as is" and any express or implied warranties of mathematical accuracy are disclaimed. In no event shall the author ve liable for any direct, indirect, incidental, parallel or sequential damages, including but not limited to loss of use, or business interruption. blah blah blah.

A fail-back monad

MFlow can express a complete Web navigation within a simple procedure, just like a console program. The problem of this model is the back button. There is nothing like the back button in console applications.  The user can not decide to go back in a console application. but in a Web application, the user can do it.

Since I want to go back to the code of the previous user interactions, not just to the previous statement, I need a monad transformer which permits the creation of ckeckpoints form which the computation can be resumed when the received result does not match with the output expected from the last form that was sent to the user. If the user go back, what the application receives is an output corresponding to a past interaction. Then I do not receive what I expect. I need a way to go back in my code acordingly upto the user interaction step that match the output.

Since my interaction is basically similar to a console application, this example below would be a simple console translation for my problem. liftRepeat will label the checkpoint from which I want to go back and repeat the code when fail is invoked.

test= runBackT $ do lift $ print "will not return back here" liftBackPoint $ print "will return here" n2 <- lift $ getLine lift $ print "second input" n3 <- lift $ getLine if n3 == "back" then fail "" else lift $ print $ n2++n3

Whenever the second input is "back" The procedure will go back to where liftBackPoint is. Otherwise, it will return the concatenation of the two inputs.

Here below is the failback monad transformer.  (I will not call it "backtracking" since this term has a tradition in non-deterministic logic programming). 

The monad instance is similar to what would be an identity monad transformer  as long as NoRepeat is used. But when GoBack found, the monad roll back until a BackPoint is found and the computation start again from it. 

data FailBack a = BackPoint a | NoBack a | GoBack newtype BackT m a = BackT { runBackT :: m (FailBack a ) } instance Monad m => Monad (BackT m) where fail _ = BackT $ return GoBack return x = BackT . return $ NoBack x x >>= f = BackT $ loop where loop = do v <- runBackT x case v of NoBack y ->; runBackT (f y) BackPoint y ->; do z <- runBackT (f y) case z of GoBack ->; loop other ->; return other GoBack -> return GoBack backPointReturn x= BackT . return $ BackPoint x liftBackPoint f= BackT $ f >>= \x -> return $ BackPoint x backPointHere :: Monad m => BackT m () backPointHere = backPointReturn ()

This monad does not perform exploration of alternatives as is the case of MonadPlus instances. It does not perform the kind of backtracking of "nondeterministic"  three navigations in the Prolog style. It just go back to the point where the computation can restart again in a  sequence of actions.

The chain of fail backs could go as far back as necessary, That is what I need, since the user can go back as deep in the web browser as he pleases.

In particular if the embedded monad is an state monad, the state will transport the user output back to the previous interaction 

instance (MonadIO m, MonadState s m) =>; MonadIO (BackT m) where liftIO f= BackT $ liftIO f >>= \ x -> return $ NoBack x instance (Monad m,Functor m) => Functor (BackT m) where fmap f g= BackT $ do mr <- runBackT g case mr of BackPoint x -> return . BackPoint $ f x NoBack x -> return . NoBack $ f x GoBack -> return GoBack instance MonadTrans BackT where lift f= BackT $ f >>= \x -> return $ NoBack x instance MonadState s m => MonadState s (BackT m) where get= lift get put= lift . put

These are the instances that I need to lift the computations to the failback monad.

I suspect that this monad has more applications. For example it can be used to generalize exceptions for any monad

See this short mail list discussion where Oleg shows some alternatives:

http://haskell.1045720.n5.nabble.com/Fail-back-monad-td5599230.html

An important advantage of this monad is that it is tail recursive, unlike other alternatives, and captures all the semantic of the problem and the solution in a single monad, instead of a combination of monads.