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

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]&
zipping[List]:=Thread

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.

Answer 3

Does every Symbol in Mathematica induce a monad?

Yes, the monad laws are satisfied for every symbol in Mathematica with List being the unit operation and Apply being the binding operation.

So, does Mathematica provide a natural maybe-like monad for every symbol [...]

In view of the monad laws satisfaction table above the answer is "yes, kind of."

[...] and does it provide a natural framework for any explicit monadic computations?

I would say the answer is "yes" to this question. I think this way of programming of the Maybe monad is fairly straightforward.

A general approach for working with monads is described in the blog post "Monad code generation and extension" (or see Markdown version at GitHub.) That approach does not take the "algebraic type" perspective on monad programming, it uses code generation instead.

Answer 4

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.

Answer 5

I have been trying to find out how to use Either/Maybe type in Mathematica.

Unfortunately algebraic data type doesn't work very well in Mathematica, some data type definitions are complex.

I have come up a method to use them without define them. I defined Maybe type in functions.

Please notes that there are a couple of incorrect examples in some answers, for instance,

Just[3] + Just[5] == Just[8]
Just[Just[3]] == Just[3]

Maybe type doesn't work like this.

Maybe type is like a box, either it's Just a value, or it's Nothing. Before you use it, you have to unwrap the box and use the value or Nothing directly or indirectly.

Maybe

In:

Maybe[a_] := Just | $Nothing (*Do nothing, it's like a comment*)

fromJust
(*The fromJust function extracts the element out of a Just and throws \
an error if its argument is Nothing.*)

fromJust::argx = "`` is not Just";
fromJust[Just[a_]] := a
fromJust[x_] := Message[fromJust::argx, x]

fromJust[Just[3]]
fromJust[$Nothing]
fromJust[Just[Just[x]]]

fromMaybe
(*The fromMaybe function takes a default value and and Maybe value.If \
the Maybe is Nothing,it returns the default values;otherwise,it \
returns the value contained in the Maybe.*)

fromMaybe::argx = "`` is not Maybe";
fromMaybe[a_, Just[x_]] := x
fromMaybe[a_, $Nothing] := a
fromMaybe[a_, _] := Message[fromMaybe::argx, x]

fromMaybe[0, Just[100]]
fromMaybe[0, $Nothing]
fromMaybe[0, t]

LiftM2
(*Promote a function to a monad,scanning the monadic arguments from \
left to right.For example*)

LiftM2::argx = "Either `` or `` is not Maybe";
LiftM2[f_, Just[a_], Just[b_]] := Just@f[a, b]
LiftM2[f_, $Nothing, _] := $Nothing
LiftM2[f_, _, $Nothing] := $Nothing
LiftM2[f_, x_, y_] := Message[LiftM2::argx, x, y]

LiftM2[#1 + #2 &, Just[3], Just[4]]
LiftM2[#1 + #2 &, Just[5], $Nothing]
LiftM2[#1 + #2 &, t, 3]

Out:

Monad Maybe

The definition of Monad Maybe is simple.

Just[x_] \[CirclePlus] g_ := g[x]
$Nothing  \[CirclePlus] g_ := $Nothing

And it's a powerful technique.

If there is a task which has 3 subtasks. Any subtasks can go wrong, it either returns Nothing or a Just value. If any subtask goes wrong, the whole task should be stopped immediately. Before you read further, you could think how you implement it.

Implementation:

ClearAll[f, g, CirclePlus, debug, clean, build, combine]

Just[x_] \[CirclePlus] g_ := g[x]
$Nothing  \[CirclePlus] g_ := $Nothing

CirclePlus[f_, g_, h__] := (f \[CirclePlus] g)\[CirclePlus]h
CirclePlus[f_, g_] := f \[CirclePlus] g

debug[name_, Just[x_]] := (Print@name; Just[x])

1
ClearAll[clean, build, combine]
clean[x_] := (Print["Failed: clean"]; $Nothing)
clean[100] \[CirclePlus] build \[CirclePlus] combine

2
ClearAll[clean, build, combine]
clean[x_] := debug[clean, Just[x + 1]]
build[x_] := (Print["Failed: build"]; $Nothing)
clean[100] \[CirclePlus] build \[CirclePlus] combine

3
ClearAll[clean, build, combine]
clean[x_] := debug[clean, Just[x + 1]]
build[x_] := debug[build, Just[x + 1]]
combine[x_] := (Print["Failed: combine"]; $Nothing)
clean[100] \[CirclePlus] build \[CirclePlus] combine

4
ClearAll[clean, build, combine]
clean[x_] := debug[clean, Just[x + 1]]
build[x_] := debug[build, Just[x + 1]]
combine[x_] := debug[combine, Just[x + 1]]
clean[100] \[CirclePlus] build \[CirclePlus] combine

Out: