Does every Symbol in Mathematica induce a monad?

Question

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?

Answer 1

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.

1. Monad Maybe:

   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[{OutputSizeLimit`Dump`boxes$ =
        Block[{$RecursionLimit = Typeset`$RecursionLimit},
         MakeBoxes[Just[3], StandardForm]
         ]
       },
      OutputSizeLimit`Dump`loadSizeCountRules[]; 
      If[TrueQ[BoxForm`SizeCount[OutputSizeLimit`Dump`boxes$, 1048576]], 
       OutputSizeLimit`Dump`boxes$,
       OutputSizeLimit`Dump`encapsulateOutput[
        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.

2. Monad State:

   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.

Answer 2

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.