juan_gandhi | Entries tagged with maybe

sassa_nf noted that in Haskell actually Reader composes with any monad. That's a pleasant surprise; and this happens due to the fact that any monad is strong in Haskell. Yes, with the same arguments as I used before, a composition of Reader with any monad is still a monad.

2. The proof of monadicity of Reader and Maybe (or any other strong monad).
I tried; it is long and boring, and there's nothing unusual there, just apply diagonals and eval, and use Yoneda lemma. No big deal, boring.

3. What is eval actually?
3.1. Formal definition.

eval: A × B^A → B

is defined via adjointness of functors X^- and -×Y, it comes from id_A: A → B.

3.2. Informal definition.
Given (a,f) ∈ A × B^A, eval(a,f)=f(a).

4. How does it all look in Java?
Given

interface Maybe<X> {
  X getOrElse(X alt);
  <Y> Maybe<Y> map(Function<X,Y> f);
  <Y> Maybe<Y> flatMap(Function<X,Maybe<Y> f);
}

with two implementation classes, Some and None (having appropriate factories),
and

abstract class Reader<E,X> {
  <X,Y> Reader<E,Y> map(Function<X,Y> f);
  <X,Y> Reader<E,Y> flatMap(Function<X,Reader<E,Y> f);
}

with a factory

  <E,X> Reader<E,X> reader(X x) { return new Reader<E,X){...}; } // constant x

and provided the implementations follows monadic laws,

We can define

class<E,X> PartialReader<E,X> extends Reader<E,Maybe<X>>{
  <X,Y> PartialReader<E,Y> map(Function<X,Y> f) { ... }
  <X,Y> PartialReader<E,Y> flatMap(Function<X,Reader<E,Maybe<Y> f) { ... }
}

and a factory

  <E,X> PartialReader<E,X> pr(X x) { return new PartialReader<E,X){...}; } // constant Some(x)

Now this PartialReader satisfies monadic laws.

I wonder, do I need to define the guts of the methods? I could, no request.

I believe we can.

Generally speaking, say, we have two monads, T and U; their composition T ∘ U is a functor which is not always a monad. Unit is okay, but multiplication, T ∘ U ∘ T ∘ U → T ∘ U does not always exist. It would exist if the two monads commuted, that if, if we had U ∘ T → T ∘ U, which is also known as traversal of U over T; in case U comes from a monoid, this is the famouse "map/reduce".

I was working on a simple example in Java programming language, say, take Reader monad and Maybe monad, the latter also known as Option in Scala and in various Java libraries. It is almost obvious that if we have a Maybe wrapped into a Reader, it cannot be naturally transformed into Reader wrapped into a Maybe.

Maybe in Java can be thought of as a function that may throw some kind of exception, and we don't care which, just catch it (and log it, that's what Java people do with exceptions).

Reader in Java can be represented as "dependency injection" - we have a function that is supposed to return something, but its behavior depends on some external circumstances unknown to client code. This is different from State, an example of which is a Random Numbers Generator; with "dependency" we are tied to the same environment during the lifetime of the program.

For the utmost simplicity, let's imagine that we have only two possible "environment values", say, DEBUG, which is either TRUE or FALSE.

So, in this case, what the client thinks of as a function: X → Y, in our Reader is actually a function: X → Y² whereby we potentially produce two values, one for DEBUG=TRUE and another for DEBUG=FALSE.

If we deal with Maybe, what a client sees as a function: X → Y is actually function: X → 1+Y, where failures map values into this 1, which in Java is represented via null.

Okay.

Now one composition is (1 + Y)² == 1 + 2×Y + Y², and the other is 1 + Y².

We can easily embed the second one into the first one, but there's no general natural way to transform the first one to the second one; what will we do with the two instances of 1×Y? Unless we have Y as an algebra over Maybe, that is, a natural transformation 1 → Y.

Nevertheless, I will show that the composition of Maybe ∘ Reader is a monad.

First, let's generalize Reader to a dependency on a certain type E of "environment: Reader<E>.

So, Reader amounts to having a functor X ↦ X^E, where unit X → X^E amounts to constant, and multiplication (X^E)^E → X^E is dual to diagonal Δ E → E×E, that is, X^Δ.

Now, can we naturally transform Reader(Maybe(Reader(Maybe(X)))) to Reader(Maybe(X))? Not only naturally, but with all the monadic properties of multiplication (unit and associativity, that is).

We have (1 + (1 + X)^E)^E, and we need to produce (1 + X)^E

This is dual to (thanks to Yoneda Lemma) having a good transformation
E × (1 + (1 + X)^E)^E → (1 + X)

Let's throw in Δ E → E×E, and build
E × (1 + (1 + X)^E)^E → E × E × (1 + (1 + X)^E)^E → (1 + X)

Using eval: E × A^E, have
E × E × (1 + (1 + X)^E)^E → E × (1 + (1 + X)^E)

So it would be enough to have a good
E × (1 + (1 + X)^E) → (1 + X)
which amounts to having

E × 1 + E × (1 + X)^E) → (1 + X)

Which is obvious: the first component maps to 1, the second is eval again.

That's it.

Questions? Errors? Remarks? Suggestions.

(One question is how come Java types are not Maybe-algebras, they are, are not they?)

В разных там WriterMonad требуется, чтобы внутре был моноид, и возникает иной раз такое ощущение, что и везде нужен моноид. Ан нет, бывает и полугруппы достаточно.

Скажем, Option[T], где Т - полугруппа, можно считать моноидом - к полугруппе присоединяется внешний нуль.

def sum(maybeX; Option[T])(maybeY: Option[T]) = maybeX match {
  case Some(x) => maybeY match {
    case Some(y) => Some(x+y)
    case None    => Some(x) }
  case None => maybeY
}

Так получается, что тот нуль, что был в T раньше, теперь не будет нулём.

Та же фигня и с мапредьюсом - в качестве типа накапливаемых значений берётся полугруппа, а нуль присоединяется внешний.

Это, заодно, ответ на мой старый вопрос - шо за моноид в мапредьюсе. Да вот этот, с присоединённым нулём.

S	M	T	W	T	F	S
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31

Observations

Views from Souths

Entries tagged with maybe

Reader and Maybe, comments

So, can we compose Reader and Maybe?

моноид из полугруппы

Profile

May 2025

Syndicate

Most Popular Tags

Page Summary

Active Entries

Style Credit

Expand Cut Tags