On Tuesday 02 November 2010 3:11:22 pm Brandon Moore wrote:
That's surprising, I think LogicT gains significant performance from that sort of CPS conversion.
It's probably not that surprising. LogicT is an encoding of a recursive type, so there's potentially more causes for the gain. For instance, if we just look at Logic versus lists, Logic has concatenation that is O(1), and associative with regard to performance. For lists, that's O(m), and you get quadratic behavior with left-nesting. That alone may account for a lot of the performance boost, since the main idea of Logic is to be used as a monad for backtracking search, which is all concatMap. Either, on the other hand, is a non-recursive data type, so I doubt you can milk any asymptotic improvements out of an encoding. Further, GHC has fancy constructor specialization optimizations developed specifically (I think) to make using these non-recursive sum types fast. For that matter, I can't say I've benchmarked Logic against lists recently. -- Dan