[SOLVED] How to implement Haskell's newtype using a function encoding?

How to implement Haskell's newtype using a function encoding?

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.

Solution

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);