[Haskell-cafe] CPS Error Monad
dan.doel at gmail.com
Tue Nov 2 16:54:46 EDT 2010
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
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.
More information about the Haskell-Cafe