33
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$ – nixeagle Mar 25 '12 at 20:28
  • $\begingroup$ 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. $\endgroup$ – nixeagle Mar 25 '12 at 21:21
  • 1
    $\begingroup$ The comments of @nixeagle are mostly correct but given with the wrong attitude. 1) Monad programming is not that needed in Mathematica, and it is not a paradigm to be look up to. 2) Monad programming is easily done in Mathematica, using Mathematica's core principles. $\endgroup$ – Anton Antonov Jun 12 '17 at 12:08
18
$\begingroup$

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.
$\endgroup$
2
$\begingroup$

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:

syntax examples of monad comprehensions

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.

$\endgroup$
3
  • 1
    $\begingroup$ Interesting post from a didactic point of view (especially for comparisons with Haskell, Scala, F#), but not that useful because: (1) the posted code needs more explanations (or related links) and better usages examples, and (2) the programmed comprehension functionalities are easily done with the core Mathematica/WL functions. $\endgroup$ – Anton Antonov May 28 '17 at 17:03
  • $\begingroup$ You are right that the code needs more explanations. I think the comprehensions style is easier for many (including me) to read and understand, especially if there is existing familiarity with set theory. I would like to make the case that code can be clearer and more easily modified using this style, which is probably why the implementors of e.g. Haskell's comprehensions syntax decided to do it (comprehensions are readily defined from other monadic functions, or directly using core language functions, this applies as well to Haskell as to WL). I'll provide some better examples when I can. $\endgroup$ – fairflow Jun 13 '17 at 11:41
  • 1
    $\begingroup$ Thank you for your response! Do you mind posting it as a response in the discussion "How and why to use monadic programming in Mathematica?"? (Probably, together with other explanations as your answer opening.) $\endgroup$ – Anton Antonov Jun 13 '17 at 11:49
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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? $\endgroup$ – Piotr Semenov Apr 20 '12 at 10:44
  • $\begingroup$ @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. $\endgroup$ – celtschk Apr 24 '12 at 21:19
  • $\begingroup$ 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. $\endgroup$ – Piotr Semenov Apr 30 '12 at 11:41
  • $\begingroup$ Please, see my answer below for monads Maybe and State. $\endgroup$ – Piotr Semenov Apr 30 '12 at 13:04
  • $\begingroup$ 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. $\endgroup$ – jVincent Oct 4 '12 at 21:01
-1
$\begingroup$

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:

enter image description here

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:

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.