Practical reasons for Church Encoding

Question

Church encoding (aka Visitor Pattern) is a way of representing data as functions: instead of

data T = C1 F1 F2 | C2 F3 F4

you can define

data T = T (forall r. (F1 -> F2 -> r) -> (F3 -> F4 -> r) -> r)

. Although the ability to represent anything as a function is nice, I've always thought the first version was preferable because it's cleaner and it does not require language extensions (explicit forall). However, you can sometimes find church-encoded data in public libraries. What are the advantages of using that?

The examples of church encoding in public libraries:

• Iteratee
• Revision control monad
• (please help me extend the list)

Selden

Answer 1

This corresponds to continuation-passing style with multiple continuations, and is done for performance: the explicit construction and destruction of data is avoided, instead passing control directly based on the output of the pattern-match that would be immediately done instead. This doesn't always result in improved performance, but when it does it can be fairly significant.

Basically, you can think of it as data vs. control. If what you're doing is essentially similar to control in nature — such as the success and failure branches of a parser — then the control-based representation might well be superior. Otherwise, stick with data.

Slam