Re: [Haskell-cafe] How to translate Haskell to other languages?

2008/10/11 Jason Dagit :

On Sat, Oct 11, 2008 at 8:55 AM, Matthew Naylor wrote:

...

Here is the result of (manually) applying D to the list-reversing program.

If nil() corresponds to [] in Haskell, then how did you arrive at this definition? As Derek Elkins points out your transformation is a CPS based. So I'm going to guess that c is the continuation and n represents the nil?

...

def nil() : return (lambda n: lambda c: n)

I think this is known as the Church encoding. The parameters n and c describe what to do with lists that are constructed with [] and (:), respectively. You can do this in Haskell, as well: newtype List a = List { unList :: forall b. b -> (a -> List a -> b) -> b } nil :: List a nil = List (\n c -> n) cons :: a -> List a -> List a cons x xs = List (\n c -> c x xs) foldListR :: (a -> b -> b) -> b -> List a -> b foldListR f z l = unList l z (\x xs -> f x (foldListR f z xs)) compare foldListR with foldr: foldr f z [] = z foldr f z (x:xs) = f x (foldr f z xs) Essentially, it represents the data in terms of how you pattern match on it. You can in principle pull this off for any Haskell type, but the resulting code isn't anything you'd want to work on manually. -- Dave Menendez http://www.eyrie.org/~zednenem/