[Haskell-cafe] CPS Error Monad

[Dan Doel]

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