4 ms·

> Free monads permit unlimited introspection and transformation of the structure of your program; Free monads allow minimal specification of each semantic layer

> Free monads permit unlimited introspection and transformation of the structure of your program; Free monads allow minimal specification of each semantic layer, since performance can be optimized via analysis and transformation. That is not true and this overselling of the Free monad is hurting the concept. The Free monad is nothing more than the flatMap/bind operation, specified as a data-structure, much like how a binary-search tree describes binary search. And this means an imposed ordering of operations and loss of information due to computations being suspended by means of functions. You see, if the statement I'm disagreeing with would be true, then you'd be able to build something like .NET LINQ on top of Free. But you can't.

rtpg 10y ago
Maybe this is a bit trite, but isn't the ordering given in Free simply the order of the code? At what stage does loss of information happen.
- mbrock 10y ago
  Yeah, the free monad structures involve lots of lambdas. It's not so much that information is "lost", more that you cannot see beyond the next lambda abstraction. From a DSL perspective, it's like you can only inspect the program so far as to know the next statement in the "do" block. To see what the next statement will be, you need to actually evaluate the current one. Instead of free monads, if you want very analyzable structures, look at free applicative functors. "Applicative functors are a generalisation of monads. Both allow the expression of effectful computations into an otherwise pure language, like Haskell. Applicative functors are to be preferred to monads when the structure of a computation is fixed a priori. That makes it possible to perform certain kinds of static analysis on applicative values. We define a notion of free applicative functor, prove that it satisfies the appropriate laws, and that the construction is left adjoint to a suitable forgetful functor. We show how free applicative functors can be used to implement embedded DSLs which can be statically analysed." http://arxiv.org/abs/1403.0749 http://arxiv.org/abs/1403.0749
  - lmm 10y ago
    The problem is that applicative functors aren't powerful enough to allow computations that depend on previous results. I suspect what we want is something like free ArrowChoice, but I'm not aware of any work in that direction.
    - mbrock 10y ago
      You can still do a lot with applicatives, like parsing context-free languages... and even parsing context-sensitive languages. https://byorgey.wordpress.com/2012/01/05/parsing-context-sensitive-languages-with-applicative/ https://byorgey.wordpress.com/2012/01/05/parsing-context-sen... But yeah. ApplicativeDo might be useful. You would be able to see the static applicative structure as far as the next monadic bind, which lets you do interesting types of optimization, e.g. Haxl. https://ghc.haskell.org/trac/ghc/wiki/ApplicativeDo https://ghc.haskell.org/trac/ghc/wiki/ApplicativeDo https://github.com/facebook/Haxl https://github.com/facebook/Haxl
      - lmm 10y ago
        The thing is we're used to thinking in monads, and used to thinking of certain constructs as equivalent, which ApplicativeDo would break. There's a real tension between being explicit about the performance - in which case many identities no longer hold - and not. I don't know what Haxl itself does, but Fetch (which claims to be a Scala port) is kind of unsatisfactory in that regard.
    - jfoutz 10y ago
      I might be completely missing your point (my apologies if i am). applicative is for specific elements of the structure. It's totally reasonable to want access to nearby values, but that requires being a little bit tricky. You could do something like a window of averages windows = map (take 5) tails $ [1,2,3,4,5,6] and then do your fmap across that fmap sum windows For access to prior values, you need something that looks a lot more like a fold. In that kind of case, i'd point at traversable. mapAccumL (\val accumulator -> val + accumulator) 0 [1,2,3,4,5] which would gather up the sums, [1, 3, 6, 10, 15] of course, accumulator can be as fancy as you want, hashmap, set, tree, or whatever. If you can formulate a dynamic programming solution, there's generally a way to stuff that into traversable. This is sort of off the top of my head and my haskell is a bit rusty, so this probably won't compile. But i think it captures the essence.
- lmm 10y ago
  Monad linearizes the call graph; the effects of f(g, h) have to look the same as those of f(g(h)). In particular your interpreter can't parallelize, because it can't tell whether there's a data dependency between one effect and the next or not.
KirinDave 10y ago
Maybe John is attributing more magic to the common free monad patterns than is actually there? Certainly I had stars in my eyes when I first read: https://people.cs.kuleuven.be/~tom.schrijvers/Research/papers/mpc2015.pdf https://people.cs.kuleuven.be/~tom.schrijvers/Research/paper... > then you'd be able to build something like .NET LINQ on top of Free. But you can't. You sort of can. You could build an interpreter of Linq commands and then have an executor interpret that. Which I suppose could be argued is making Linq. :)
buffyoda 10y ago
Free monads can be inspected "up to the first lambda", which is always at least one operation in, and it's what enables things like purely functional mocking. However, other free structures, such as free applicatives, can be completely introspected: https://www.youtube.com/watch?v=H28QqxO7Ihc https://www.youtube.com/watch?v=H28QqxO7Ihc The point is that free monads allow introspection up to the information-theoretic limit (obviously you can't inspect a program whose structure depend on a runtime value), while transformers do not allow any introspection at all.

rtpg 10y ago

Maybe this is a bit trite, but isn't the ordering given in Free simply the order of the code? At what stage does loss of information happen.

mbrock 10y ago
Yeah, the free monad structures involve lots of lambdas. It's not so much that information is "lost", more that you cannot see beyond the next lambda abstraction. From a DSL perspective, it's like you can only inspect the program so far as to know the next statement in the "do" block. To see what the next statement will be, you need to actually evaluate the current one. Instead of free monads, if you want very analyzable structures, look at free applicative functors. "Applicative functors are a generalisation of monads. Both allow the expression of effectful computations into an otherwise pure language, like Haskell. Applicative functors are to be preferred to monads when the structure of a computation is fixed a priori. That makes it possible to perform certain kinds of static analysis on applicative values. We define a notion of free applicative functor, prove that it satisfies the appropriate laws, and that the construction is left adjoint to a suitable forgetful functor. We show how free applicative functors can be used to implement embedded DSLs which can be statically analysed." http://arxiv.org/abs/1403.0749 http://arxiv.org/abs/1403.0749
- lmm 10y ago
  The problem is that applicative functors aren't powerful enough to allow computations that depend on previous results. I suspect what we want is something like free ArrowChoice, but I'm not aware of any work in that direction.
  - mbrock 10y ago
    You can still do a lot with applicatives, like parsing context-free languages... and even parsing context-sensitive languages. https://byorgey.wordpress.com/2012/01/05/parsing-context-sensitive-languages-with-applicative/ https://byorgey.wordpress.com/2012/01/05/parsing-context-sen... But yeah. ApplicativeDo might be useful. You would be able to see the static applicative structure as far as the next monadic bind, which lets you do interesting types of optimization, e.g. Haxl. https://ghc.haskell.org/trac/ghc/wiki/ApplicativeDo https://ghc.haskell.org/trac/ghc/wiki/ApplicativeDo https://github.com/facebook/Haxl https://github.com/facebook/Haxl
    - lmm 10y ago
      The thing is we're used to thinking in monads, and used to thinking of certain constructs as equivalent, which ApplicativeDo would break. There's a real tension between being explicit about the performance - in which case many identities no longer hold - and not. I don't know what Haxl itself does, but Fetch (which claims to be a Scala port) is kind of unsatisfactory in that regard.
  - jfoutz 10y ago
    I might be completely missing your point (my apologies if i am). applicative is for specific elements of the structure. It's totally reasonable to want access to nearby values, but that requires being a little bit tricky. You could do something like a window of averages windows = map (take 5) tails $ [1,2,3,4,5,6] and then do your fmap across that fmap sum windows For access to prior values, you need something that looks a lot more like a fold. In that kind of case, i'd point at traversable. mapAccumL (\val accumulator -> val + accumulator) 0 [1,2,3,4,5] which would gather up the sums, [1, 3, 6, 10, 15] of course, accumulator can be as fancy as you want, hashmap, set, tree, or whatever. If you can formulate a dynamic programming solution, there's generally a way to stuff that into traversable. This is sort of off the top of my head and my haskell is a bit rusty, so this probably won't compile. But i think it captures the essence.
lmm 10y ago
Monad linearizes the call graph; the effects of f(g, h) have to look the same as those of f(g(h)). In particular your interpreter can't parallelize, because it can't tell whether there's a data dependency between one effect and the next or not.

KirinDave 10y ago

Maybe John is attributing more magic to the common free monad patterns than is actually there? Certainly I had stars in my eyes when I first read: https://people.cs.kuleuven.be/~tom.schrijvers/Research/papers/mpc2015.pdf https://people.cs.kuleuven.be/~tom.schrijvers/Research/paper... > then you'd be able to build something like .NET LINQ on top of Free. But you can't. You sort of can. You could build an interpreter of Linq commands and then have an executor interpret that. Which I suppose could be argued is making Linq. :)

buffyoda 10y ago

Free monads can be inspected "up to the first lambda", which is always at least one operation in, and it's what enables things like purely functional mocking. However, other free structures, such as free applicatives, can be completely introspected: https://www.youtube.com/watch?v=H28QqxO7Ihc https://www.youtube.com/watch?v=H28QqxO7Ihc The point is that free monads allow introspection up to the information-theoretic limit (obviously you can't inspect a program whose structure depend on a runtime value), while transformers do not allow any introspection at all.