8

1

Write a term on the pure untyped lambda calculus that, when applied to a church-encoded list of numbers, returns it with its numbers sorted in ascending or descending order. Church lists and numbers must be encoded as folds for their usual ADTs:

```
-- Usual ADTs for Lists and Nats (in Haskell, for example)
data List a = Cons a (List a) | Nil
data Nat a = Succ (Nat a) | Zero
-- Their respective folds are the λ-calculus representation used on this challenge
church_list = (λ c n . (c ... (c ... (c ... n))))
church_num = (λ succ zero . (succ (succ (succ ... zero))))
```

Example input:

```
(λ cons nil .
(cons (λ f x . (f x)) -- 1
(cons (λ f x . (f (f (f (f (f (f (f x)))))))) -- 7
(cons (λ f x . (f (f x))) -- 2
(cons (λ f x . (f (f (f x)))) -- 3
nil)))))
```

Example output:

```
(λ cons nil .
(cons (λ f x . (f x)) -- 1
(cons (λ f x . (f (f x))) -- 2
(cons (λ f x . (f (f (f x)))) -- 3
(cons (λ f x . (f (f (f (f (f (f (f x)))))))) -- 7
nil)))))
```

The score of a submission will be calculated as follows:

```
score(x) = 1
score(λx.t) = score(t) + 1
score(t s) = score(t) + score(s) + 1
```

Lowest score wins.

7The linked page provides three different Church encodings for lists, and there's nothing to stop it from changing in the future. In order that the question be unambiguous, you will need to define the particular encoding you have in mind explicitly in the question. (It would also be advisable to define the encoding of the numbers). – Peter Taylor – 2015-08-24T15:19:33.007

1

ascending or descending order-- why do we get to pick? – Lynn – 2015-08-24T17:02:52.057I just didn't find a reason to limit it. Why not? – MaiaVictor – 2015-08-24T17:07:29.317