Heads-up: This is a cross-language question.

I will demonstrate the problem by means of implementing a difference list. Here is the Scott encoded `List`

, which provides the basic type. I use it with a dynamic type validator, hence I need a wrapper to associate the type `List a`

with (simplified in the example below):

// (forall r. r -> (a -> List a -> r) -> r) -> List a const List = k => ({[Symbol.toStringTag]: "List", run: k}); // type wrapper + namespace // a -> List a -> List a List.Cons = x => xs => List(nil => cons => cons(x) (xs)); // List a List.Nil = List(nil => cons => nil); // List a -> List a -> List a List.append = xs => ys => function go(acc) { return acc.run(ys) (x => xs_ => List.Cons(x) (thunk(() => go(xs_)))); // A } (xs); // List a List.empty = List.Nil;

The expression `thunk(() => ...)`

in line `A`

creates an implicit thunk, i.e. (except for `===`

) you can treat it as the expression the thunk is deferring. In this case it has type `Last a`

.

This is pretty much standard in a eager language without ADT. Next I want to offer efficient `append`

and `snoc`

operations supplied by a difference list. At this point things are getting messy. In Haskell such a type is declared with a `newtype`

wrapper, but I don’t know how to implement it using Scott encoding. So I stick with the normal encoding:

// (forall r. ((List a -> List a) -> r) -> r) -> DList a const DList = k => ({[Symbol.toStringTag]: "DList", run: k}); // type wrapper + namespace // (List a -> List a) -> DList a DList.Cons = fun( f => DList(cons => cons(f)); // DList<a> => DList<a> => DList<a> DList.append = f => g => DList.Cons( xs => f.run( cons => cons(g.run( // B cons_ => cons_(xs))))); // B // DList a DList.empty = DList.Cons( xs => List.append(List.Nil) (xs));

Well, this works but the implementation of such an easy thing as the monoid instance is rather entangled. Having to *pattern match* (`cons(...)`

and `cons_(...)`

in line `B`

) to get the partially applied `List.append`

(`List a -> List a`

) is redundant. and unsecessarily complicating.

Maybe it is as simple as dropping the Scott encoding altogether, but I don’t want to lose the type abstraction from `List a -> List a`

to `DList a`

on the type level. Hopefully someone with more experience can point the right way.

Answers both using Haskell or JS are appreciated.

## Answer

We can simplify the implementation of `DList.append`

and `DList.empty`

as follows.

const comp = f => g => x => f(g(x)); const id = x => x; DList.append = xs => ys => xs.run(f => ys.run(g => DList.Cons(comp(f)(g)))); DList.empty = DList.Cons(id);

However, it would be even simpler if we didn’t use CPS at all.

// (List a -> List a) -> DList a const DList = run => ({ [Symbol.toStringTag]: "DList", run }); DList.append = xs => ys => DList(comp(xs.run)(ys.run)); DList.empty = DList(id);