0

给出了两种都代表延迟计算的类型：

const deferThunk = thunk =>
  ({run: thunk});

const deferPair = (f, args) =>
  ({run: [f, args]});
  
const tap = f => x => (f(x), x);

const log = console.log;

const tx = deferThunk(
  () => tap(log) ("thunk based" + " " + "deferred computations"));

const ty = deferPair(
  ([x, y, z]) => tap(log) (x + y + z), ["pair based", " ", "deferred computations"]);

log("nothing happened yet...")

tx.run();
ty.run[0] (ty.run[1]);

一个重要的区别似乎是deferThunk倾向于单子，而deferPair倾向于comonad。我更喜欢deferPair，因为 thunk 执行在 Javascript 中很昂贵。但是，我不确定可能的缺点。

4

2 回答 2

2

thunk 或基于对的延迟类型的表现力有区别吗？

不，表现力没有区别。每个函数及其参数（即闭包）都等效于一个 thunk，每个 thunk 都等效于一个接受单元类型作为输入的闭包：

{-# LANGUAGE ExistentialQuantification #-}

import Control.Comonad

newtype Thunk a = Thunk { runThunk :: () -> a }

data Closure a = forall b. Closure (b -> a) b

runClosure :: Closure a -> a
runClosure (Closure f x) = f x

toThunk :: Closure a -> Thunk a
toThunk (Closure f x) = Thunk (\() -> f x)

toClosure :: Thunk a -> Closure a
toClosure (Thunk f) = Closure f ()

一个重要的区别似乎是deferThunk倾向于单子，而deferPair倾向于comonad。

不，它们是等价的。两者都有Thunk和的Closure实例：MonadComonad

instance Functor Thunk where
    fmap f (Thunk g) = Thunk (f . g)

instance Applicative Thunk where
    pure = Thunk . pure
    Thunk f <*> Thunk g = Thunk (f <*> g)

instance Monad Thunk where
    Thunk f >>= g = g (f ())

instance Comonad Thunk where
    extract (Thunk f) = f ()
    duplicate = pure

instance Functor Closure where
    fmap f (Closure g x) = Closure (f . g) x

instance Applicative Closure where
    pure a = Closure (pure a) ()
    Closure f x <*> Closure g y = Closure (\(x, y) -> f x (g y)) (x, y)

instance Monad Closure where
    Closure f x >>= g = Closure (runClosure . g . f) x

instance Comonad Closure where
    extract = runClosure
    duplicate = pure

我更喜欢deferPair，因为 thunk 执行在 Javascript 中很昂贵。

谁说的？我的基准测试表明 thunk 执行比闭包执行更快：

const thunk = () => 2 + 3;

const closureFunction = (x, y) => x + y;

const closureArguments = [2, 3];

const expected = 5;

const iterations = 10000000;

console.time("Thunk Execution");

for (let i = 0; i < iterations; i++) {
    const actual = thunk();
    console.assert(actual, expected);
}

console.timeEnd("Thunk Execution");

console.time("Closure Execution");

for (let i = 0; i < iterations; i++) {
    const actual = closureFunction(...closureArguments);
    console.assert(actual, expected);
}

console.timeEnd("Closure Execution");

我无法理解您对重击和关闭的区别。

thunk，在 JavaScript 这样的严格语言中，是任何类型的函数() -> a。例如，函数() => 2 + 3的类型为() -> Number。因此，这是一个重击。thunk通过推迟计算直到调用 thunk 来具体化惰性求值。

闭包是任意两个元素对，其中第一个元素是类型的函数，b -> a第二个元素是类型的值b。因此，该对具有类型(b -> a, b)。例如，该对[(x, y) => x + y, [2, 3]]的类型为((Number, Number) -> Number, (Number, Number))。因此，它是一个闭包。

thunk 也可以有自由依赖项。

我将假设您的意思是自由变量。当然，thunk 可以有自由变量。例如，() => x + 3在x = 2词汇上下文中，是一个完全有效的 thunk。同样，闭包也可以有自由变量。例如，[y => x + y, [3]]在x = 2词汇上下文中，是一个完全有效的闭包。

我也没有声称没有用于 thunk 的comonad 实例。

您说“deferThunk倾向于单子，而deferPair倾向于共子”。“倾向于”这句话毫无意义。要么deferThunk返回一个单子，要么不返回。和comonadsdeferPair也是如此。因此，我假设您的意思是deferThunk返回一个单子（但不是一个共单子），反之亦然deferPair。

Thunk 没有上下文，所以构造一个comonad 有点奇怪，对吧？

为什么你认为 thunk 不能有上下文？您自己说过“thunk 也可以有自由依赖项”。此外，不，为 thunk 构建一个comonad 实例并不奇怪。是什么让你觉得这很奇怪？

此外，您使用存在主义来避免bLHS 上的。我不完全理解这一点，但它不符合我的代码，它使用一个普通的对。一对给出上下文，因此是comonad实例。

我也用一双普通的。将 Haskell 代码翻译成 JavaScript：

// Closure :: (b -> a, b) -> Closure a
const Closure = (f, x) => [f, x]; // constructing a plain pair

// runClosure :: Closure a -> a
const runClosure = ([f, x]) => f(x); // pattern matching on a plain pair

存在量化只需要进行类型检查。考虑以下Applicative实例Closure：

instance Applicative Closure where
    pure a = Closure (pure a) ()
    Closure f x <*> Closure g y = Closure (\(x, y) -> f x (g y)) (x, y)

因为我们使用了存在量化，所以我们可以编写如下代码：

replicateThrice :: Closure (a -> [a])
replicateThrice = Closure replicate 3

laugh :: Closure String
laugh = Closure reverse "ah"

laughter :: Closure [String]
laughter = replicateThrice <*> laugh

main :: IO ()
main = print (runClosure laughter) -- ["ha", "ha", "ha"]

如果我们不使用存在量化，那么我们的代码就不会进行类型检查：

data Closure b a = Closure (b -> a) b

runClosure :: Closure b a -> a
runClosure (Closure f x) = f x -- this works

instance Functor (Closure b) where
    fmap f (Closure g x) = Closure (f . g) x -- this works too

instance Applicative (Closure b) where
    pure a = Closure (pure a) () -- but this doesn't work
    -- Expected pure :: a -> Closure b a
    -- Actual   pure :: a -> Closure () a

    pure a = Closure (pure a) undefined -- hack to make it work

    -- and this doesn't work either
    Closure f x <*> Closure g y = Closure (\(x, y) -> f x (g y)) (x, y)
    -- Expected (<*>) :: Closure b (a -> c) -> Closure b a -> Closure b c
    -- Actual   (<*>) :: Closure b (a -> c) -> Closure b a -> Closure (b, b) c

    -- hack to make it work
    Closure f x <*> Closure g y = Closure (\x -> f x (g y)) x

尽管我们可以通过某种方式让Applicative实例进行类型检查，但这并不是一个正确的实现。因此，以下程序仍然不会进行类型检查：

replicateThrice :: Closure Int (a -> [a])
replicateThrice = Closure replicate 3

laugh :: Closure String String
laugh = Closure reverse "ah"

laughter :: Closure Int [String]
laughter = replicateThrice <*> laugh -- this doesn't work
-- Expected laugh :: Closure Int String
-- Actual   laugh :: Closure String String

如您所见，我们希望(<*>)具有以下类型：

(<*>) :: Closure b (a -> c) -> Closure d a -> Closure (b, d) c

如果我们有这样的函数，那么我们可以这样写：

replicateThrice :: Closure Int (a -> [a])
replicateThrice = Closure replicate 3

laugh :: Closure String String
laugh = Closure reverse "ah"

laughter :: Closure (Int, String) [String]
laughter = replicateThrice <*> laugh

main :: IO ()
main = print (runClosure laughter) -- ["ha", "ha", "ha"]

因为我们不能这样做，所以我们使用存在量化来隐藏类型变量b。因此：

(<*>) :: Closure (a -> b) -> Closure a -> Closure b

此外，使用存在量化会强制执行给定的约束，即我们Closure f x只能使用f和x应用于f。x例如，如果没有存在量化，我们可以这样做：

replicateThrice :: Closure Int (a -> [a])
replicateThrice = Closure replicate 3

useReplicateThrice :: a -> [a]
-- we shouldn't be allowed to do this
useReplicateThrice = let (Closure f x) = replicateThrice in f 2

main :: IO ()
main = print (useReplicateThrice "ha") -- ["ha", "ha"]

但是，对于存在量化，上述程序不会进行类型检查。我们只被允许申请f，x这就是应该如何使用闭包。

于 2019-04-07T12:20:28.087 回答
0

我玩过基于对的延迟计算，我认为它们至少比它们的 thunk 对应物更灵活。这是 Haskell 的定点组合器到 Javascript 的堆栈安全端口：

// data constructor

const structure = type => cons => {
  const f = (f, args) => ({
    ["run" + type]: f,
    [Symbol.toStringTag]: type,
    [Symbol("args")]: args
  });

  return cons(f);
};

// trampoline

const tramp = f => (...args) => {
  let acc = f(...args);

  while (acc && acc.type === recur) {
    let [f, ...args_] = acc.args; // (A)
    acc = f(...args_);
  }

  return acc;
};

const recur = (...args) =>
  ({type: recur, args});

// deferred type

const Defer = structure("Defer")
  (Defer => (f, ...args) => Defer([f, args]))

// fixed-point combinators

const defFix = f => f(Defer(defFix, f));

const defFixPoly = (...fs) =>
  defFix(self => fs.map(f => f(self)));

// mutual recursive functions derived from fixed-point combinator

const [isEven, isOdd] = defFixPoly(
  f => n => n === 0
    ? true
    : recur(f.runDefer[0] (...f.runDefer[1]) [1], n - 1),
  f => n => n === 0
    ? false
    : recur(f.runDefer[0] (...f.runDefer[1]) [0], n - 1));

// run...

console.log(
  tramp(defFix(f => x =>
    x === Math.cos(x)
      ? x
      : recur(
        f.runDefer[0] (...f.runDefer[1]),
        Math.cos(x)))) (3)); // 0.7390851332151607

console.log(
  tramp(isEven) (1e6 + 1)); // false

请注意，不仅延迟类型基于成对，还包括结合蹦床（参见“A”行）。

这不是一个理想的实现，而只是一个演示，在没有尾调用/尾调用模 x 优化的情况下，我们可以在严格的语言中使用惰性求值获得多远。我很抱歉就同一主题提出了太多问题。当某人缺乏智慧时，坚韧是获得新知识的另一种策略。

于 2019-04-06T12:41:22.283 回答