如何使用函数编码实现Haskell的newtype？

Question

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

我将通过实现差异列表来演示问题。这是 Scott 编码的 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));

好吧，这行得通，但是像幺半群实例这样简单的事情的实现却相当复杂。必须 模式匹配 （cons(...) 和 cons_(...) 行 B）以获得部分应用的 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);

如何使用函数编码实现Haskell的newtype？

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

javascript

haskell

functional-programming

newtype

scott-encoding