Implement a Monad

Question

A monad is a type that wraps another type, that represents the available operations on the wrapped type. Monads have the following associated operations, where M is the monad type, and T and U are any type:

• A type constructor that defines a new type M[T] that can hold some type T.
• A type converter that wraps a value and returns an instance of the monad: unit: (T) -> M[T]
• A combinator that unwraps the monad instance, performs a provided operation on the contained value, then returns the wrapped result: bind: (M[T], (T) → M[U]) → M[U]

These operations have the following properties, given some function f and g, and a value x, where <-> is equivalence:

• unit is a left-identity for bind: bind(unit(x), f) <-> f(x)
• unit is a right-identity for bind: bind(x, unit) <-> x
• bind is associative: bind(x, lambda a: bind(f(a),g)) <-> bind(bind(x, f), g)

Your goal is to write the shortest three functions, code snippets, and/or full programs that implements the above three operations. You must indicate which function/code snippet/program is which operation, as well as show the three properties of unit and bind above.

Note: If your language does not have the ability to declare a new type, you may instead replace your type constructor with an explanation on how your monad is represented in your language.

Note: You may use built-ins, but trivial substitutions, such as preprocessor directives (e.g. C++ #define M std::optional) or type aliases (e.g. Rust type M<T>=Option<T>), are not allowed. Solutions without built-ins are highly encouraged.

Note: Identity monads, single-valued monads, and other similar trivial monads are allowed; the challenge is to implement any one specific monad. However, you will get brownie points if your monad is able to wrap any valid type in your language.

• pxeger: "you will get brownie points if your monad is able to wrap any valid type in your language" - Is this not a necessary condition for M to be a type constructor (with the constraint that such a type must be well-kinded)?
• pxeger: You say there should be 3 separate programs, but since the unit and return programs will have to depend on the type-constructor-definition program for type information (except in silly cases), is it ok to specify all three things in one program?
• bigyihsuan: @pxeger Yes, that's fine. I do say 3 separate programs, but they can be also 3 functions, code snippets, programs, etc. in any combination. That's what I meant with the and/or
• bigyihsuan: @pxeger People in the sandbox asked whether trivial monads were valid submissions; for this challenge they are, but I would also like to see non-trivial monads.
• xnor: I think the appeal of open-ended-function challenges is that deciding which function is golfiest to implement is an interesting puzzle in itself. But having mathematically trivial options available, like the identity monad and single-valid monad, makes for a boring choice that produces boring golfs. Just encouraging solvers to choose interesting non-built-in monads makes it more a popularity contest to "do a cool thing". I think a better challenge would ask to implement a specific monad.

Answer 1

Haskell, 22 bytes

data M t=R t
R x%f=f x

Attempt This Online!

First, a definitely-correct answer. This is the identity monad: the type constructor is called M, the unit constructor is called R, and the bind combinator is called (%).

I defined a Monad instance in the footer to demonstrate that the operations have the correct types. I hope it's clear why the monad laws hold.

---

Pure Haskell, 12 bytes

data M t
z=z

Attempt This Online!

By "pure" I mean with no exceptions and no unsafePerformIO etc.

Highly debatable, but I think it's technically valid. My type constructor is called M (the resulting type just happens to have no values), my unit constructor is called z, and my bind combinator is also called z. Here's my proof of the monad laws:

1. We must prove z(z(x), f) <-> f(x). If f has type a -> M b for some a and b, then since there are no values of type M b, f must never return (and since we're in "pure" Haskell, f must be a simple infinite loop). Likewise z(z(x), f) will never return because z will enter an infinite loop, so the two expressions are equivalent.

2. We must prove z(x, z) <-> x. Similarly to the above, x has the type M a for some a, which means evaluating x will never return. Equally, z(x, z) will never return, so they're equivalent.

3. Very similar.

---

Pure, halting Haskell, 22 bytes

data M t=R
r _=R
_%_=R

Attempt This Online!

Another silly one. This requires that f has no side effects and always halts.

---

In fact, since not taking input at all is a valid standard I/O method, you could just have this:

Pure, halting Haskell, 10 bytes

data M t=R

Attempt This Online!

Here, my type constructor is called M, my unit constructor is called R (just make sure not to pass it any arguments), and my bind combinator is also called R (also no need to pass the arguments).

---

If I can argue this "I/O method" is allowed for the 3rd monad, maybe you can argue that this alone is valid for the 2nd monad? unit and bind take input by... not being called at all?

data M t

---

There's probably room for some more silly-but-valid Monads. But here's a non-trivial one - the Option monad:

Haskell, 30 bytes

data M t=N|R t
N%_=N
R t%f=f t

The unit constructor is called R, and the bind combinator is called (%).

Attempt This Online!

Answer 2

C++20 (gcc), 60 bytes

template<class T>struct M{T t;auto b(auto f){return f(t);}};

Where M is the monad, which allows types to be constructed by instantiating the template:

using Type = M<int>;

Values can be wrapped by using the converting constructor which is generated by the compiler automatically:

auto value = Type{42};

Although thanks to template argument deduction it's also possible to just write auto value = M{42}. And binding works by calling the member function b():

auto value_squared = value.b([](auto x){ return M{x * x}; });

Try it online! (Except at the time of writing, TIO is using an old version of GCC that doesn't fully support C++20 yet.)

Answer 3

OCaml, 37 bytes

type 'a m=M;;let u x=M;;let b x f=M;;

This implements a single-valued monad with constructor u and bind operation b.

And for an example of a non-trivial monad, let's see Reader<int> monad in 53 bytes:

type 'a m=int->'a;;let u x _=x;;let b x f s=f(x s)s;;

Answer 4

Javascript, 1 byte

0

This monad is isomorphic to Identity (). All values of the monad are 0.

The expression 0 defines a "function" with zero arguments (as in Haskell) that works as both unit and bind. As pxeger noted, this bends our rules very much, but I think it's still fun to think about, so I posted this.