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

[David Menendez]

2008/10/11 Jason Dagit <dagit at codersbase.com>:
>
> On Sat, Oct 11, 2008 at 8:55 AM, Matthew Naylor
> <mfn-haskell-cafe at cs.york.ac.uk> 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 <dave at zednenem.com>
<http://www.eyrie.org/~zednenem/>