0

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.

  • 1
    all code snippets are JS –  Jun 24 '21 at 14:33
  • Oh, wow - they are too!! sorry about that - I've been drinking :p – Jaromanda X Jun 24 '21 at 14:38
  • 2
    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 Jun 24 '21 at 14:53
  • Why are you even trying to use a Scott encoding here? A `newtype` has only a single constructor anyway. – Bergi Jun 24 '21 at 15:16
  • `DList.Cons` seems misnamed. Or does that stand for "Constructor" here? – Bergi Jun 24 '21 at 15:21
  • @Li-yaoXia Okay, I figured there was a distinct way how to encode `newtype` with functions, but it seems to be Scott with just a single constructor. Thank you. –  Jun 24 '21 at 16:08
  • @Bergi Up to know Scott encoded ADTs are the only means for user defined data types in a principled way provided by my type validator. Using Scott I can abstract `(List -> List a) -> List a` to just `DList a`, which is exactly what I want. There is also a `Native` type constrcutor but it is meant for imperative (non-algebraic) types, so using it for `DList` feels like misuse. –  Jun 24 '21 at 16:13
  • 2
    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 Jun 24 '21 at 16:18
  • @IvenMarquardt I don't know what your type validator does, but if you just use `(List a -> List a) -> DList a` instead of `(forall r. ((List a -> List a) -> r) -> r) -> DList a` it would simplify a lot. – Bergi Jun 24 '21 at 16:30
  • @DanielWagner Using CPS I only had to extend HM by impredicative poly for `->`. The rest including pattern matching was for free. Besides I don't think I have the skills to implement ADTs by myself yet. I'd probably just make things up/make terrible choices in implementation details. –  Jun 24 '21 at 17:02
  • 2
    @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 Jun 24 '21 at 17:10
  • I agree with @DanielWagner. Why not just define `DList :: (List a -> List a) -> DList a`? Using the CPS version `DList :: (forall r. ((List a -> List a) -> r) -> r) -> DList a` is unnecessarily complex. – Aadit M Shah Jun 26 '21 at 06:48
  • _“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.”_ What do you mean by losing the type abstraction from `List a -> List a` to `DList a` on the type level? Please clarify. – Aadit M Shah Jun 26 '21 at 06:51
  • I don't want to bug you with implementation details of my validator. My ADTs have a run method and expect a higher-kinded function argument. In order to declare single constructor ADTs w/o CPS I need a completely new logic. The new type probably don't need higher-rank but I'm not sure about this. I wanted to avoid this. Losing the abstraction was based on the initial assumption that I work with the raw type and simply use (.) for append. –  Jun 26 '21 at 07:33

1 Answers1

0

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);
Aadit M Shah
  • 72,912
  • 30
  • 168
  • 299
  • I overcomplicated things again - sort of my weak spot. It turns out that as soon as I drop the continuations I don't have to deal with higher-rank anymore, but I can still reuse most of the code responsible for multi-constructor ADT declaration. As a matter of fact entailing pattern matching is the only reason why I need to use a CPS encoding in the first place. –  Jun 26 '21 at 15:13