Church encoding of lists using right folds and dif

Question

Here is the sequential question after

How to store data of a functional chain of Monoidal List?

and

Extracting data from a function chain without arrays

and here I would like to express my respect and appreciation for contributors to my Questions, especially by @Aadit M Shah and @user633183

Now, this question is opened to clarify the similarities and differences or relation between Difference list and Church list

.

---

Difference list

https://stackoverflow.com/a/51320041/6440264

A difference list is a function that takes a list and prepends another list to it. For example:

const concat = xs => ys => xs.concat(ys); // This creates a difference list.

const f = concat([1,2,3]); // This is a difference list.

console.log(f([])); // You can get its value by applying it to the empty array.

console.log(f([4,5,6])); // You can also apply it to any other array.

The cool thing about difference lists are that they form a monoid because they are just endofunctions:

const id = x => x; // The identity element is just the id function.

const compose = (f, g) => x => f(g(x)); // The binary operation is composition.

compose(id, f) = f = compose(f, id);                   // identity law
compose(compose(f, g), h) = compose(f, compose(g, h)); // associativity law

Even better, you can package them into a neat little class where function composition is the dot operator:

class DList {
    constructor(f) {
        this.f  = f;
        this.id = this;
    }

    cons(x) {
        return new DList(ys => this.f([x].concat(ys)));
    }

    concat(xs) {
        return new DList(ys => this.f(xs.concat(ys)));
    }

    apply(xs) {
        return this.f(xs);
    }
}

const id = new DList(x => x);

const cons = x => new DList(ys => [x].concat(ys));   // Construct DList from value.

const concat = xs => new DList(ys => xs.concat(ys)); // Construct DList from array.

id . concat([1, 2, 3]) = concat([1, 2, 3]) = concat([1, 2, 3]) . id // identity law

concat([1, 2]) . cons(3) = cons(1) . concat([2, 3]) // associativity law

You can use the apply method to retrieve the value of the DList as follows:

class DList {
    constructor(f) {
        this.f  = f;
        this.id = this;
    }

    cons(x) {
        return new DList(ys => this.f([x].concat(ys)));
    }

    concat(xs) {
        return new DList(ys => this.f(xs.concat(ys)));
    }

    apply(xs) {
        return this.f(xs);
    }
}

const id = new DList(x => x);

const cons = x => new DList(ys => [x].concat(ys));

const concat = xs => new DList(ys => xs.concat(ys));

const identityLeft  = id . concat([1, 2, 3]);
const identityRight = concat([1, 2, 3]) . id;

const associativityLeft  = concat([1, 2]) . cons(3);
const associativityRight = cons(1) . concat([2, 3]);

console.log(identityLeft.apply([]));  // [1,2,3]
console.log(identityRight.apply([])); // [1,2,3]

console.log(associativityLeft.apply([]));  // [1,2,3]
console.log(associativityRight.apply([])); // [1,2,3]

An advantage of using difference lists over regular lists (functional lists, not JavaScript arrays) is that concatenation is more efficient because the lists are concatenated from right to left. Hence, it doesn't copy the same values over and over again if you're concatenating multiple lists.

---

Church Encoding List

As an alternative to the encoding using Church pairs, a list can be encoded by identifying it with its right fold function. For example, a list of three elements x, y and z can be encoded by a higher-order function that when applied to a combinator c and a value n returns c x (c y (c z n)).

https://stackoverflow.com/a/51420884/6440264

user633183's solution is brilliant. It uses the Church encoding of lists using right folds to alleviate the need for continuations, resulting in simpler code which is easy to understand. Here's her solution, modified to make foldr seem like foldl:

const L = g => function (x, a) {
    switch (arguments.length) {
    case 1: return L((f, a) => f(g(f, a), x));
    case 2: return g(x, a);
    }
};

const A = L((f, a) => a);

const xs = A(1)(2)(3)(4)(5);

console.log(xs((x, y) => x + y, 0));        // 15
console.log(xs((x, y) => x * y, 1));        // 120
console.log(xs((a, x) => a.concat(x), [])); // [1,2,3,4,5]

Here g is the Church encoded list accumulated so far. Initially, it's the empty list. Calling g folds it from the right. However, we also build the list from the right. Hence, it seems like we're building the list and folding it from the left because of the way we write it.

---

If all these functions are confusing you, what user633183 is really doing is:

const L = g => function (x, a) {
    switch (arguments.length) {
    case 1: return L([x].concat(g));
    case 2: return g.reduceRight(x, a);
    }
};

const A = L([]);

const xs = A(1)(2)(3)(4)(5);

console.log(xs((x, y) => x + y, 0));        // 15
console.log(xs((x, y) => x * y, 1));        // 120
console.log(xs((a, x) => a.concat(x), [])); // [1,2,3,4,5]

As you can see, she is building the list backwards and then using reduceRight to fold the backwards list backwards. Hence, it looks like you're building and folding the list forwards.

---

What I like to see in Diffrence List is

1. It seems natural and straightforwad to understand.
2. With concattation (flatten), it forms monoids
3. Identity element is identity function, and no need for external initial values provided.

What I don't like

1. At least, the sample code provided depends on JavaScript Array

What I like/dislike in Church List is, in fact, the opoosite of the above.

I like

1. It's indpendent of JavaScript Array implementation, and it can define operations by itself : user633183's solution

I dislike

1. I don't know why it must be not left but right fold?

a list can be encoded by identifying it with its right fold function

2. Unclear for the realation to Monoids

3. Especailly, Nil is not Identity element( = identity function), and the sample code need for external initial values provided.

So, what I am curious is is there any formalization of Diffrence list like Church-list.

The specificaton would be

• Basically, it's a difference list

• Indenpendent of JavaScipt Array implementation

• The initial value is the built-in identety function.

Thsnk you.

Answer 1

I don't know why it must be not left but right fold?

There is no such thing as "it must be not left fold" or "it must be right fold". My implementation was a choice and I provided you with a very small program to give you the confidence to make choices on your own

Unclear for the relation to Monoids

The implementation I gave for append is the monoid binary operation, nil is the identity element.

const nil =
  (c, n) => n

const cons = (x, y = nil) =>
  (c, n) => c (y (c, n), x)

const append = (l1, l2) =>
  (c, n) => l2 (c, l1 (c, n))

// monoid left/right identity
append (nil, l) == l
append (l, nil) == l

// associativity
append (a, append (b, c)) == append (append (a, b), c)

Especailly, Nil is not Identity element( = identity function), and the sample code need for external initial values provided.

No, nil is the identity element as shown above.

---

Your string of questions seems to, in general, be about various ways to implement a list-style data type without using JavaScript compound data [] or {}.

In reality, there are countless ways to implement a list. There are many conventional designs of course, but if your goal is to create one on your own, there is not a "best" or even "better" type. Each implementation is designed around a set of criteria.

Difference lists and Church's right-fold lists are just two possible encodings. We can use an entirely different encoding for a simplified list –

const nil =
  () => nil

const cons = (x, y = nil) =>
  k => k (x, y)

This list can be folded left-wise or right-wise

const foldl = (f, init) => l =>
  l === nil
    ? init
    : l ((x, y) => foldl (f, f (init, x)) (y))

const foldr = (f, init) => l =>
  l === nil
    ? init
    : l ((x, y) => f (foldr (f, init) (y), x))

Common map and filter functions implemented trivially with foldlr

const map = f =>
  foldr
    ( (acc, x) => cons (f (x), acc)
    , nil
    )

const filter = f =>
  foldr
    ( (acc, x) =>  f (x) ? cons (x, acc) : acc
    , nil
    )

map (x => x * x) (autoCons (3, 4, 5))
// == autoCons (9, 16, 25)

filter (x => x !== 4) (autoCons (3, 4, 5))
// == autoCons (3, 5)

Notice how these are essentially identical to the previous implementation even though nil and cons construct an entirely different data structure. This is the power essence of data abstraction.

length and toArray need no change. We can implement Monoid interface –

const append = (l1, l2) =>
  l1 === nil
    ? l2
    : l1 ((x, y) => cons (x, append (y, l2)))

// left/right identity
append (nil, l) == l
append (l, nil) == l

// associativity
append (a, append (b, c)) == append (append (a, b), c)

append (autoCons (1, 2, 3), autoCons (4, 5, 6))
// == autoCons (1, 2, 3, 4, 5, 6)

Monad? Sure –

const unit = x =>
  cons (x, nil)

const bind = f =>
  foldl
    ( (acc, x) => append (acc, f (x))
    , nil
    )

// left/right identities
bind (f) (unit (x)) == f (x)
bind (unit, m) == m

// associativity
bind (g) (bind (f) (m)) == bind (x => bind (g) (f (x)))

bind (x => autoCons (x, x, x)) (autoCons (1, 2, 3))
// == autoCons (1, 1, 1, 2, 2, 2, 3, 3, 3)

Applicative?

const ap = mx =>
  bind (f => map (f) (mx))

ap (autoCons (2, 3, 4)) (autoCons (x => x * x, x => x ** x))
// == autoCons (2 * 2, 3 * 3, 4 * 4, 2 ** 2, 3 ** 3, 4 ** 4)
// == autoCons (4, 9, 16, 4, 27, 256)

The point is that not one of these implementations is particularly special. The list here and the list given in my other answer can easily satisfy these interfaces because nil and cons form a reliable contract. Same with the difference list – it's just another implementation with a well-defined and reliable behavior. Each implementation has its own performance profile and will perform differently in varying situations.

As an exercise, you should try your own implementation of nil and cons Then build the other first-order and higher-order functions from there.

---

the traditional way to construct list as explained in lisp/Scheme textbook is very wrong. Nil should not be in the tail of the list, instead it should be in the head. Lisp/Scheme brought so much confusion having twisted list structure(0 =nil in the tail) to programming world.

You have no idea what you're saying

查看更多

0人赞 添加讨论(0) 举报

Answer 2

The Root of the Problem

The root of the problem underlying your series of questions is your insistence on using the L(1)(2)(3) syntax to construct a list. This syntax just doesn't make any sense, and people have told you time and again to forgo using this syntax:

1. user633183's answer to your very first question:

   Function currying and variadic arguments don't really work together. It's a restriction made obvious once you realize that the following two expressions are incompatible

   L (1)     -> [ 1 ]
   L (1) (2) -> [ 1, 2 ]
   

   Above L (1) returns a list, but in the second expression we expect L (1) to be a function that we can apply to 2. L (1) can be a list or it can be a function that produces a list; it cannot be both at the same time.

2. Bergi's comment on your second question:

   First of all, if you want to embrace functional programming, avoid variadic functions or curiously mixed return types.

3. user633183's answer to your third question:

   So speaking of types, let's examine the type of autoCons –

   autoCons (1)                  // "lambda (x,n) => isFunction (x) ...
   autoCons (1) (2)              // "lambda (x,n) => isFunction (x) ...
   autoCons (1) (2) (3)          // "lambda (x,n) => isFunction (x) ...
   autoCons (1) (2) (3) (add, 0) // 6
   

   Well autoCons always returns a lambda, but that lambda has a type that we cannot determine – sometimes it returns another lambda of its same kind, other times it returns a completely different result; in this case some number, 6

   Because of this, we cannot easily mix and combine autoCons expressions with other parts of our program. If you drop this perverse drive to create variadic curried interfaces, you can make an autoCons that is type-able

I don't see any good reason to use the L(1)(2)(3) syntax when you could simply write toList([1,2,3]):

// null :: List a
// cons :: (a, List a) -> List a
const cons = (head, tail) => ({ head, tail });

// xs :: List Number
const xs = cons(1, cons(2, cons(3, null))); // You can either construct a list manually,

// toList :: Array a -> List a
const toList = array => array.length ? cons(array[0], toList(array.slice(1))) : null;

// ys :: List Number
const ys = toList([1,2,3]); // or you can construct a list from an array.

console.log(xs);
console.log(ys);

Furthermore, if your only reason to use the L(1)(2)(3) syntax is to “efficiently” push an element to the end of the list, then you can do so with normal lists too. Just build the list backwards and use cons to put a new element at the beginning of the list.

The Algebraic Structure of Lists

You seem to have some unorthodox beliefs about the structure of lists:

1. First, you believe that the head of the list should always be nil:

   the traditional way to construct list as explained in lisp/Scheme textbook is very wrong. Nil should not be in the tail of the list, instead it should be in the head. Lisp/Scheme brought so much confusion having twisted list structure(0 =nil in the tail) to programming world.

2. Second, you believe that you should not have to provide an initial value for list folds:

   I still don't know any justification you stick to use "init" value for fold etc, Looking at some libraries, they don't use "init", and I think they are more reasonable. github.com/benji6/church/blob/master/src/lists.js To be precise, they basically use Zero=Identity for init that makes more sense.

Both of these beliefs are ill-informed. To understand why we need to look at the algebraic structure of lists:

   ┌──────────────────────────── A List of a
   │   ┌──────────────────────── is
   |   |   ┌──────────────────── either null
   |   |   |  ┌───────────────── or
   |   |   |  |   ┌───────────── cons of
   |   |   |  |   |   ┌───────── an a and
   │   |   |  |   |   |     ┌─── another List of a.
┌──┴─┐ │ ┌─┴┐ | ┌─┴┐  |  ┌──┴─┐
List a = null | cons (a, List a)

A list can either be empty or non-empty. Empty lists are represented by null. Non-empty lists are formed by putting a new element in front of another (possibly empty) list of elements by using cons. We put the new element in front of the original list instead of behind it because it's more natural:

cons(1, cons(2, cons(3, null))); // This is easier to read and write.

snoc(snoc(snoc(null, 1), 2), 3); // This is more difficult to read and write.

Note: There's nothing inherently wrong with using snoc. We could define List as List a = null | snoc (List a, a). However, it's just more natural to use cons. Now, depending upon whether we use cons or snoc to define the List data type, either putting new elements in front of a list or putting new elements behind a list becomes expensive:

       in front of     behind
     ┌─────────────┬─────────────┐
cons │ Inexpensive │  Expensive  │
     ├─────────────┼─────────────┤
snoc │  Expensive  │ Inexpensive │
     └─────────────┴─────────────┘

Note: Using Haskell syntax for the next two paragraphs.

Difference lists are used to amortize the cost of the expensive operation by delaying the concatenation of lists until required and then concatenating them in the most efficient order. For example, suppose we have the expression as ++ bs ++ cs ++ ds where we are concatenating four lists. If we're using the cons implementation of List then the most efficient order of concatenation is as ++ (bs ++ (cs ++ ds)), which is why the (++) operator in Haskell is right associative. On the other hand, if we're using the snoc implementation of List then the most efficient order of concatenation is ((as ++ bs) ++ cs) ++ ds.

When using the cons implementation of List, a difference list has the form (xs ++) where xs is a regular list. We can compose them forwards using regular function composition (i.e. (as ++) . (bs ++) . (cs ++) . (ds ++)). When using the snoc implementation of List, a difference list has the form (++ xs) where xs is a regular list. We can compose them backwards using regular function composition (i.e. (++ ds) . (++ cs) . (++ bs) . (++ as)). This is another reason why using the cons implementation of List is more preferable.

Now, let's change gears and talk about parts of a non-empty list. When it comes to lists (regardless of whether we're using the cons implementation of List or the snoc implementation of List), the terms head, tail, init and last have very specific meanings:

   head          tail
     │  ┌──────────┴─────────┐
cons(1, cons(2, cons(3, null)));
└──────┬─────┘       │
     init          last

              init         last
     ┌──────────┴─────────┐  │
snoc(snoc(snoc(null, 1), 2), 3);
                     │   └─┬─┘
                   head  tail

1. The head of a non-empty list is the first element of the list.
2. The tail of a non-empty list is everything but the first element of the list.
3. The init of a non-empty list is everything but the last element of the list.
4. The last of a non-empty list is, well, the last element of the list.

Hence, depending upon whether we use cons or snoc to define the List data type, either head and tail or init and last becomes expensive:

       head / tail   init / last
     ┌─────────────┬─────────────┐
cons │ Inexpensive │  Expensive  │
     ├─────────────┼─────────────┤
snoc │  Expensive  │ Inexpensive │
     └─────────────┴─────────────┘

Anyway, this is the reason why the statement, “Nil should not be in the tail of the list, instead it should be in the head,” makes no sense. The head of the list is the first element of the list. Nil is not the first element of the list. Therefore, it's illogical to state that nil should always be the head of the list.

---

Now, let's move onto folds. Depending upon whether we use cons or snoc to define the List data type, either foldl or foldr becomes tail recursive:

               foldl                  foldr
     ┌──────────────────────┬──────────────────────┐
cons │    Tail Recursion    │ Structural Recursion │
     ├──────────────────────┼──────────────────────┤
snoc │ Structural Recursion │    Tail Recursion    │
     └──────────────────────┴──────────────────────┘

Tail recursion is usually more efficient if the language performs tail call optimization. However, structural recursion is more natural, and in languages with lazy evaluation it becomes more efficient and it can work on infinite data structures. Speaking of infinite data structures, the cons implementation grows infinitely forwards (i.e. cons(1, cons(2, cons(3, ....)))) whereas the snoc implementation grows infinitely backwards (i.e. snoc(snoc(snoc(...., 1), 2), 3)). Yet another reason to prefer cons over snoc.

Anyway, let's try to understand why the initial value of a fold is required. Suppose we have the following list, xs = cons(1, cons(2, cons(3, null))) and we fold it using foldr:

  cons                                         func
 /    \                                       /    \
1    cons                                    1    func
    /    \      -> foldr(func, init, xs) ->      /    \
   2    cons                                    2    func
       /    \                                       /    \
      3    null                                    3    init

As you can see, when we reduce a list using foldr we're essentially replacing every cons with func and we're replacing null with init. This allows you to do things like append two lists by folding the first list, replacing cons with cons and null with the second list, ys = cons(4, cons(5, cons(6, null))):

  cons                                       cons
 /    \                                     /    \
1    cons                                  1    cons
    /    \      -> foldr(cons, ys, xs) ->      /    \
   2    cons                                  2    cons
       /    \                                     /    \
      3    null                                  3    cons
                                                     /    \
                                                    4    cons
                                                        /    \
                                                       5    cons
                                                           /    \
                                                          6    null

Now, if you don't provide an initial value then you aren't preserving the structure of the list. Hence, you won't be able to append two lists. In fact, you won't even be able to reconstruct the same list. Consider:

  cons                                    func
 /    \                                  /    \
1    cons                               1    func
    /    \      -> foldr1(func, xs) ->      /    \
   2    cons                               2    func
       /    \                                  /
      3    null                               3

Using foldr1 you can find the sum of the list without providing an initial value (i.e. foldr1(plus, xs)), but how would you reconstruct the same list without resorting to witchcraft? If you're willing to provide an initial value then you can elegantly write foldr(cons, null, xs). Otherwise, it's impossible to do so unless you break the principles of functional programming and use side effects to artificially provide an initial value from within func itself. Either way, you are going to provide an initial value whether it's by explicitly specifying an initial value or by handling the last element of the list as a special case within func.

Choose the simpler alternative. Explicitly provide an initial value. As the Zen of Python states:

Beautiful is better than ugly.
Explicit is better than implicit.
Simple is better than complex.
...
Special cases aren't special enough to break the rules.

Anyway, moving on to the final section.

The answers you were looking for (and more)

It would be improper of me to lecture you without answering any of your questions. Hence:

1. With respect to difference lists, your following statement is wrong:

   3. Identity element is identity function, and no need for external initial values provided.

   Actually, if you fold a difference list then you still need to provide an initial value. For reference, see the foldr function from the Data.DList package on Hackage.

2. With respect to Church encoded lists, you had the following question:

   1. I don't know why it must be not left but right fold?

   Because of your wonky L(1)(2)(3) syntax, you can only build the list backwards (i.e. L(1)(2)(3) = cons(3, cons(2, cons(1, null)))). Hence, if you want to fold the list “forwards” then you have to use foldr instead of foldl. Note that if we use snoc instead of cons then it's actually forwards (i.e. L(1)(2)(3) = snoc(snoc(snoc(null, 1), 2), 3)). This follows from the fact that snoc is just cons with the arguments flipped. Therefore, foldr for cons is equivalent to foldl for snoc and vice versa, which is what user633183 noticed.

   Note that my initial solution using continuations did in fact use foldl for cons, but in order to do that I had to somehow reverse the list since it was being built backwards. That's what the continuations were for, to reverse the list. It only later occurred to me that I don't need to reverse the list at all. I could simply use foldr instead of foldl.

3. With respect to your second point about Church encoded lists:

   2. Unclear for the realation to Monoids

   All lists are monoids, where the identity element is null and the binary operation is append = (xs, ys) => foldr(cons, ys, xs). Note that foldr(cons, null, xs) = xs (left identity) and foldr(cons, ys, null) = ys (right identity). Furthermore, foldr(cons, zs, foldr(cons, ys, xs)) is equivalent to foldr(cons, foldr(cons, zs, ys), xs) (associativity).

4. With respect to your third point about Church encoded lists:

   3. Especailly, Nil is not Identity element( = identity function), and the sample code need for external initial values provided.

   Yes, nil is in fact the identity element for lists. If the List data type is implemented as a difference list then nil is the identity function. Otherwise, it's something else. Nevertheless, nil is always the identity element for lists.

   We've already discussed why external initial values are necessary. If you don't provide them, then you can't do certain operations like append. You have to provide the initial value to append two lists. Either you provide the initial value explicitly or you provide the initial value artificially by handling the first element (when using foldl) or last element (when using foldr) of the list as a special case (and thereby breaking the principles of functional programming).

5. Finally, with respect to your dream interface:

   So, what I am curious is is there any formalization of Diffrence list like Church-list.

   Why would you want to do that? What do you hope to achieve? Church encoding is only interesting in theory. It's not very efficient in practice. Furthermore, difference lists are only useful when you're concatenating lists haphazardly (thereby taking advantage of the monoidal structure of difference lists to flatten them). Combining the two is a really bad idea.

Anyway, I hope you stop asking such questions and take some time to read SICP.

Answer 3

This is a sequel to https://stackoverflow.com/a/51500775/6440264

Response to @ Aadit M Shah

Now, let's move onto folds. Depending upon whether we use cons or snoc to define the List data type, either foldl or foldr becomes tail recursive:

               foldl                  foldr
     ┌──────────────────────┬──────────────────────┐
cons │    Tail Recursion    │ Structural Recursion │
     ├──────────────────────┼──────────────────────┤
snoc │ Structural Recursion │    Tail Recursion    │
     └──────────────────────┴──────────────────────┘

Tail recursion is usually more efficient if the language performs tail call optimization. However, structural recursion is more natural, and in languages with lazy evaluation it becomes more efficient and it can work on infinite data structures. Speaking of infinite data structures, the cons implementation grows infinitely forwards (i.e. cons(1, cons(2, cons(3, ....)))) whereas the snoc implementation grows infinitely backwards (i.e. snoc(snoc(snoc(...., 1), 2), 3)). Yet another reason to prefer cons over snoc.

The foldl of snoc as Structural Recursion is natural , and I would like to share the answer there. https://stackoverflow.com/a/32276670/6440264

"Natural" (or just "Structural") recursion is the best way to start teaching students about recursion. This is because it has the wonderful guarantee that Joshua Taylor points out: it's guaranteed to terminate[*]. Students have a hard enough time wrapping their heads around this kind of program that making this a "rule" can save them a huge amount of head-against-wall-banging.

When you choose to leave the realm of structural recursion, you (the programmer) have taken on an additional responsibility, which is to ensure that your program halts on all inputs; it's one more thing to think about & prove.

Yet another reason to prefer snoc over cons.

Anyway, let's try to understand why the initial value of a fold is required. Suppose we have the following list, xs = cons(1, cons(2, cons(3, null))) and we fold it using foldr:

  cons                                         func
 /    \                                       /    \
1    cons                                    1    func
    /    \      -> foldr(func, init, xs) ->      /    \
   2    cons                                    2    func
       /    \                                       /    \
      3    null                                    3    init

As you can see, when we reduce a list using foldr we're essentially replacing every cons with func and we're replacing null with init. This allows you to do things like append two lists by folding the first list, replacing cons with cons and null with the second list, ys = cons(4, cons(5, cons(6, null))):

  cons                                       cons
 /    \                                     /    \
1    cons                                  1    cons
    /    \      -> foldr(cons, ys, xs) ->      /    \
   2    cons                                  2    cons
       /    \                                     /    \
      3    null                                  3    cons
                                                     /    \
                                                    4    cons
                                                        /    \
                                                       5    cons
                                                           /    \
                                                          6    null

Now, if you don't provide an initial value then you aren't preserving the structure of the list. Hence, you won't be able to append two lists. In fact, you won't even be able to reconstruct the same list. Consider:

  cons                                    func
 /    \                                  /    \
1    cons                               1    func
    /    \      -> foldr1(func, xs) ->      /    \
   2    cons                               2    func
       /    \                                  /
      3    null                               3

Using foldr1 you can find the sum of the list without providing an initial value (i.e. foldr1(plus, xs)), but how would you reconstruct the same list without resorting to witchcraft? If you're willing to provide an initial value then you can elegantly write foldr(cons, null, xs). Otherwise, it's impossible to do so unless you break the principles of functional programming and use side effects to artificially provide an initial value from within func itself. Either way, you are going to provide an initial value whether it's by explicitly specifying an initial value or by handling the last element of the list as a special case within func.

Well, I really don't understand why you do this while I wrote a code without a initial value and disproved this series of opinion of "an initial value should be provided".

I already have shown the part of my code, but again, here's a how:

const plus = a => b => Number(a) + Number(b);

const sum = left => right => left === I
    ? right
    : plus(left(sum))(right);

log(
    list3(sum)
);

When you hard-code the "initial value", what are you really doing?

For instance, for "plus" operation, how do you chose the initial value should be 0?

Did it come from nowhere? Never, in fact 0 as the initial value is defined by the binary operator itself.

In your head, you thought, "ok 0+a = a = a + 0 , so this must be the initial value!",

or you thought, "ok 1 * a = a = a * 1, so this must be!",

or you thought, "ok, [].concat(a) = [a], so [] muse be the initial value!"

right? What are you doing? You just pick up the identity element in your head, and it's absolute nonsense to do because we use a computer and write a code!

If what you really need is identity element, code as so. At least, I did.

const sum = left => right => left === I //hit the bottom of pairs
    ? right // reflect the right value of the bottom pair.

If it is I reflect the right value of the bottom pair, because I is an identity I = a=>a, and in fact, I could rewrite the code as:

const sum = left => right => left === I
    ? (left)(right)
    : plus(left(sum))(right);

Please note since it hits the bottom pair, the loop operation:

plus(left(sum))(right) becomes (left)(right)

in this way, we don't have to waste our brain operation just to identiy the obvious initial values such as 0 or 1 or [] that are fundamentally identity values.

const list = L(3)(4)(5)

const max = (a, b) => (a > b) ? a : b;//initial value would be -Infinity
const min = (a, b) => (a < b) ? a : b;//initial value would be  Infinity

It is possible to define binary operators to identify first/last that is independent of left/right fold implementation.

const first = (a, b) => a; //initial value is 3 <= nonsense
const last = (a, b) => b; //initial value is 3 <= nonsense
// what if the list members is unknown??

Answer 4

My implementation:

Identity/Nil on the head not tails

No hard-coding initial values required.

const log = (m) => {
    console.log(m); //IO
    return m;
};

const I = x => x;
const K = x => y => x;
const V = x => y => z => z(x)(y);

const left = K;
const right = K(I);

log("left right test---------");
log(
    left("boy")("girl")
);
log(
    right("boy")("girl")
);

const pair = V;

const thePair = pair("boy")("girl");

log("pair test---------");
log(
    thePair(left)
);//boy
log(
    thePair(right)
);//girl

const list1 = pair(I)(1);// Identity/Nil on the head not tails...

const list2 = pair(list1)(2);

const list3 = pair(list2)(3);

log("list right test---------");
log(
    list3(right)
);//3

//Dive into the list and investigate the behevior
log("inspect---------");
const inspect = left => right => left === I
    ? (() => {
        log(right);
        return I;
    })()
    : (() => {
        log(right);
        return left(inspect);
    })();

list3(inspect);

log("plus---------");
const plus = a => b => Number(a) + Number(b);

const sum = left => right => left === I
    ? right
    : plus(left(sum))(right);

log(
    list3(sum)
);

log("fold---------");
const fold = f => left => right => left === I
    ? right //if root Identity, reflect the right of the pair
    : f(left(fold(f)))(right);

log(
    list3(fold(plus))
);

log("list constructor---------");
const isFunction = f => (typeof f === 'function');

const _L = x => y => z => isFunction(z)
    ? L(pair(x)(y)(z)) // not a naked return value but a list
    : _L(pair(x)(y))(z);

const L = _L(I);

log(
    L(1)(2)(3)(fold(plus))
);//fold returns a list // type match

log("inspect the result------------------------");

const plusStr = a => b => String(a) + String(b);
// binary operators define the type or 
//the category of Monoid List
const unit = (a) => [a];
const join = ([a]) => [].concat(a);
const flatUnit = a => join(unit(a));
const toArray = a => x => flatUnit(a)
    .concat(x);


L(1)(2)(3)
    (fold(plus))
    (inspect);
//6

L(1)(2)(3)
    (fold(plusStr))
    (inspect);
//"123"

L(1)(2)(3)
    (fold(toArray))
    (inspect);
//[ 1, 2, 3 ]

Based on this implementation, I would like to respond to

Church encoding of lists using right folds and difference lists

The Root of the Problem

The root of the problem underlying your series of questions is your insistence on using the L(1)(2)(3) syntax to construct a list.

As we already confirmed, there is nothing wrong with to constuct a list by only functions. Church encoding is a manner to construct everything with curried function. So this statement is invalid.

This syntax just doesn't make any sense, and people have told you time and again to forgo using this syntax:

If you insisit the reason something doesn't make any sense, is due to " people have told you time and again to forgo", I'm afrad to say you are wrong, and let's check it out what people said.

1. user633183's answer to your very first question:

Function currying and variadic arguments don't really work together. It's a restriction made obvious once you realize that the following two expressions are incompatible

L (1)     -> [ 1 ]
L (1) (2) -> [ 1, 2 ]

Above L (1) returns a list, but in the second expression we expect L (1) to be a function that we can apply to 2. L (1) can be a list or it can be a function that produces a list; it cannot be both at the same time.

The type mismatch issue is already resolved, hense, this problem does not exist any more for L.

2. Bergi's comment on your second question:

First of all, if you want to embrace functional programming, avoid variadic functions or curiously mixed return types.

Again, the type mismatch issue is already resolved, hense, this problem does not exist any more for L.

3. user633183's answer to your third question:

So speaking of types, let's examine the type of autoCons –

autoCons (1)                  // "lambda (x,n) => isFunction (x) ...
autoCons (1) (2)              // "lambda (x,n) => isFunction (x) ...
autoCons (1) (2) (3)          // "lambda (x,n) => isFunction (x) ...
autoCons (1) (2) (3) (add, 0) // 6

Well autoCons always returns a lambda, but that lambda has a type that we cannot determine – sometimes it returns another lambda of its same kind, other times it returns a completely different result; in this case some number, 6

Because of this, we cannot easily mix and combine autoCons expressions with other parts of our program. If you drop this perverse drive to create variadic curried interfaces, you can make an autoCons that is type-able

Again, the type mismatch issue is already resolved, hense, this problem does not exist any more for L, and fianlly, please note it's Not me who have implemented to make L returns a naked value, without wrapped by L.

I don't see any good reason to use the L(1)(2)(3) syntax when you could simply write toList([1,2,3]):

There is also absolutely no reason to prohibit to use L(1)(2)(3) syntax when there is another way to write. It is a problem of choice.

Furthermore, if your only reason to use the L(1)(2)(3) syntax is to “efficiently” push an element to the end of the list, then you can do so with normal lists too. Just build the list backwards and use cons to put a new element at the beginning of the list.

I must comment for the efficiency later, but so far, why on earth someone have to implement a flip list backwards when an exisiting method alreday achieves it naturally and simply?? How can you justify that to have broken the simplicity just to support to the fever use to "normal lists"?? What do you mean by "normal"?

Unfortunately, I cannnot find any of "The Root of the Problem" here.

The Algebraic Structure of Lists

You seem to have some unorthodox beliefs about the structure of lists:

1. First, you believe that the head of the list should always be nil:

the traditional way to construct list as explained in lisp/Scheme textbook is very wrong. Nil should not be in the tail of the list, instead it should be in the head. Lisp/Scheme brought so much confusion having twisted list structure(0 =nil in the tail) to programming world.

Correct. In fact, I have some more reason that I have not defined yet. I will define later.

2. Second, you believe that you should not have to provide an initial value for list folds:

I still don't know any justification you stick to use "init" value for fold etc, Looking at some libraries, they don't use "init", and I think they are more reasonable. github.com/benji6/church/blob/master/src/lists.js To be precise, they basically use Zero=Identity for init that makes more sense.

Correct.

Both of these beliefs are ill-informed. To understand why we need to look at the algebraic structure of lists:

A list can either be empty or non-empty. Empty lists are represented by null. Non-empty lists are formed by putting a new element in front of another (possibly empty) list of elements by using cons. We put the new element in front of the original list instead of behind it because it's more natural:

cons(1, cons(2, cons(3, null))); // This is easier to read and write.

snoc(snoc(snoc(null, 1), 2), 3); // This is more difficult to read and write.

Well, can I understand now you insist

1 + 2 + 3 to write down as a binary operator function in sequential operation is difficult to read and write, because it's

plus(plus(plus(0, 1), 2), 3);

and we should introduce "Nil on the each tails" because it's easier to read and write? Sereiously? I would not agree, and I wonder how other people feel.

Well, to express the following strucutre

A List of a is either null or cons of an a and another List of a.

const list1 = pair(I)(1);// Identity/Nil on the head not tails...

const list2 = pair(list1)(2);

looks more "natural" to me. In fact, this syntax of the structure directly corresponds to Append operation.

Furthermore, the fact of cons/Nils is as follows:

For a list of lists, a user/code needs to add multiple Nils and Nils insertion check logic must be implemented on every cons operation. This is really bothersome, and lose the simplicity of the code.

For "snoc", Nil/Zero/Null/0or1 whatever is an identity elemnt of the fist unit, so no Nil insertion check is not required for each operations. Again, it's as same as we don't check Nil insertion check for each time of binary operations such as + or x. We only care for the identity on the head or root.

Note: There's nothing inherently wrong with using snoc. We could define List as List a = null | snoc (List a, a). However, it's just more natural to use cons. Now, depending upon whether we use cons or snoc to define the List data type, either putting new elements in front of a list or putting new elements behind a list becomes expensive:

       in front of     behind
     ┌─────────────┬─────────────┐
cons │ Inexpensive │  Expensive  │
     ├─────────────┼─────────────┤
snoc │  Expensive  │ Inexpensive │
     └─────────────┴─────────────┘

It's rather obvious low cost for "behind", or to append has more advantage. It's rather rare we need prepend the new data to the exisiting lists.

Note: Using Haskell syntax for the next two paragraphs.

a difference list ... This is another reason why using the cons implementation of List is more preferable.

The hack requiremet such as diffrence for operational cost is a hack that "snoc" does not need. So I really don't understand your opinion of an existence of a work-around method is advantage.

Now, let's change gears and talk about parts of a non-empty list. When it comes to lists (regardless of whether we're using the cons implementation of List or the snoc implementation of List), the terms head, tail, init and last have very specific meanings:

   head          tail
     │  ┌──────────┴─────────┐
cons(1, cons(2, cons(3, null)));
└──────┬─────┘       │
     init          last

              init         last
     ┌──────────┴─────────┐  │
snoc(snoc(snoc(null, 1), 2), 3);
                     │   └─┬─┘
                   head  tail

1. The head of a non-empty list is the first element of the list.
2. The tail of a non-empty list is everything but the first element of the list.
3. The init of a non-empty list is everything but the last element of the list.
4. The last of a non-empty list is, well, the last element of the list.

Hence, depending upon whether we use cons or snoc to define the List data type, either head and tail or init and last becomes expensive:

       head / tail   init / last
     ┌─────────────┬─────────────┐
cons │ Inexpensive │  Expensive  │
     ├─────────────┼─────────────┤
snoc │  Expensive  │ Inexpensive │
     └─────────────┴─────────────┘

Thta's right, and it's common scenario a code needs a new data = "last" and accumulated data ="init", and it has been so easy to implement in my own code because "snoc"/pair provides the left("init") and right ("last") with inexpensive cost.

const plus = a => b => Number(a) + Number(b);

const sum = left => right => left === I
    ? right
    : plus(left(sum))(right);

log(
    list3(sum)
);

It's very concise and easy to implement, read/write and understand.

Of course, the simplicity comes from identical structure between the sequencial operation of Plus binary operator and pair("snoc").

//`1 + 2 + 3` 

plus(plus(plus(0, 1), 2), 3); 

snoc(snoc(snoc(ID, 1), 2), 3);

Anyway, this is the reason why the statement, “Nil should not be in the tail of the list, instead it should be in the head,” makes no sense. The head of the list is the first element of the list. Nil is not the first element of the list. Therefore, it's illogical to state that nil should always be the head of the list.

I don't feel any reason to chose more complicated strucutre, well espcially for beginners.

In fact the word cons is used everywhere and on the other hand, snoc is very rare to find.

https://en.wikipedia.org/wiki/Cons does not describe even a signle word of snoc, and of course there is no explanation. I think this is really unhealthy situation. what is going on here??

I know there is a historical context : https://en.wikipedia.org/wiki/S-expression , and alghouth it's important to repect pinoneers works, however overestimating the complexicity over the simpler structure can only be explained by authoritarianism.

I'm really sorry but I probably should point out a part of responsiblity is yours in fact, very experienced programmers and a great mentors with enthusiasm like you guys for some reason overestimate cons and underestimate snoc.

If I was a teacher to teach list to kids, which structure comes first to introduce? "Snoc". It's straigt forward and more understandable and easier to use.

Similarity to a sequential binary operation.

//`1 + 2 + 3` 

plus(plus(plus(0, 1), 2), 3); 

snoc(snoc(snoc(ID, 1), 2), 3);

Easy.

Cons? Hard with Nils.

---

I will separate the rest of respnse to another post because this gets too long.=>

https://stackoverflow.com/a/51510563/6440264