jckarter/clay — pull request #430 by galchinsky (2012-10-21 05:01:33+00:00)
Title: maybe, list and state monads with examples

I wanted to test a typesystem if there was a way to write generic functions that work with types like monads. I think that the result is good and can be pulled, but maybe there's another way to solve it.
Problems:
1. Type propagation is only unidirectional, so you can't write a generic function `[S, A] mreturn (a : A) : S[A] = S(A)` like in Hindley–Milner languages: return type is unbound. A workaround is to get help from the caller:
```
[S, A] overload mreturn (a : A, #S) = S(A);
overload mreturn(a : A, #Maybe[T])= Maybe[A](a);
```
You may look at the tests in this commit to be sure that it doesn't look very ugly.
2. sequence function should be `sequence(ms : Vector[M[A]]) : M[Vector[A]]` in HM-language.
In clay it is `[M when Monad?] sequence(ms : Vector[M])`. `M` is a black box. We need to extract `A` type from `M` and to change M[A] to M[Vector[A]]. This extraction can be done with 2 helper functions for every box (Maybe, Vector, State or any other).
```
[T]overload typeInBox(#Maybe[T]) = T;
[T, U] overload changeTypeInBox(#Maybe[T], #U) = Maybe[U];
```
It can be automated by the compiler, but I'm not sure that it is good idea: for example, State[S, A] has 2 parameters and you need to change only the second.
then we can write `sequence` this way:
```
[M when Monad?(M)]
sequence(ms: Vector[M]){
alias A = typeInBox(M);
alias R = changeTypeInBox(#M, Vector[A]);//result type
//...
}
```
3. Bind function should be `mbind(f : Function[A, MB], x : MA) : MB`. But lambdas needs to be casted to a Function object, so I think it's better to write `[MA when Monad?(MA)]mbind(f, x:MA)`. Resulting type is unknown again. It can be extracted via `alias MB=Type(f())` and we already have `typeInBox` to extract B. I needed this extraction only in `State` `mbind`.

4. `With` syntax seems to be broken, especially when it is nested. And in fact it is more verbose than straight operator `>>=` using. I think it's better to make a classic do-notation.

5. State monad needs capture-by-value `=>` lambdas to work properly, so it is everywhere in generic functions.