FYI, I implemented an error monad using this church-encoded either instead of the conventional either. my thought was that since you skip the conditional at each bind call you'd get better performance. I was quite mistaken. Max On Nov 2, 2010, at 6:40 AM, Jeremy Shaw wrote:

Looks a lot like Church encoding to me:

http://en.wikipedia.org/wiki/Church_encoding

It was first discovered by the guy who invented lambda calculus :p

- jeremy

On Nov 1, 2010, at 5:28 PM, Andrew Coppin wrote:

...

The other day, I accidentally came up with this:

{-# LANGUAGE RankNTypes #-}

type Either x y = forall r. (x -> r) -> (y -> r) -> r

left :: x -> Either x y left x f g = f x

right :: y -> Either x y right y f g = g y

This is one example; it seems that just about any algebraic type can be encoded this way. I presume that somebody else has thought of this before. Does it have a name?

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

On Tue, Nov 2, 2010 at 2:11 PM, Brandon Moore wrote:

...

From: Max Cantor Sent: Tue, November 2, 2010 7:58:49 AM

FYI,

I  implemented an error monad using this church-encoded either  instead of the conventional either.  my thought was that since you skip the  conditional at each bind call you'd get better performance.  I was quite  mistaken.

That's surprising, I think LogicT gains significant performance from that sort of CPS conversion.

Was your code like this?

newtype ErrorC e a = ErrorC (runErrorC :: forall r . (e -> r) -> (a -> r) -> r)

instance Monad (ErrorC e) where  return x = ErrorC (\fail succeed -> succeed x)  ErrorC part1 >>= f =     ErrorC (\fail succeed -> part1 fail (\a -> runErrorC (f a) fail succeed))

instance MonadError e (ErrorC e) where  throwError e = ErrorC (\fail succeed -> fail e)  catchError m handler = ErrorC (\fail succeed ->     runErrorC m (\err -> runErrorC (handler err) fail succeed) succeed)

In a monad transformer, performing a CPS translation has the benefit of being able to implement bind, return and other effects without having to pass through operations on the wrapped monad. This could be part of the performance improvement you're seeing. Antoine

On 01/11/2010 10:40 PM, Jeremy Shaw wrote:

Looks a lot like Church encoding to me:

http://en.wikipedia.org/wiki/Church_encoding

It was first discovered by the guy who invented lambda calculus :p

Yes, well, the various Church encodings and the lambda calculus in general are where I got the idea. I was just wondering if there's a specific term for using this in concrete programs rather than as a theoretical exercise, that's all.

Jon, you beat me to it. I was going to mention Ponder. But Ponder did have a builtin type, it had the function type built in. :) -- Lennart On Tue, Nov 2, 2010 at 9:47 PM, Jon Fairbairn wrote:

Andrew Coppin writes:

...

The other day, I accidentally came up with this:

|{-# LANGUAGE RankNTypes #-}

type  Either  x y=  forall r.  (x ->  r) ->  (y ->  r) ->  r

left :: x ->  Either  x y left x f g=  f x

right :: y ->  Either  x y right y f g=  g y

|

This is one example; it seems that just about any algebraic type can be encoded this way. I presume that somebody else has thought of this before. Does it have a name?

You could try reading my PhD thesis! http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-75.html contains a link to the full text scanned to a pdf. (That -- 1985 -- was a long time ago. One thing I really regret about it is that there should have been a comma between "simple" and "typed" in the title. I suspect people think "simply typed" when they see it). It isn't hard to read (one of my examiners said it made good bed-time reading).

Anyway, the relevant part is that Ponder was a programming language (Stuart Wray even wrote a GUI programme in it) that had (in principle) no built-in types, relying on the type system being powerful enough to express anything and the optimiser being good enough to convert them to something more sensible. In practice neither was /quite/ true, but it got quite close.

-- Jón Fairbairn                                 Jon.Fairbairn@cl.cam.ac.uk http://www.chaos.org.uk/~jf/Stuff-I-dont-want.html  (updated 2010-09-14)

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe