Is Free more efficient in moon?

[Kesanov]

I have recently read an article called modern functional programming which makes some nice use of free monads (currently moon is using Free to express IO, but instead of ADT it uses strings).

The only problem with Free is its poor performance (unless you have supercompiler) - at least that's why it is slow in languages like Haskell. But isn't moon different, because it has #?

[VictorTaelin]

No, not because # on this case. It is the church-encoding. It has O(1) (not O(N)) monadic bind (and concatenation, etc.). For example,

list0 = cons => nil => (cons 1 (cons 2 (cons 3 (cons 4 (cons 5 nil))))
list1 = cons => nil => (list0 cons (cons 6 nil))
list2 = cons => nil => (cons 6 (list0 cons nil)) 

Here, list1 appends 6 to the end of list0, and list2 appends 6 to its beginning. Both take O(1) time. With Haskell's ADTs, inserting on the end would take linear time. Haskell has church-encoded free monads too.

[Kesanov]

I see, so is there then any point in using mtl instead of free?

[VictorTaelin]

Currently what I'm doing for side effects is basically free, except with less indirections. See here. This was how I was doing it initially. Notice though how many intermediate types and transformations the free monad approach uses. In the end, all that we want is build an ADT monadically. Free monads aren't necessary for that!

By just building church-encoded ADTs with the bang notation, we can get the same benefits (purifying "side-effective" code [which is obvious as Moon is pure]) with added simplicity and, of course, performance. Check out random and blockies for some examples. In particular, this function shows very well how I apply that to express "side-effective" calls (createColor and randomGenerate) inside seemingly pure code.