juan_gandhi: (Default)
I get totally pissed off and call those people plain idiots. Kleisli monad...
juan_gandhi: (Default)

That's James and Saunders bashing (in a generalized monoidal sense).
juan_gandhi: (Default)

List a = Codensity Endo a = forall r. (a -> r -> r) -> r -> r

nil :: List a
nil = \f z -> z

cons :: a -> List a -> List a
cons x xs = \f z -> f x (xs f z)

append :: List a -> List a -> List a
append xs ys = \f z -> xs f (ys f z)

foldr :: (a -> r -> r) -> r -> List a -> r
foldr f z xs = xs f z

Basically, it's like lambda.

Src: https://golem.ph.utexas.edu/category/2012/09/where_do_monads_come_from.html#c042100
juan_gandhi: (Default)
As promised (to myself), started writing the "three myphs of FP".

 - part 1, "not every monad is strong" 
juan_gandhi: (VP)
Categories for Scala Programmers

Pretty primitive, but well, the target audience... just to dispel some myths and clear the people's conscience.
juan_gandhi: (VP)

(10x [livejournal.com profile] _hacid_)

The list of references starts with Penrose.

author's page
juan_gandhi: (VP)
People started assuring me that Haskell streams may be empty. Meaning, not a comonad at all.
So, wtf, are they even monads? They also say a list can be infinite; well, any proof that it's still a monad? Not what you get if you build a free monoid (that's what a list is).

Or? Do they mean we actually need σ-algebras?!
juan_gandhi: (VP)
So, I've been thinking, wtf is it with Stream, why is it a monad?

First, Stream functor is representable, it's just ℕ → A - so forget about all those magic definitions.

Unit is easy to implement, it corresponds to ℕ → 1, no big deal. But flattening should be defined by ℕ → ℕ × ℕ - and there's plenty, some are good, some not.

What I discovered. Here: https://patternsinfp.wordpress.com/2010/12/31/stream-monad/ it is defined by diagonal Δ:ℕ → ℕ × ℕ - no big deal, monadic properties follow.

Except that, well, is it okay to skip values? I don't have a problem with it, but plain regular programmers must be aware, this flattening skips most of the values.

Not so in Scala. Scala people are naive in a different way. Their "flattening" of a stream of streams consists of scanning the first stream to the end, then the second... wait, are we dealing with transfinite numbers? Nobody knows, it's just funny.

Well, wait. It's not a monad. Check out this: http://zenzike.com/posts/2010-10-21-streams-and-monad-laws

The flattening that takes just the first stream out of the stream of streams, does not satisfy monad laws. So, Scala streams are not monads, you know.

Ok now. But because of this definition as representable, it's obvious that Stream can be a comonad.
Defined by a monoidal operation ℕ × ℕ → ℕ

Note the a. There's an infinite (a continuum) number of ways to define a monoid on ℕ. That's how many ways there are to define a comonad on Stream.

Actually, it's a neat way to define a comonad from a monoid. Given a monoid M, the functor M → X is a comonad.

Also, I'm afraid Kiselyov is writing something weird on all this.
But not as weird as these weird guys from IBM - https://www.ibm.com/support/knowledgecenter/SSCRJU_3.2.1/com.ibm.swg.im.infosphere.streams.spl-standard-toolkit-reference.doc/doc/functor.html - they defined a functor! Except that they are clueless.

Tell me if/where I am wrong.
juan_gandhi: (VP)
Every time you write
val myName = props.get("Name") orElse ""
you are introducing an algebra over Option monad.
Even if you have no clue what an algebra or a monad is.

Same goes for catching exceptions and returning a "default value". Now you have a category of algebras over the exception monad.

This category is called Eilenberg-Moore category for the monad. There's a couple of adjunctions of course.

Kleisli also provides a couple of adjunctions.

All possible adjunctions make a category, where Kleisli is an initial object and Eilenberg-Moore is a terminal object.

Nlab says that Kleisli can actually be embedded into Eilenberg-Moore.

Meaning, guys, you don't need to invent "default values"; just use Option[T]. Whatever. Probably hard to explain to people that are thinking in terms of saving computer memory on string instantiation.
juan_gandhi: (VP)
Say, we have a regex, right? This is a regular language; so there must be a free monad with a pretty simple structure. May be related to State monad, I guess.
juan_gandhi: (VP)
Now I want to show several examples, just as an illustration for the previous talk.

Exception Monad

Given some fixed type E (just any), exception monad is defined as the functor that maps type X to type E+X. That's assuming we have union defined and working in our category.

Why is it a monad?
1. pure: X ⇒ E+X is defined naturally
2. flatten: E+(E+X) ⇒ E+X is defined naturally

These two are behaving, as you can check. Suppose we are in a category where we can build an applicative functor out of it; what can it be? First, what's its signature? It is (E+X) × (E+Y) ⇒ E + X×Y. It is kind of obvious it is enough (and necessary) to define E×E ⇒ E. And this operation should be associative.

So we will have a semigroup; and if we have a semigroup, we will have an applicative functor.

But what semigroup is given by our magic that provides (if possible) a default monadic strength for a given monad? If you look into the details of implementation, in the first part, the operation is just the first projection, p1: E×E ⇒ E.

In plain programmatic terms it behaves like this: if we throw an exception in the first component, we do not evaluate the second component. Namely, having (E+X) × (E+Y) = E×E + X×E + E×Y + X×Y, when we flatten it to E + X×Y, the first component returns "the first exception"; the second component returns "the second exception", the third component returns "the first exception", and the fourth component returns a pair (x,y).

Having just a type E (e.g. a set E), one may have more than one semigroup defined on it. And we can have a monad E+X with monadic strength defined separately. Is there a problem with it? None; each strength, derived from the semigroup, is just another monadic strength. It satisfies all the conditions.


With lists, one can easily see that the default strength exists, and the appropriate zip operation is the following: List[X]×List[Y] ⇒ List[X×Y] is the list of all combinations of elements of the first and the second list. zip(1::2::Nil, "ab") = List((1,'a'),(1,'b'),(2,'a'),(2'b')).

Are there other ways to zip two lists? There's an interesting belief that the known 'zip' operation serves this goal: zip(list1,list2) = list1.zip(list2); this applicative functor is called 'zipList'.

No. It does not preserve identity. pure(x) cannot be a singleton list; and repeatForever(x) is not a list.

You will need a very different structure, a stream. A stream is a function from Natural Numbers Object to a type; ℕ ⇒ T. We can define zip for streams, thus making the functor applicative. And this operation actually gives us a hint how to make a stream a monad.

See, a stream of streams can be represented as a map ℕ×ℕ ⇒ T; compose it with diag:ℕ ⇒ ℕ×ℕ, and you get a new stream. pure is defined as a constant function. It is obvious that pure is a monadic unit. All that is left to check is associativity of flatten.

And this amounts to the following property: given i1:(ℕ×ℕ)×ℕ ⇒ ℕ×ℕ×ℕ where i1((a,b),c) = (a,b,c), and i2:ℕ×(ℕ×ℕ) ⇒ ℕ×ℕ×ℕ where i2(a,(b,c)) = (a,b,c). What we have to prove is that i1((a,a),a) = i2(a,(a,a)), which is kind of obvious.

Conclusion, probably

So, here we are not only lucky, we can see that in lists and streams the monad and the strength are pretty much connected.

But it is not always so; it depends. As Tom Leinster pointed, "Something to bear in mind is that strength is not a property of a monad: it's extra structure on a monad. The same monad can admit no strengths, one strength, or many strengths. (At least, I believe this to be the case. I don't know an example.) So "monad that is not strong" is a phrase comparable to "set that is not a group"." (http://mathoverflow.net/questions/85391/any-example-of-a-non-strong-monad/86914#86914 )
juan_gandhi: (VP)
This has been dragging forever. Let me cover it, shedding light to the dark corners, ok?


First, definitions. I'll try to use, as much as possible, Scala notation, and, basically, Scala terms.

A category consists of types and functions; a function is from one type to another; some functions can compose (if one starts where the other ends), composition is associative, and there's an identity function for each type.

There's more than one category in this (kind of) world. Given two categories, C and D, we can build a product category, C × D, consisting of pairs of types and pairs of functions.

Some categories have a special type called unit; every type has exactly one function to unit. Functions from unit to a type are called points or instances. Instead of writing a:1⇒A we use to write a shortcut, a:A This is just a syntactic sugar.

Another syntactic sugar is this: if we have a point a:A, its composition with a function f:A⇒B is usually thought of as an "application" of f to a, and is written as f(a):B; but remember, it is just a composition of two functions.

It is good to know what instances a type has, but, in general settings, not all properties of a type are defined by the "set" of its instances. If they are, the category is called well-pointed. Remember this word, it's important.

In the case of a well-pointed category a function f:A⇒B is fully defined by its "application" to points of A. It is important to remember that it is not always the same thing. Not every category is well-pointed.

A category may have cartesian product defined, for a couple of types, A and B, one defines A×B, with two projection functions, to A and B, such that having a function C ⇒ A×B is the same as having a pair of functions, C⇒A and C⇒B; projections provide this one-to-one correspondence.

Note, for instance, that having a couple of points, a:A and b:B is the same as having a point c=(a,b):A×B. So some people believe that a cartesian product is just a "set" of pairs.

A functor F is mapping of types from one category to types of another, and of functions of one category to functions of another, with clearly defined rules (f:A⇒B maps to F[f]:F[A]⇒F[B], composition and identity are preserved. The action of a functor on a function, F[f] is often denoted as map[F](f). Of course map[F](f) is a function from F[A] to F[B].

Note, not every category is a category of sets. For instance the category of all categories is not a category of sets. The category of monoids is not a category of sets. It is important to remember that not everything is a set. For instance, a category of sets is not (usually) a set.

Even if you think you are dealing with the category of sets, it is important to remember that there is no such thing. One can always ask "which one?", and learn that you cannot enumerate categories of sets. We know some, and many more are still hiding, nobody knows how many. We should thank Goedel for this interesting fact of life.

Also, in case you somehow did not know, axioms of any theory, including a theory of sets, are not Eternal Truths Known To The Scientists. They are just assumptions under which a theory is being developed and applied. The same is true about (a) category theory. We do not insist on associativity of functions composition. We just say that in a category, composition is associative.

All this sounds extremely trivial, so it is very frequently forgotten.


A monad is a any functor M from a category C to itself with two properties:

  • there is a unit aka "pure" function u[X]: X⇒M[X], for every X and this function behaves (commutes with other functions etc)

  • there is a monad multiplication aka flatten function flatten:M[M[X]]⇒M[X] for each X, with good properties: a) it is associative, b) unit is left and right unit for this multiplication

I'm not going into deeper details, you can find them everywhere. Just remember this funny thing, that both unit and flatten are defined for each type, and are defined naturally, so a function from A to B combines seamlessly with these.

Being a functor, a monad has map, but there's more.

def flatMap[F,A,B](f:A=>F[B]) = map[F](f).flatten

This function, flatMap, can be used to define flatten, and it satisfies the right rules, which are harder to formulate for flatMap than for flatten.

There's a belief, in Haskell circles, that each monad is also an applicative functor (defined below). This belief has just one foundation: it's based on the belief that every category is well-pointed.

Applicative Functor

There's more than one definition; I'll use the one that does not require anything else except what was defined above.

Applicative functor, aka lax monoidal functor is such a functor F that has

  • zip[A,B]: F[A]×F[B] ⇒ F[A×B] defined for all A and B, having natural properties and behaving consistently if we have three types, A, B and C;

  • pure[A]: A ⇒ F[A] that is natural and combines well with zip

There are variants of this definition, where functor strength is defined differently; this one is pretty popular in comp sci, so there.

How can it possibly be related to monads? Here is the way Haskell and Scala people define strength for any monad, just from the definition of monad:

Say we have a monad T, and a couple of types, A and B, there's a trick that produces T[A]×T[B] ⇒ T[A×B]. How? Here's the trick.

1. Define a coupler function, A ⇒ B ⇒ A×B, like

coupler: A ⇒ B ⇒ A×B = a ⇒ (b: B) ⇒ (a, b)

There’s something fishy in this definition. First, It is not a function in our category. We have a function from type A to what? To functions from B to A×B. Funny, the collection of these functions does not belong to our category. We could introduce such a type, X⇒Y, every instance of which is a function from X to Y, or we could, if possible, the sum of units indexed by functions from X to Y. In both cases we will have a type in our category, but remember, they may be distinct. Second, even if our types were covered with instances, like in a well-pointed category, it is still not always so that defining mappings on instances gives us a legitimate function (check out topological spaces, groups, etc).

We map with T, getting a function

couplerT: T[A] ⇒ T[B ⇒ A×B]

For each instance tb:T[B] we canb uild another function, lifter(tb), that takes any function B ⇒ A×B and produces an instance of T[B]:

lifter(tb): (B ⇒ A×B) => T[A×B]

lifter(tb) takes a function f from B to A×B and produces an instance tab:T[A×B] by applying map[T](f) to tb.

See, it's just a special case of map; if you are a Haskell programmer, you would think this is the same as map. Not so from categorical point of view, for a couple of reasons.

Again, this is fishy. We suddenly talk about instances of T[B] as if they are all that we need to define a function. They are not, in general settings where the category is not well-pointed. More, the mapping is from functions to a type; each function gives an instance of a type; it is not even a function in our category.

If we map lifter with map[T] (call it lifterT), we get a function from T[B ⇒ A×B] to T[T[A×B]].

Now, given a couple of instances, ta:T[A] and tb:T[B], from the first we get an instance of T[B⇒A×B], and from this instance and from tb we get an instance of T[T[A×B]]; flatten it, and voila, an instance of T[A×B].

See, we relied on well-pointedness of our category? So many times we relied on the fact that since an A can be covered by its instances, an A×B can be covered by B.

This trick does not work if our category is not well-pointed, as well as in many other occasions. E.g. it is a category of sets on which some group, or a monoid is acting. Or if we are dealing with sets that change in time. Or a category of topological spaces.

This was the first part. Next I'll write about some specific monads and non-monads.

If you want to see an example of a monad that is not strong (that is, not an applicative functor), see the bottom of this: http://mathoverflow.net/questions/85391/any-example-of-a-non-strong-monad/86914#86914
juan_gandhi: (VP)
Just agreed with Runar that, well, it's not a monad, because there's no associativity (duh)

Or? (ok, ok, lax weak pseudo promonad...)
juan_gandhi: (VP)

Или у меня синдром Даннинга-Крюгера, или я не нашел ничего, чего бы не было у Патерсона и МакБрайда, а также поразительно похожие куски на слайды моего рассказа на Codecamp в 2012-го году. Хотя, конечно, у дураков и великих умов мысли сходятся; да и у меня там не было ничего такого, что бы не написали уже Патерсон с МакБрайдом.

Или я чего-то не понял.

Но у меня в парсерах нынче подобного кода пруд пруди.

  for {(name, sDob, membernumber, claimnumber) <-
        Result.zip(props @ Name, props @ Dob, props @ MemberId, props @ ClaimNr)
       dob <- parseDob(sDob)
       stuff <- buildStuff(name, dob, membernumber, claimnumber)
      } yield stuff
juan_gandhi: (VP)

P.Chiusano, "A very simple technique for making DSLs extensible"
juan_gandhi: (VP)
presentation: http://2013.flatmap.no/blakstad.html
unfiltered library: https://github.com/unfiltered/unfiltered/blob/master/directives/README.markdown

So, the idea is, have all this http run monadic; that includes checking conditions and throwing back all those 404s, 451, 500...
juan_gandhi: (VP)
  def retrieveAllPatients(listOfProps: Seq[Props]): Result[Traversable[PatientInfo]] = {
    val listOfMaybePatients = listOfProps.zipWithIndex map (retrievePatientInfo _).tupled
    val maybeListOfPatients = Result.traverse(listOfMaybePatients)
    suspiciousError(s"Now we have all the patients, right?\n$maybeListOfPatients")

Шутки шутками, а Патерсон и МакБрайд как бы тут непосредственно вписываются.
Научите меня HoTT, и я у меня в коде будут торсоры и группы когомологий.
Смешно, конечно.
juan_gandhi: (Default)
Can't figure out.
And how it is related to cps.


juan_gandhi: (Default)

March 2017

    1 2 3 4
5 6 7 8 9 1011
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 293031 


RSS Atom

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Mar. 29th, 2017 09:08 pm
Powered by Dreamwidth Studios