如何缓解无类型语言缺乏 return 类型多态性的问题？

Question

我最近一直在使用 Church 编码，当我看到一个典型的类型时

newtype ChurchMaybe a = 
 ChurchMaybe { runChurchMaybe :: forall r . r -> (a -> r) -> r }

看起来具有存在类型 (runChurchMaybe) 的函数的行为可能类似于 return 类型的多态函数。不过，我还没有完全理解存在类型背后的逻辑。所以我可能错了。

现在我经常读到 monad 在像 Javascript 这样的无类型语言中不太有用，也是因为缺少 return 类型多态性。所以我想知道我是否可以缓解这个缺点：

// JS version of Haskell's read

// read :: String -> forall r . (String -> r) -> r
const read = x => cons => cons(x);

// option type

const Some = x => r => f => f(x);
const None =      r => f => r;

console.log(
  read(prompt("any string")) (Array.of) // [a]
);

console.log(
  read(prompt("any string")) (Some) // Some(a)
);

console.log(
  read(prompt("number string")) (x => Number(x)) // Number
);

const append_ = x => y => append => append(x) (y);

const all = x => y => x && y;
const any = x => y => x || y;
const add = x => y => x + y;

const semigroup = append_(true) (false)

semigroup(all); // false
semigroup(any); // true
semigroup(add); // 1

显然，read 在其 return 类型中不是多态的，因为它总是 return 是一个 lambda。但是，此 lambda 可以作为实际 return 值的代理，上下文现在可以通过传递合适的构造函数来确定此代理实际生成的类型。

虽然 read 可以生成任何类型，但 append_ 仅限于具有半群约束的类型。

当然现在在这些函数的上下文中有一点噪音，因为它们 return 是代理而不是实际结果。

这就是术语 "return type polymorphism" 背后的基本机制吗？这个主题似乎很复杂，所以我想我遗漏了一些东西。感谢任何帮助。

Answer 1

如果我对你的问题的理解正确，你想知道如何实现需要访问某个类型的方法的函数 class 以便它们可以是多态的。

考虑类型 classes 的一种方法是作为类型和实现之间的查找表。例如，Show 将是类型到 return 字符串的函数的映射。 This article 对此进行了更详细的解释，并提供了一些替代方法来实现类型 classes。

在一种根本不支持类型的语言中，您必须将类型实现为某种可以传递给多态函数的唯一值，例如字符串、符号或对象引用。我更喜欢对象引用，因为它意味着我可以将我的类型实现为函数并获得实现参数化类型的能力。

这是一个示例，说明如何为 Maybe 和 Int 实施 Read：

// MACROS
const TYPE = (constructor, ...args) => Object.freeze({ constructor, args });
const TYPECLASS = (name, defaultMethods = {}) => {
  const id = Symbol(name);
  const typeClass = ({ constructor, args }) => {
    return Object.assign({}, defaultMethods, constructor[id](...args));
  };
  typeClass._instance_ = (constructor, implementation) => {
    constructor[id] = implementation;
  };
  return Object.freeze(typeClass);
};

// TYPES
const Int   = () => TYPE(Int);
const Maybe = a => TYPE(Maybe, a);

// DATA CONSTRUCTORS
const Just    = x => r => f => f(x);
const Nothing =      r => f => r;

// TYPE CLASSES and INSTANCES
const Read = TYPECLASS('Read');

Read._instance_(Maybe, A => ({
  read: str =>
    str.slice(0, 5) === "Just "
      ? Just (Read(A).read(str.slice(5)))
      : str === "Nothing"
        ? Nothing
        : undefined
}));

Read._instance_(Int, () => ({
  read: str => {
    const num = parseInt(str);
    return isNaN(num) ? undefined : num;
  }
}));

// FUNCTIONS
const error = msg => { throw new Error(msg); };
const maybe = x => f => m => m(x)(f);
const isJust = maybe (false) (_ => true);
const fromJust = maybe (undefined) (x => x);
const read = A => str => {
  const x = Read(A).read(str);
  return x === undefined ? error ("read: no parse") : x;
};
const readMaybe = A => str => {
  try       { return Just (read (A) (str)); }
  catch (e) { return Nothing; }
};

// TESTS
console.log([
  fromJust (read (Maybe(Int())) ("Just 123")), // 123
  read (Int()) ("123"),                        // 123  
  fromJust (readMaybe (Int()) ("abc"))         // undefined
]);

Answer 2

在中，我做了一个断言，但没有为自己辩护：我说过 return 类型多态性在非类型化语言中不是一个有意义的概念。那对我很粗鲁，我为如此粗鲁而道歉。我的意思比我说的要微妙得多，所以请允许我通过更详细地解释我想要表达的意思来弥补我的沟通不畅。（我希望这个答案不会让人觉得居高临下；我不知道你的基本知识水平，所以我将从头开始。）

当 Haskell 人说 "return type polymorphism" 时，他们指的是 class 调度机制类型的一种特定效果。它是 字典传递 和 双向类型推断 之间的相互作用。（我将忽略像 undefined :: forall a. a 或 let x = x in x :: forall a. a 这样的多态 _|_。它们并不算数。）

首先，请注意 Haskell 中的类型 class 实例是显式字典传递的语法糖。当 GHC 将您的程序翻译成它的核心中间表示时，所有类型 classes 都消失了。它们被替换为 "dictionary" 记录并作为常规显式参数传递； => 在运行时表示为 ->。所以代码像

class Eq a where
    (==) :: a -> a -> Bool
instance Eq Bool where
    True == True = True
    False == False = True
    _ == _ = False

headEq :: Eq a => a -> [a] -> Bool
headEq _ [] = False
headEq x (y:_) = x == y

main = print $ headEq True [False]

被翻译成

-- The class declaration is translated into a regular record type. (D for Dictionary)
data EqD a = EqD { eq :: a -> a -> Bool }
-- The instance is translated into a top-level value of that type
eqDBool :: EqD Bool
eqDBool = EqD { eq = eq }
    where eq True True = True
          eq False False = True
          eq _ _ = False

-- the Eq constraint is translated into a regular dictionary argument
headEq :: EqD a -> a -> [a] -> Bool
headEq _ _ [] = False
headEq eqD x (y:_) = eq eqD x y

-- the elaborator sees you're calling headEq with a ~ Bool and passes in Bool's instance dictionary
main = print $ headEq eqDBool True [False]

之所以有效，是因为 实例一致性：每个约束最多有一个 "best" 匹配 instance（除非你打开 IncoherentInstances，这通常是个坏主意）。在重载函数的调用点，细化器查看约束的类型参数，搜索与该约束匹配的实例 - 顶级 instance 或范围内的约束 - 并传入单个相应的字典作为论据。（有关实例一致性概念的更多信息，我推荐 Ed Kmett 的 this talk。它相当先进——我花了好几次时间才理解他的观点——但它充满了洞察力。）

很多时候，如在 headEq 中，约束的类型参数可以通过仅查看重载函数参数的类型来确定，但在多态 return 值的情况下（例如 read :: Read a => String -> a 或 mempty :: Monoid m => m) 键入信息必须来自调用站点的上下文。这是通过双向类型推断的常用机制工作的：GHC 查看 return 值的用法，生成并解决统一约束以找出其类型，然后使用该类型来搜索实例。它带来了一种神奇的开发人员体验：您编写 mempty，机器会从上下文中找出您所指的 mempty！

（顺便说一句，这就是为什么 show . read :: String -> String 被禁止的原因。 show 和 read 是类型 class 的方法，如果没有任何关于它们被使用的类型。show . read 中的中间类型——你正在读入然后显示的那个——是不明确的，所以 GHC 不知道如何选择一个实例字典来生成运行时代码。）

所以 "return type polymorphism" 实际上是一个有点误导的术语。它实际上是一种特定类型的 类型导向代码生成 的代名词；它的核心表示就像一个常规函数，其 return 类型可以根据其（字典）参数的类型确定。在没有类型 classes 的语言（或根本没有类型的语言，如 JS）中，你必须使用程序员手动传递的显式字典参数来模拟类型 classes，如@ 4Castle 已在中展示。没有类型的指导，你不能进行类型指导的代码生成！

如何缓解无类型语言缺乏 return 类型多态性的问题？

How can the lack of return type polymorphism in untyped languages be alleviated?

javascript

haskell

functional-programming

polymorphism

existential-type