# Difference between revisions of "Multiplate"

(An example of how to make Multiplate instaces.) |
m |
||

(10 intermediate revisions by 3 users not shown) | |||

Line 1: | Line 1: | ||

== Making a Multiplate instance == |
== Making a Multiplate instance == |
||

− | The easiest way to understand how to use Multiplate is to look at a simple example. |
+ | The easiest way to understand how to use Multiplate is to look at a simple example. We assume you have the transformers library installed. |

<pre> |
<pre> |
||

> import Data.Generics.Multiplate |
> import Data.Generics.Multiplate |
||

+ | > import Data.Functor.Constant |
||

+ | > import Data.Functor.Identity |
||

+ | > import Control.Applicative |
||

</pre> |
</pre> |
||

Line 39: | Line 42: | ||

</pre> |
</pre> |
||

− | A plate is a record type that is parametrized by |
+ | A plate is a record type that is parametrized by an applicative functor <code>f</code>. There is one field for each type in the mutually recursive structure we want to write generic functions for. Each field has type <code>A -> f A</code> where <code>A</code> is one of the data types. |

− | To use the Multiplate library we have to make <code>Plate</code> |
+ | To use the Multiplate library we have to make <code>Plate</code> an instance of the <code>Multiplate</code> class. The instance requires that we write two functions: <code>multiplate</code> and <code>mkPlate</code>. Let's define each of these functions in turn. |

<pre> |
<pre> |
||

Line 54: | Line 57: | ||

<pre> |
<pre> |
||

− | > multiplate |
+ | > multiplate child = Plate buildExpr buildDecl |

> where |
> where |
||

− | > buildExpr (Add e1 e2) = Add <$> expr |
+ | > buildExpr (Add e1 e2) = Add <$> expr child e1 <*> expr child e2 |

− | > buildExpr (Mul e1 e2) = Mul <$> expr |
+ | > buildExpr (Mul e1 e2) = Mul <$> expr child e1 <*> expr child e2 |

− | > buildExpr (Let d e) = Let <$> decl |
+ | > buildExpr (Let d e) = Let <$> decl child d <*> expr child e |

> buildExpr e = pure e |
> buildExpr e = pure e |
||

− | > buildDecl (v := e) = (:=) <$> pure v <*> expr |
+ | > buildDecl (v := e) = (:=) <$> pure v <*> expr child e |

− | > buildDecl (Seq d1 d2) = Seq <$> decl |
+ | > buildDecl (Seq d1 d2) = Seq <$> decl child d1 <*> decl child d2 |

</pre> |
</pre> |
||

Line 76: | Line 79: | ||

</pre> |
</pre> |
||

− | That's it. Now we are ready to use out generic library to process our mutually recursive data structure without using any more boilerplate |
+ | That's it. Now we are ready to use out generic library to process our mutually recursive data structure without using any more boilerplate. |

== Generic Programing with Multiplate == |
== Generic Programing with Multiplate == |
||

− | Coming Soon. |
||

+ | === Monoids === |
||

+ | |||

+ | Suppose we we want to get a list of all variables used in an expression. To do this we would use <code>preorderFold</code> with the list monoid. The first step is to build a <code>Plate</code> that handles the cases we care about. What we can do is use the default <code>purePlate</code> which does nothing, and modify it to handle the cases we care about. |
||

+ | |||

+ | <pre> |
||

+ | getVariablesPlate :: Plate (Constant [Var]) |
||

+ | getVariablesPlate = purePlate { exprPlate = exprVars } |
||

+ | where |
||

+ | exprVars (EVar v) = Constant [v] |
||

+ | exprVars x = pure x |
||

+ | </pre> |
||

+ | |||

+ | This can be written alternatively using some list comprehension tricks |
||

+ | |||

+ | <pre> |
||

+ | getVariablesPlate = purePlate {expr = \x -> Constant [s|EVar s <- [x]]} |
||

+ | </pre> |
||

+ | |||

+ | Now we can can build a plate that will get variables from all subexpressions and concatenate them together into one big list |
||

+ | |||

+ | <pre> |
||

+ | variablesPlate = preorderFold getVariablesPlate |
||

+ | </pre> |
||

+ | |||

+ | In a real program we would either put <code>getVariablesPlate</code> into <code>variablesPlates</code>'s <code>where</code> clause or else simply inline |
||

+ | the definition. |
||

+ | |||

+ | <code>variablesPlate</code> is a record of functions that will give a list of variables for each type in our mutually recursive record. Say we have an <code>Expr</code> we want to apply this to. |
||

+ | |||

+ | <pre> |
||

+ | e1 :: Expr |
||

+ | e1 = Let ("x" := Con 42) (Add (EVar "x") (EVar "x")) |
||

+ | </pre> |
||

+ | |||

+ | We can project out the function for <code>Expr</code>'s from our plate apply it to <code>e1</code> and then unwrap the <code>Constant</code> wrapper. There is a little helper function, called <code>foldFor</code>, that will upgrade of projection function to remove the <code>Constant</code> wrapper for us. |
||

+ | |||

+ | <pre> |
||

+ | >>> foldFor expr variablesPlate e1 |
||

+ | |||

+ | ["x","x"] |
||

+ | </pre> |
||

+ | |||

+ | === Traversing === |
||

+ | |||

+ | Suppose we want to recursively evaluate constant expressions in the language. |
||

+ | We can use <code>mapFamily</code> for this. |
||

+ | We define a <code>Plate Identity</code> for the functionality we care about. |
||

+ | |||

+ | <pre> |
||

+ | doConstFold :: Plate Identity |
||

+ | doConstFold = purePlate { expr = exprConst } |
||

+ | where |
||

+ | expr (Add (Con x) (Con y)) = return (Con (x + y)) |
||

+ | expr (Mul (Con x) (Con y)) = return (Con (x * y)) |
||

+ | expr x = pure x |
||

+ | </pre> |
||

+ | |||

+ | Now we can can build a plate that will repeatedly apply this transformation from bottom up. |
||

+ | |||

+ | <pre> |
||

+ | constFoldPlate = mapFamily doConstFold |
||

+ | </pre> |
||

+ | |||

+ | Let's build an declaration to test. |
||

+ | |||

+ | <pre> |
||

+ | d1 :: Decl |
||

+ | d1 = "x" := (Add (Mul (Con 42) (Con 68)) (Con 7)) |
||

+ | </pre> |
||

+ | |||

+ | We can project out the function for <code>Decl</code>'s from our plate apply it to <code>d1</code> and then unwrap the <code>Identity</code> wrapper. Again, there is a little helper function, called <code>traverseFor</code>, that will upgrade of projection function to remove the <code>Identity</code> wrapper for us. |
||

+ | |||

+ | <pre> |
||

+ | >>> traverseFor decl constFoldPlate d1 |
||

+ | |||

+ | "x" := Con 2863 |
||

+ | </pre> |
||

+ | |||

+ | == Alternative Plates == |
||

+ | |||

+ | Multiplate does not have to be used in the above way. Any structure can be made an instance of <code>Multiplate</code> as long as the following two Multiplate laws are satisfied: |
||

+ | |||

+ | <OL> |
||

+ | <LI><code>multiplate purePlate = purePlate</code> |
||

+ | <LI><code>multiplate (composePlate p1 p2) = composePlate (multiplate p1) (multiplate p2)</code> |
||

+ | </OL> |
||

+ | |||

+ | For example, Sjoerd Visscher gives [https://gist.github.com/707890 an example] of a plate where each constructor of each data type has its own field in a record structure. |
||

+ | |||

+ | == Links == |
||

+ | |||

+ | [http://hackage.haskell.org/package/multiplate Multiplate on Hackage] |

## Latest revision as of 07:47, 22 January 2012

## Contents

## Making a Multiplate instance

The easiest way to understand how to use Multiplate is to look at a simple example. We assume you have the transformers library installed.

> import Data.Generics.Multiplate > import Data.Functor.Constant > import Data.Functor.Identity > import Control.Applicative

Suppose you defined the follow set of mutually recursive data types for a simple language.

> data Expr = Con Int > | Add Expr Expr > | Mul Expr Expr > | EVar Var > | Let Decl Expr > deriving (Eq, Show) > > data Decl = Var := Expr > | Seq Decl Decl > deriving (Eq, Show) > > type Var = String

The first thing we are going to define is a 'plate' for this language.

> data Plate f = Plate > { expr :: Expr -> f Expr > , decl :: Decl -> f Decl > }

A plate is a record type that is parametrized by an applicative functor `f`

. There is one field for each type in the mutually recursive structure we want to write generic functions for. Each field has type `A -> f A`

where `A`

is one of the data types.

To use the Multiplate library we have to make `Plate`

an instance of the `Multiplate`

class. The instance requires that we write two functions: `multiplate`

and `mkPlate`

. Let's define each of these functions in turn.

> instance Multiplate Plate where

We have to write one piece of boilerplate code for `multiplate`

. However, once this is implemented, no further boilerplate code need be written.
`multiplate`

takes a `Plate`

as a parameter. The idea is that for each expression in our language we will call this a function from this `Plate`

parameter on the children of our expression and then combine the results.

> multiplate child = Plate buildExpr buildDecl > where > buildExpr (Add e1 e2) = Add <$> expr child e1 <*> expr child e2 > buildExpr (Mul e1 e2) = Mul <$> expr child e1 <*> expr child e2 > buildExpr (Let d e) = Let <$> decl child d <*> expr child e > buildExpr e = pure e > buildDecl (v := e) = (:=) <$> pure v <*> expr child e > buildDecl (Seq d1 d2) = Seq <$> decl child d1 <*> decl child d2

Notice that when an expression has no children, as in the case of `v`

in `v := e`

, we simply use `pure v`

.
`pure`

is used to handle the default case in `buildExpr`

, also have no subexpressions.

Next we have to define `mkPlate`

. `mkPlate`

is a function that builds a `Plate`

given a generic builder function that produces values of type `a -> f a`

. However these generic builder functions require a bit of help. The need to know what the projection function for the field that they are building is, so we pass that as a parameter to them.

> mkPlate build = Plate (build expr) (build decl)

That's it. Now we are ready to use out generic library to process our mutually recursive data structure without using any more boilerplate.

## Generic Programing with Multiplate

### Monoids

Suppose we we want to get a list of all variables used in an expression. To do this we would use `preorderFold`

with the list monoid. The first step is to build a `Plate`

that handles the cases we care about. What we can do is use the default `purePlate`

which does nothing, and modify it to handle the cases we care about.

getVariablesPlate :: Plate (Constant [Var]) getVariablesPlate = purePlate { exprPlate = exprVars } where exprVars (EVar v) = Constant [v] exprVars x = pure x

This can be written alternatively using some list comprehension tricks

getVariablesPlate = purePlate {expr = \x -> Constant [s|EVar s <- [x]]}

Now we can can build a plate that will get variables from all subexpressions and concatenate them together into one big list

variablesPlate = preorderFold getVariablesPlate

In a real program we would either put `getVariablesPlate`

into `variablesPlates`

's `where`

clause or else simply inline
the definition.

`variablesPlate`

is a record of functions that will give a list of variables for each type in our mutually recursive record. Say we have an `Expr`

we want to apply this to.

e1 :: Expr e1 = Let ("x" := Con 42) (Add (EVar "x") (EVar "x"))

We can project out the function for `Expr`

's from our plate apply it to `e1`

and then unwrap the `Constant`

wrapper. There is a little helper function, called `foldFor`

, that will upgrade of projection function to remove the `Constant`

wrapper for us.

>>> foldFor expr variablesPlate e1 ["x","x"]

### Traversing

Suppose we want to recursively evaluate constant expressions in the language.
We can use `mapFamily`

for this.
We define a `Plate Identity`

for the functionality we care about.

doConstFold :: Plate Identity doConstFold = purePlate { expr = exprConst } where expr (Add (Con x) (Con y)) = return (Con (x + y)) expr (Mul (Con x) (Con y)) = return (Con (x * y)) expr x = pure x

Now we can can build a plate that will repeatedly apply this transformation from bottom up.

constFoldPlate = mapFamily doConstFold

Let's build an declaration to test.

d1 :: Decl d1 = "x" := (Add (Mul (Con 42) (Con 68)) (Con 7))

We can project out the function for `Decl`

's from our plate apply it to `d1`

and then unwrap the `Identity`

wrapper. Again, there is a little helper function, called `traverseFor`

, that will upgrade of projection function to remove the `Identity`

wrapper for us.

>>> traverseFor decl constFoldPlate d1 "x" := Con 2863

## Alternative Plates

Multiplate does not have to be used in the above way. Any structure can be made an instance of `Multiplate`

as long as the following two Multiplate laws are satisfied:

`multiplate purePlate = purePlate`

`multiplate (composePlate p1 p2) = composePlate (multiplate p1) (multiplate p2)`

For example, Sjoerd Visscher gives an example of a plate where each constructor of each data type has its own field in a record structure.