Monads are techiques of composing functions defined on types. We shall describe some examples of functions (relations) composition of kind maybe or option monad.
From a point of view of a VFP programer (relational database) monads are also a way of thinking, looking at a problem and analyzing it. Mostly all VFP programmers have written maybe monads. They use them. We shall explain monads in a systematic way.
In this article we shall concentrate on functions composition and their use in the SQL queries.
Let us start with a simple VFP monad:
Replace price with price + 3 && MONAD 1
This VFP command is a monad. This function do a transformation on the data in a record. Let us write it in a more complicated way and analyze it:
Replace price with
fp(price)
Function fp(price)
Return price+3
We can use also the closure:
Function fpc()
Return price+3
And the command:
Replace price with fpc()
This commad does four operations:
1) Read the value price from the record in a table (for example, using a function xxx not visible by the programmer). This function takes a value from a table, an »outside world«.
2) Call the function fpc on the value returned by a function xxx,
3) Call the VFP function Replace on the value returned by a function fpc.
4) Put the value in a record (using for example the function to write yyy). It returns the new value to the »outside world«.
To replace a value in a character field we need another monad, for example:
Replace name with name+«xxx« && MONAD 2
In this example we have a new type, a new function fpc and a new monad. This monad transformation is not visible to the programer. She/he knows only the type of the value and the transformation function. We can look at this as a »main effect« replace, and two »side effects« read and write to the table.
Excesize: Write a monad for a logical type transformation and analyze the Replace comand.
For example the function x**2 is not always the same in VFP. We have a table, in it two columns: C1 of type N5,2 and C2 N10,2. This two functions has different domains, so are different. We can change (enlarge the column C1 to N10,2) and the function x**2 is now identical on boath domains.
In VFP we have also anaother type of function amplification. For example, we have a column C1 (N10,2). We change its structure and alow also null values in it. We have amplified (enlarged, changed) the column type. It is no more only Numeric, it alows (alternatively) also null's to be written in it. This is an option type (Numeric,null). This modiffication creates another problem: The function x**2 doesn't know how to write a null in this column!!! Theoretically, this is not a mathematical problem. There are languages without »nulls«, so this is in some way a VFP problem: how VFP manipulate nulls?
Let us experiment with a table. Modiffy a structure of a column C1 to allow it to accept null values and run this commannds:
Replace c1 with 5 && wittes 5
Replace c1 with
null && wittes null
Replace c1 with
»xxx« && throw an excepti
on
The Replace command finds out (from the type of C1-Numeric) that the value »xxx« is not a correct type.
The replace command »knows« how to manipulate a new option (amplified) type.
We have a problem with our function f(x)=x**2: it can't put a null value in a field C1. For example,
Replace C1 with f(C1+3) puts only real numbers in the column C1.
Let us ampliffy our function f(x)=x**2 to opeate in the same way as a command replace.
Function fu(x)
If vartype(x)=«X«
Return null
Else
Return f(x) && can be x**2
Endif
Endfunc
The domain (input) of this mapping are the real numbers or a null value. The same is for its output. We have a mapping fu: option (real,null) -> option(real,null). It is an amplified mapping fu.
Now we can write:
X=null
Replace C1 with fu(x)
&& put a null in a record
.
Our function fu(x) puts a null in a record, it behave the same way as a Replace (or SQL insert or SQL update) command.
This new mapping is an inside VFP extention: we have add to VFP a new type and a new mapping.
It is easy to compose »pure« functions, for example: F(y)=y**2, g(x)=x+1 and the composition is F(x)=(x+1)**2.
Note. This composition is not comutative, we can't write f(g(x))=g(f(x)) as g(f(x)=x**2 +1. If we call the functions in a revers order, we get a new function.
The new amplified »functions« are not »pure« function and we have some problems in composing them, for example for the »amplified« g(x) we have:
Function ga(x)
If vartype(x)=«X«
&&null
Return null
Else
Return g(x)
Endif
Endfunc
The same »if« command we add to a function fa(y). Theirs composition is:
Function compoFaGa(x)
If x=null
Return null
Else
If g(x)=null
Return
null
Else
Return
(x+1)**2
Endif
Endif
Endfunc
In this function we have nested if statements. This pattern is frequent, when we compose »amplified« functions, so we can create a mathematical »formula« for this composition. We shall create two simple functions (formula) to compose the functions without the nested if statements. This »simplified« composition is know as maybe or option monad. The result of this composition is a new composable function: we can compose it with other functions.
There are various ways we write mathematicaly equivalent functions. In VFP we can generate acceptable results also using functions that are not mathematicaly equivalent.
Note. Later we shall see also other non mathematical looks at a function. Some times compilers optimize functions evaluation (transform a function); a compiler can also detect errors in a mathematicaly correct functions, especially when we compose them.
FUNCTION priceold(x)
IF value/x>1
RETURN x
endif
endfunc
FUNCTION quantold(x)
IF x<>0
RETURN x
ENDIF
endfun
It is difficult to compose this two function in a mathematical way. But in VFP we can compose in this way:
function
pricequantold()
iif (x<>0,
iif(value/x>1,x, return 999999999),return 999999999)
endif
The function pricequantold is a composition of the two functions: priceold and quantold. It return a numeric value. We can use this function with a litle bit forced convention that 999999999 is a non existent value. Later we shall present a better composition.
FUNCTION price(x)
IF value/x>1
RETURN x
ELSE
RETURN null
endif
endfunc
A function priceold(x) is a little bit "defformated". To make it more composable, we transform it in the function price. The function price has a new domain, the old enlarged with a null.
FUNCTION goodstype(x)
&& a closure on gt
DO case
case gt="1"
RETURN x
CASE gt="2"
RETURN (x*90/100)
otherwise
RETURN .null.
endcase
endfunc
FUNCTION quant(x)
IF x=0
RETURN .null.
ELSE
RETURN x
ENDIF
endfun
Let us analyze these functions from a composable point of view.
All the three functions price, goodstype and quant have as argument an
1) Numeric value or a null value (a type).
They also return the same type (for a VFP programer a litle bit strange type an option). They return a
2) Numeric value or a null value (in some languages a touple, a pair, a choice).
The functions price and priceold are mathematically two different functions. When we add a return value null to the function priceold and get a function price, we add it a "null" and we get a composable function (small, simple, foolish but efficient transformation). We shall see it efficiency in a SQL example.
Normally, we compute the function values in this way: z=f(g(x)), where x is from a set of real numbers. For every x we compute y=g(x) and after that z=f(y).
Example 1. Mathematical function on a domain of real numbers.
Z=F(x)
F(x)=G(x)**2
G(x)=x+5
X=2, g(x)=7, z=49
Example 2. Function with restriction.
Y=sqrt(x)
A function y is defined only for x>=0.
For x=4 we have y=+2 and y=-2.
Example 3. Mathematical function on a new domain (a type)
X=2, quant(2)=2
X=0, quant(0)=null
The domain of a function quant is »larger« than real numbers, it is (R,null). In VFP this is a type Numeric: it accept real numbers and null and returns real numbers and null. We can use the same function on a character type.
The important conclusion is: In VFP (and also in other languages) the function quant depend of the type of its argument.
FUNCTION funallseq()
y=goodstype(x) && if y=null stop execution, exit
the nested composition
if vartype(y)=X«
return y
endif
x=price(y)
&& price is a continuation of goodstype
if
vartype(x)=«X«
return null
endif
z=quant(x)
RETURN z
ENDFUNC
The function funallseq is simmilar to funallimp. It is written in an explicit way: in each step we call a new function using local variables y and x. We test the value's type and if we have a null value, we exit the chain. It is written as a chain of computations (actions).
Note. There are problems with this function: the code become less readable.
Note. A function priceL:
FUNCTION priceL(x)
IF value/x>1
RETURN x
ELSE
RETURN .f.
endif
ENDFUNC
has two return types: numeric and logical. It is composable and simmilar to price, but as we shall see later there can be problems using such functions in SQL queries.
In VFP we use a maybe monad when we compose functions useing nested if statements or simmilar commands. Let us see some examples of problems in writting the SQL queries:
SELECT id,CAST(quant(x)
as N(10,2)) as x from test INTO CURSOR xx (A)
(DON'T USE)
The query (A) has to create a cursor xx with an equal numbers of rows as the original (all id). In some rows there will be null values (rows with x=0).
test
id quantity value gt
1 5 50.001 1
2 0 0.001 1
3 7 60.001 1
4 8 5.002 2
5 9 90.002 2
6 10 100.002 2
7 0 11000.002 3
8 2 120.002 3
9 13 130.003 3
We run this query on a table test and get an error "field quantity doesn't accept null values". We have a correct mathematical and VFP function, but the compiler ("VFP engine") cann't detect the type of the new column. What is going on?
The composed functions execute in a lazzy way. The first computed value (on a first record) is numeric, the second is null and VFP throw an error.
Can we help the VFP engine? Let us try with a new composition:
SELECT
id,CAST(IIF(VARTYPE(quant(quantity))="X",null, quant(quantity))) as
N(10,2)) as quantity from test INTO CURSOR xx
(B)
Note. null is of vartype X.
We add an IIF statement to the query to add it the possibility to detect the type for the field quantity. We have done a new small, foolish thing, a monad.
Making monad is not a cheap operation, but is efficient.
Note. Funcions composition is asociative but not neccesary comutative. You can compose, for example in these way:
quant(price(x)) is not equal to price(quant(x)).
We have composed functions in an intuitive way, but there is a simple rule (method) how to do this.
Creating mybe monads in VFP
Monads in VFP are simmilar to macro commands and we use them to compose functions mostly of the same type.
From a mathematical point of view we can formalize the mybe monad.
1) Let us start with an identity function (it is very simple, the most difficult part is to read the mathematical notation, so we need some experience):
function idnet(x)
if vartype(x)=«X«
return null
else
return x
endif
endfunc
Its goal is to extract the value from the environement. An example, how we use it:
?ident(5) && return 5
?ident(null) &&return null
We have an identity function for a »type numeric«, but it can be usable also for a »type caracter«. We are manipulating amplified types, defined on domains with null values.
Note. Monads are in relation with types. Fo example, we are speaking of a mybe monad for type numeric. It is very simmilar to a maybe monad for a character type.
Whay doing such computation?
When a value is wrapped in a context (in our case a function environement), you can’t apply a normal function to it. For example, if x is a value in a text file, you have to extract a value (open a file and do some read), and then you can applay a function on this value. The ident function extract the value from its context.
2) The next function is a bind. It is similar to a BINDEVENT function: It bind two functions. Let us write it:
Function bindm(f1,f) && for a numeric type
IF
VARTYPE(f1)="X"
RETURN
null && exit
endif
mv=evaluate(f1) &&
extract the monadic value
IF VARTYPE(mv)="X"
RETURN
null && exit
else
mv=LTRIM(STR(mv)) &&
transform it in a correct form
Return
f+"("+mv+")"
endif
ENDFUNC
The function bindM extract the monadic value (mv) from its context (closure, datatable, cursor, string) usig a command EVALUATE(mv). If the result is null it stops execution and return a null value. Otherwise it calls a function f on this monadic value mv. In the next examples I shall explain how to use this function (it is very simple):
Example 4. A theoretical example.
x=null
ff=bindM
("ident(x)","price")
?ff && price(null)
?EVALUATE(ff) && null
When we bind an ident function with a function price, it returns a function price, as ident is a neutral element (like one for multiplication).
Note. The returned value ff is a function (enclosed in quotation marks or an expression), not a »classic« VFP value.
The function priceold(x) is not defined for x=null. We can lift it (»do a makeup«) with this command:
X=null
?priceold(x)
&& generate an error
bindm("ident(x)","priceold") && returns null
A composition of the ident function with another function is called lifting. The composition of priceold and ident gives us an amplified function that manage also nulls.
Instead of a bindm we frequently use a helper function:
function dobind(mv,f)
return evaluate(bindM (mv,f)
Example 5.
FUNCTION pricetype(x)
return bindM
("goodstype(x)","price")
endfunc
We bind the functions goodstype and price and obtain a new function pricetype(x). It is the same, as if we call goodstype(quantity) and then price.
Let us test the function pricetype():
quantity=5
x=2
value=2
gt="2"
? pricetype(quantity)
&& returns price(2),
quantity 4.5=5*90/100
?EVALUATE(pricetype(x)) && returns null, 2/4.5<1
We can use the function eval(pricetype(x)) as a macro.
Example 6.
We shall bind the function quant(x) with a function pricetype(x) from Example 5.
FUNCTION
quantpricetype(x)
return bindM
("quant(x)","pricetype")
endfunc
A function quantpricetype() is a composition of a function pricetaype from Example 5 and the function quant. Using bind we can compose functions and obtain new composable functions.
The function bindM ("quant(x)","pricetype") can be written in a pseudo code:
bindm (quant,price, goodstype)=
quant
price
goodstype
From a nested composition of if statements we have composed a sequential block of functions or a macro function.
Example 7.
We can use the composed functions as macro commands and write the query (B) in this way:
SELECT id,CAST(IIF(VARTYPE(quantpricetype(quantity))="X",
null, value/quantpricetype(quantity)) as N(10,2)) as quantity, gt, value,
quantity as oldval from test INTO CURSOR xx
Example 8. Parse an array.
In an array find the first occurence of 0,2.
DIMENSION ar[5]
ar[1]=5
ar[2]=0 && afer that is 2
ar[3]=2 && find this element
ar[4]=0
ar[5]=3
Note. A simmilar problem is find the first occurenc of the characters "tu" in a string "cfkumtuab". We are parsing an array.
We have two if statements (two predicates):
pred1="ar[i]=2"
and
pred2="oldelement=0".
Let us write two (composable) functions:
FUNCTION
predicate() && logic not based
on ar
IF EVALUATE(pred1)
RETURN null
ELSE
RETURN .t.
ENDIF
ENDFUNC
A function predicate is a closure with two alternative returns values .t. or null.
FUNCTION oldel() && logic not based on ar
IF evaluate (pred2) && oldelement=0
RETURN null
ELSE
RETURN .t.
ENDIF
endfunc
This is our second condition. oldel is a bindable function and is simmilar to a function predicate.
FUNCTION predicatetwo()
RETURN EVALUATE(bindM
("oldel()","predicate()")
&& functions order metters
endfunc
This is a composition of the functions oldel and predicate. It is a closure. We have used a maybe monad bind functio (bindM).
FUNCTION findZeroTwo()
DO WHILE not
isnull(predicatetwo()) AND i<ALEN(ar)
i=i+1
old1=oldelement
oldelement=ar[i]
ENDDO
?"element",i,"old
value",old1,"new value",oldelement
RETURN oldelement
ENDFUNC
In a function findzeroTwo we have a do loop with an increasing i (a closure). We exit from the loop when the predicatetwo is equal null. In it we have the two conditions.
oldelement=-1
*ar, pred1, pred2 are
defined here
i=1
findZeroTwo() && return 2
We can use the function findzeroTwo as a macro (a clousre) . Its variables are ar, pred1, pred2, i. We can find the first occurence of every pair of elements values in an array. This function is an inside extension of a VFP language (simmilar as LINQ extensions functions in C#). Also ours predicate strings are similar to anonymus functions in C#. They are without names. In C# you have more possibilities to compose anonimus functions, but also in VFP you can create interesting composition (without delegates).
Note.In this example we have used a maybe monad bind. Behaind the scene we have managed also the state monad ( variables i, oldelement). In the next article we shall ilustrate the state monad.
Example 9. Parse a table.
In a table Test find a first record where the occurence of the value of the quantity in two consequtive records is 0,2. This example is simmilar to Example 8. We are serching records instead of array elements. We will serch useing a table and a do loop.
Let us present only the modiffied functions from Example 8.
FUNCTION findZeroTwoF()
DO WHILE (NOT
ISNULL(predicatetwo())) AND NOT EOF()
old1=oldelement
oldelement=quantity
skip && logic based on ar
ENDDO
IF EVALUATE(pred1)
?"old value",oldelement,"new
value",quantity
RETURN quantity
ELSE
?"Not found"
RETURN null
endif
ENDFUNC
A do while loop executes till it finds the two values in sequence.
CLOSE DATABASES all
CLEAR
USE test
pred1="quantity=2"
pred2="oldelement=0"
oldelement=-1
findZeroTwoF() && return 2
We run the function findZeroTwo on a table test. It finds the 0 in row 7 and the 2 in row 8.
Example 10. SQL parser.
We shall solve the problem from example 9 using a SQL query (SQL as a parser).
CLOSE DATABASES all
CLEAR
pred1="quantity=2"
pred2="oldelement=0"
oldelement=-1
SELECT id,CAST(IIF(VARTYPE(predicatetwo())="X",null,predicatetwo())
as N(10,2)) as quantity,quantity as q,gt ,value from test INTO CURSOR xx
*SELECT id,quantity as
q,gt ,value from test INTO CURSOR xx WHERE ISNULL(predicatetwo())
BROWSE && for id=8
The first query generates a cursor. Two records has quantity=null.
The second query (with a *) generates a cursor with two records.
Normally, in VFP we manage relation between two tables (records in this tables). In this query we have put in relation the two consequtive records in one table. We navigate on a "pair" of records. The relation is inside the table and not between tables. We are »inspecting« the inside of a table. These are monads.
Example 11. Option values in a table. A complicated example.
fruits oranges
id fruitcat weigth gr id fruitcat name price val id
1 oranges 50.00 1 1 oranges or.first c. 4 FR 1
2 bananas 0.00 1 2 oranges o.2 3 IT 2
1 apples 60.00 1 3 oranges o.3 2 IT
3 oranges 5.00 2 4 oranges o.4 1 ES
4 oranges 90.00 2
2 apples 100.00 2
apples
id fruitcat name price
1 apples a.1 2
2 apples a.2 1
We have a table fruits, oranges, apples and bnanas. The table bananas is simmilar to a table oranges. A table apples is different from a table oranges, it is without a column VAL.
The problem is to bind the table fruits with oranges, apples and bananas to get prices, names and other fruits data. The field ID in table fruits is a fruit id. For example the ID in
a first row (1) for oranges is equal to a id for apples in a third row (1). A fruit in a table fruits is identiffyed by a pair (id, fruitcat). We extract this pair (tuple) from a table fruit, unwrap it to get the information about a table name, open the table (switch to a work area) and seek the pair in the appropriate table. When we find the pair, we get the data (price, name....).
Mathematically we have a "function" (relation) with an argument of three types (apples, oranges and bananas).
One solution is to create a special option (either) type fruitcat:(apples,oranges,bananas) (a tuple).
In VFP you don't have a type Option. A workaround is to store it, for example, as a character (container) (fruitcat as in our example) or you create three columns with some empty values.
When we wrap (extract) the value of a column (fruitcat), we have a character and we need a function to extract the "real" value.
When you extract it (you get for example oranges, you "bind" oranges to a table oranges (In two sentences I have created a monad: extract and bind).
We have this logical problem:
If oranges
Return oranges
else
if apples
return apples
else
if bananas
return bananas
endif
endif
endif
Using monads (in our case the Option or Maybe monad) you can make the code block of nested if statement more readable.
Note. If you have many nested block of code, think about a maybe-option monad.
Our functions are:
function ident() && this simple function is called
identity function (like a number 1), a neutral function)
return fruitcat
ENDFUNC
function
bindM(mv,f) && mv is a function
that extract a value (apple or orange or fish)
x=EVALUATE(mv) &&
this is a function that gets the value, p.e. oranges
* I have extracted the
value x and I know which is my "partner table"
x=LTRIM(TRIM(x))
do case
case x="oranges" && bind me to the table oranges
cattab="oranges"
indcat="idor" && idor is the name of the
index on the field id in a table oranges
case x="apples" && bind me to the table apples
cattab="apples"
indcat="idap"
case x="bananas" && bind me to the table bananas
cattab="bananas"
indcat="idba"
otherwise
**** error management
without try
endcase
return EVALUATE(f) && eval on a record
endfunc
A function bindM extract the value fruitcat (using the function ident), pattern match this value, generate a table name , an index name and call a function F on these values.
FUNCTION callsub() && seek in an appropriate table
SELECT (cattab) && can run also without this
command, using another seek command
SET ORDER TO (indcat)
SEEK m.x
?"found",m.x,name && name is from table cattab
SELECT fruit && can run also without this command
ENDFUNC
The function callsub has two parameters: a table name and an index name. It seek using an index and return the data from a table. Let us see how to use it:
CLEAR
CLOSE DATABASES
SELECT 0
USE bananas
SELECT 0
USE apples
SELECT 0
USE oranges
SELECT 0
USE fruit
DO WHILE NOT EOF()
*extract the value
(ident) and ssek in appropriate table (callsub)
bindM("ident()","callsub()")
&&instead of a normal select and seek
SKIP
enddo
return
A do loop in this program scan a table fruit, using a bindm etract the values from its record, switch to another table, seek the ID and return the data.
Example 12. SQL for example 11.
We can solve the problem using higher abstraction, a SQL command. Let us write it in two steps:
SELECT * FROM
oranges UNION (SELECT *,"" as
val FROM apples) UNION (SELECT *
FROM bananas) INTO CURSOR xor
SELECT A.*,
B.name,b.price,b.val FROM fruit A left JOIN xor B ON A.id=B.id ;
AND
LTRIM(TRIM(A.fruitcat))=LTRIM(TRIM(B.fruitcat)) INTO cursor x1
The first query can be a VFP view or adapter; a databse infrastructure object.
The nested if statements in our example are written as a sequence of SQL commands (see xor). This transformation is a beauty of monads.