# Does every Symbol in Mathematica induce a monad?

From my question about types in Mathematica, I assume that every Symbol in Mathematica is a type if it appears as a Head of some expression.

So I can implement operators for monad associated with that Symbol (let it be F for instance):

1. monad lift function (return in Haskell notation) is just return[p_] = F[p];
2. monad bind function (>>= in Haskell notation) is just a rule bind[F[p_], f_] := F[f[p]] (as monad Maybe is for example).

From point of view of category theory, in Mathematica one can define some common rules for symbols to model monad multiplication (just flatten of repeating Head): monadMultiplyRule = {p_[p_[params___]] -> p[params]}. So expression F[F[F[p_]]] //. monadMultiplyRule will be just F[p].

Also all monad axioms are satisfied:

1. return acts as a neutral element of bind: bind[return[p], f] is F[f[p]] and bind[F[p], Identity] is F[p];
2. sequential bind of two functions f and q is the same as a single bind with their "composition" Bind[F[f[p]], q]: Bind[Bind[F[p], f], q] and Bind[F[f[p]], q] produce both the same result F[q[f[p]]].

So, does Mathematica provide a natural maybe-like monad for every symbol and does it provide a natural framework for any explicit monadic computations?

-
Very nice question! I too am familier with haskell and the other functional languages. However, I'm unaware of any monadic builtins within Mathematica proper. Mathematica is essentially a glorified pattern matcher, which means it ought to be possible to write a Monadic extension to MMA using the Notation  package to implement monadic operators. When I get a chance later today, I may expand this comment to a proper answer, but I think this might get folks thinking in the meantime. – nixeagle Mar 25 '12 at 20:28
The more I think about your question the more I think the answer is yes to the question in the title. But not sure (I need to think) and no to the questions at the end. There is no natural framework for explicit monadic computations in Mathematica like that which exists in Haskell that I am aware of. But! There is nothing stopping us from "hacking" in one as folks do to emulate OOP style programming. I'll try to formulate a proper answer soonish. – nixeagle Mar 25 '12 at 21:21

Mathematica provides a perfect way to define monad by setting UpValues and DownValues of some symbol. Please, find specifications for monads Maybe and State below.

DownValues[Just] = {Just[(a: Just[x_])] :> Just[x]};
UpValues[Just] =
{(expr: (op: Except[Just | List | Trace | UpValues | DownValues])[
a___, Just[b_], c___]) /;
!MatchQ[
Unevaluated[expr],
HoldPattern[If[__, __, Just[x_]] | If[__, Just[x_], __]]
] :> Just[op[a, b, c]]};


Rule from DownValues[Just] stands for monad Maybe multiplication law. That is removing of head duplicates. Rule from UpValues[Just] stands for bind operation of monad Maybe. One need to use special pre-condition for this pattern because Mathematica uses some wrapping code to convert evaluating/reducing expression in standard form by low-level call MakeBoxes. For example, let's see this wrapping code:

Hold[
If[False, 3,
With[{OutputSizeLimitDumpboxes$= Block[{$RecursionLimit = Typeset$RecursionLimit}, MakeBoxes[Just[3], StandardForm] ] }, OutputSizeLimitDumploadSizeCountRules[]; If[TrueQ[BoxFormSizeCount[OutputSizeLimitDumpboxes$, 1048576]],
OutputSizeLimitDumpboxes$, OutputSizeLimitDumpencapsulateOutput[ Just[3],$Line,
\$SessionID,
5
]
]
],
Just[3]
]
]


That's why rule from UpValues[Just] has special pre-condition for being inside of condition expression. Now one can use symbol Just as a head for computations with exceptions:

UpValues[Nothing] = {_[___, Nothing, ___] :> Nothing};
Just[Just[123]]
(*
==> Just[123]
*)

Just[123] + Just[34] - (Just[1223]/Just[12321])*Just[N[Sqrt[123]]]
(*
==> Just[155.899]
*)


Thanks to @celtschk for great comments of this point.

return[x_] := State[s \[Function] {x, s}];
bind[m_State, f_] := State[r \[Function] (f[#[[1]]][#[[2]]] & @ Part[m, 1][r])];
runState[s_, State[f_]] := f[s];


For monad State I didn't use UpValues and DownValues just for similarity with Haskell notation. Now, one can define some sequential computation as State value with complex state logics as a monadic computation by using return and bind operations. Please, see an example:

computation =
Fold[bind, return[1],
Join[{a \[Function] s \[Function] {a, a + s},
b \[Function] s \[Function] {b, s + b/(3 s)},
c \[Function] s \[Function] {c, s + (s^2 + c)}},
Array[x \[Function] a \[Function] s \[Function] {a, s}, 300]
]
];


To get more effective computation one can use runState operation:

Fold[#2[#1[[1]]][#1[[2]]] &, runState[23, return[1]],
Join[{a \[Function] s \[Function] {a, a + s},
b \[Function] s \[Function] {b, s + b/(3 s)},
c \[Function] s \[Function] {c, s + (s^2 + c)}},
Array[x \[Function] a \[Function] s \[Function] {a, s}, 3000]
]
]
(*
==> {1, 3119113/5184}
*)


Conclusion:

1. Ideas of rule-based programming and using Head as type identifier allow user to express any(?) programming concept in Mathematica. For example, as it has just been shown, monads State and Maybe from Haskell;
2. Using of UpValues and DownValues for assigning rules to symbols and using of generalized operations (such as bind is) allow user to put expressions in different monadic environments.
-

If I understand your explanation correctly, the following definitions should implement a Maybe monad:

_[___, Nothing, ___] ^:= Nothing;
Just[Just[a_]]:=Just[a]
Just/:(f:Except[Just])[a___,Just[b_],c___]:=Just[f[a,b,c]]


Now you may write e.g.

Just[2]+Just[3]
(*
==> Just[5]
*)
2+Just[3]
(*
==> Just[5]
*)
2+Nothing
(*
==> Nothing
*)


Note however that this does not play nice with Mathematica's special functions, e.g.

Hold[Just[3]]
(*
==> Just[Hold[3]]
*)


Of course one would want that expression to remain unevaluated.

One solution to this would be to replace Except[Just] by Except[Just|Hold|HoldForm|Trace|TracePrint] and just hope that no function has been forgotten. Or maybe one should just exclude all functions having a Hold* attribute.

-
Thank you for a nice answer! I thought about solution like yours. But in Mathematica 8 I have next problem: UpValues[Just] = {Just[Just[x_]] :> Just[x], (op : Except[Just])[a___, Just[b_], c___] :> Just[op[a, b, c]]}; Plus[Just[2], 3] does not works as patterns = {Just[Just[x_]] :> Just[x], (op : Except[Just])[a___, Just[b_], c___] :> Just[op[a, b, c]]}; Plus[Just[2], 3] //. patterns. For first way, answer will be Just[Just[Just[5]]]. And for second way, answer will be as I expected: Just[5]. Do you know the reason of this? – Piotr Semenov Apr 20 '12 at 10:44
@spk: You have to wrap the left side of the rules in HoldPattern: patterns={HoldPattern[Just[Just[x_]]]:> Just[x], HoldPattern[(op : Except[Just])[a___, Just[b_], c___]]:> Just[op[a, b, c]]}; Plus[Just[2], 3] //. patterns gives Just[5], and the same is true for UpValues. – celtschk Apr 24 '12 at 21:19
HoldPattern is a good point, but pattern (op: Except[Just])[a___, Just[b_], c___] can match expressions like Just[Just[x_]] because Mathematica convert each value to standard boxes by low-level call of MakeBoxes. So define monad "bind" pattern as UpValues[Just] = {HoldPattern[(op: Except[Just])[a___, Just[b_], c___]] :> Hold[op[a, b, c]]}. Then Mathematica produces some deboxing code (and cheking current session params) for value Just[Just[3]]. So one has to check this to define correct rules for Maybe monad. – Piotr Semenov Apr 30 '12 at 11:41
Please, see my answer below for monads Maybe and State. – Piotr Semenov Apr 30 '12 at 13:04
I think your comment on the behavior of Hold is misplaced. It is doing exactly what should be expected, Hold isen't intended to prevent UpValues. If you want to protect against UpValues, you should use HoldComplete. This behavoir is also documented in the documentation center of Hold. – jVincent Oct 4 '12 at 21:01

Perhaps this alternative approach is useful? Many years ago, before I stumbled on this site, I wrote a package for monad comprehensions with parallel generators (think Thread), which I found a very useful feature of early Haskell compilers and missed in MMA. I simply implemented the formal semantics given in a paper I found on the topic. I added some syntax with the Notation package which allows me to write things such as:

SetAttributes[comprehend,HoldRest]

comprehend[m_, e_, True]:= unit[m][e]
comprehend[m_, e_, q_]  := comprehend[m,e,q,True]

comprehend[m_,e_,generator[p_,l_],q__]:=
Module[{ok}, ok[_]:=zero[m]; ok[p]:=comprehend[m, e, q]; bind[m][ok,l]]

comprehend[m_,e_,zipgen[gens__],q__]:=
Block[{x},
comprehend[m, e,
generator[comprehend[m,x,generator[generator[x_,_],
{gens}]],
zipping[m][comprehend[m,l, generator[generator[_,l_],{gens}]]]],q]]

(*  assume everything not a generator or a parallel generator is a test *)
comprehend[m_,e_,b_,q__]:=If[b,comprehend[m,e,q],zero[m]]

zero[Maybe] := None
unit[Maybe] := Some
bindMaybe[_,None] := None
bindMaybe[f_,Some[x_]] := f[x]
bind[Maybe] := bindMaybe
zipping[Maybe] := (Message[comprehend::nozip,Maybe];zipping[])

zero[List]:={}
unit[List]:={#}&
bind[List]:=Flatten[#1 /@ #2,1]&

pluck[e_,l_] := Block[{x},comprehend[List,x,generator[x_,l],x=!=e]]

removeDups[{}] := {}
removeDups[{h_,l___}] := Prepend[pluck[h,removeDups[{l}]],h]

zero[Sets] := {}
unit[Sets] := {#}&
bind[Sets] := removeDups[Flatten[#1 /@ #2,1]]&
zipping[Sets] := (Message[comprehend::nozip,Sets];zipping[])

zero::usage="The zero of a monad (if any)";
unit::usage="The unit of a monad";
bind::usage="The bind function of a monad";
zipping::usage="The zipper for a monad (if any)";
comprehend::usage="A monad comprehension (requires a zero)";
zipgen::usage="The constructor for parallel generation";
generator::usage="The constructor for generation";
comprehend::nozip="Zipping not implemented for 1";
removeDups::usage="Remove duplicates from a list";
Maybe::usage="The (name of the) Maybe monad";
Sets::usage="The (name of the) Set monad";
`

I'd be interested if anyone finds this adds something useful.

-