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

Question

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.

Oh, wow - they are too!! sorry about that - I've been drinking :p — Jaromanda X
In DList.append, you're pattern-matching on the DList constructor, which is the same as in Haskell if you view newtypes as just data types with one constructor. cons and cons_ are ill-named there; they correspond to f in DList.Cons. However, the main purpose of newtypes in Haskell is to enforce an abstraction statically without runtime cost, which just doesn't make sense in a dynamically typed language. — Li-yao Xia
Why CPS your DList? Why not just directly use DList a = List a -> List a, analogously to what is done in Haskell? The monoid instance is much easier in that case -- mappend = (.). — Daniel Wagner
@IvenMarquardt I'm not proposing any ADT implementation, as far as I can tell. Just literally use the type List a -> List a -- you already have implemented List, and I assume -> is available, no? — Daniel Wagner

Aadit M Shah Aadit M Shah · Accepted Answer · 2021-06-26T07:32:18

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

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

1 Answers