如何使用函数编码实现哈斯克尔的newtype？

Question

注意：这是一个跨语言的问题。

我将通过实施差异列表来证明这个问题。这里是斯科特编码的List，它提供了基本类型。我将它与动态类型验证器一起使用，因此我需要一个包装器来将类型List a与关联起来(在下面的示例中进行了简化(：

// (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;

第A行中的表达式thunk(() => ...)创建了一个隐式thunk，即(除了===(您可以将其视为thunk正在延迟的表达式。在这种情况下，它的类型为Last a。

这在没有ADT的热切语言中是相当标准的。接下来，我想提供由差异列表提供的有效的append和snoc操作。在这一点上，事情变得一团糟。在Haskell中，这样的类型是用newtype包装器声明的，但我不知道如何使用Scott编码来实现它。所以我坚持正常的编码：

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

好吧，这是可行的，但像monoid实例这样简单的事情的实现相当复杂。必须模式匹配(B行中的cons(...)和cons_(...)(以获得部分应用的List.append(List a -> List a(是多余的。并且不必要地复杂化。

也许这就像完全删除Scott编码一样简单，但我不想在类型级别上丢失从List a -> List a到DList a的类型抽象。希望有更多经验的人能指出正确的方向。

感谢使用Haskell或JS的回答。

Answer 1

我们可以简化DList.append和DList.empty的实现，如下所示。

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

然而，如果我们根本不使用CPS，它会更简单。

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