基于 thunk 或 pair 的延迟类型的表现力是否存在差异？
Is there a difference in expressiveness of thunk or pair based deferred types?
给定两种都代表延迟计算的类型：
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 倾向于 monad，而 deferPair 倾向于 comonad。我倾向于选择 deferPair，因为在 Javascript 中执行 thunk 非常昂贵。但是，我不确定可能存在的缺点。
我玩过基于对的延迟计算，我认为它们至少比它们的 thunk-counterparts 更灵活。这是 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" 行）。
这不是一个理想的实现，而只是一个演示，我们可以在没有尾部 call/tail 调用模 x 优化的严格语言中通过惰性求值达到什么程度。对于同一主题问了太多问题，我深表歉意。当一个人缺乏聪明时，坚韧是获得新知识的另一种策略。
Is there a difference in expressiveness of thunk or pair based deferred types?
不，表现力没有区别。每个函数及其参数（即 closure）等同于一个 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 ()
An important difference seems to be that deferThunk leans towards a monad, whereas deferPair towards a comonad.
不，它们是等价的。 Thunk 和 Closure 都有 Monad 和 Comonad:
的实例
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
I tend to prefer deferPair, because thunk execution is expensive in 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");
I can't follow your distinction between thunk and closure.
thunk，在像 JavaScript 这样的严格语言中，是 () -> a 类型的任何函数。例如，函数 () => 2 + 3 的类型为 () -> Number。因此，这是一个thunk。一个 thunk reifies 惰性评估，通过推迟计算直到 thunk 被调用。
闭包是任意一对两个元素，其中第一个元素是 b -> a 类型的函数，第二个元素是 b 类型的值。因此，该对的类型为 (b -> a, b)。例如，[(x, y) => x + y, [2, 3]] 对的类型为 ((Number, Number) -> Number, (Number, Number))。因此，它是一个闭包。
A thunk can have free dependencies too.
我假设您指的是自由变量。当然，thunk 可以有自由变量。例如，() => x + 3，其中词法上下文中的 x = 2 是完全有效的 thunk。同样，闭包也可以有自由变量。例如，[y => x + y, [3]]，其中词法上下文中的 x = 2 是一个完全有效的闭包。
I also didn't claim that there was no comonad instance for thunk.
你说“deferThunk 倾向于 monad，而 deferPair 倾向于 comonad。” “倾向于”这句话没有任何意义。 deferThunk returns 要么是 monad，要么不是。 deferPair 和 comonads 也是如此。因此，我假设你的意思是说 deferThunk returns 是一个 monad（但不是 comonad），反之亦然 deferPair.
Thunk doesn't have a context, so it is a bit weird to construct a comonad, right?
为什么你认为 thunk 不能有上下文？您自己说过“thunk 也可以有自由依赖项”。此外，不，为 thunk 构造一个 comonad 实例并不奇怪。是什么让你觉得它很奇怪？
Additionally, you use existentials to avoid the b on the LHS. I don't fully understand this, but it isn't compliant with my code, which uses a plain pair. And a pair gives context, hence the comonad instance.
我也用一双普通的。将 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
存在量化只需要进行类型检查。考虑 Closure 的 Applicative 实例：
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，这是应该使用闭包的方式。
给定两种都代表延迟计算的类型：
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 倾向于 monad，而 deferPair 倾向于 comonad。我倾向于选择 deferPair，因为在 Javascript 中执行 thunk 非常昂贵。但是，我不确定可能存在的缺点。
我玩过基于对的延迟计算，我认为它们至少比它们的 thunk-counterparts 更灵活。这是 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" 行）。
这不是一个理想的实现，而只是一个演示，我们可以在没有尾部 call/tail 调用模 x 优化的严格语言中通过惰性求值达到什么程度。对于同一主题问了太多问题，我深表歉意。当一个人缺乏聪明时，坚韧是获得新知识的另一种策略。
Is there a difference in expressiveness of thunk or pair based deferred types?
不，表现力没有区别。每个函数及其参数（即 closure）等同于一个 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 ()
An important difference seems to be that
deferThunkleans towards a monad, whereasdeferPairtowards a comonad.
不，它们是等价的。 Thunk 和 Closure 都有 Monad 和 Comonad:
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
I tend to prefer
deferPair, because thunk execution is expensive in 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");
I can't follow your distinction between thunk and closure.
thunk，在像 JavaScript 这样的严格语言中，是 () -> a 类型的任何函数。例如，函数 () => 2 + 3 的类型为 () -> Number。因此，这是一个thunk。一个 thunk reifies 惰性评估，通过推迟计算直到 thunk 被调用。
闭包是任意一对两个元素，其中第一个元素是 b -> a 类型的函数，第二个元素是 b 类型的值。因此，该对的类型为 (b -> a, b)。例如，[(x, y) => x + y, [2, 3]] 对的类型为 ((Number, Number) -> Number, (Number, Number))。因此，它是一个闭包。
A thunk can have free dependencies too.
我假设您指的是自由变量。当然，thunk 可以有自由变量。例如，() => x + 3，其中词法上下文中的 x = 2 是完全有效的 thunk。同样，闭包也可以有自由变量。例如，[y => x + y, [3]]，其中词法上下文中的 x = 2 是一个完全有效的闭包。
I also didn't claim that there was no comonad instance for thunk.
你说“deferThunk 倾向于 monad，而 deferPair 倾向于 comonad。” “倾向于”这句话没有任何意义。 deferThunk returns 要么是 monad，要么不是。 deferPair 和 comonads 也是如此。因此，我假设你的意思是说 deferThunk returns 是一个 monad（但不是 comonad），反之亦然 deferPair.
Thunk doesn't have a context, so it is a bit weird to construct a comonad, right?
为什么你认为 thunk 不能有上下文？您自己说过“thunk 也可以有自由依赖项”。此外，不，为 thunk 构造一个 comonad 实例并不奇怪。是什么让你觉得它很奇怪？
Additionally, you use existentials to avoid the
bon the LHS. I don't fully understand this, but it isn't compliant with my code, which uses a plain pair. And a pair gives context, hence the comonad instance.
我也用一双普通的。将 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
存在量化只需要进行类型检查。考虑 Closure 的 Applicative 实例：
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，这是应该使用闭包的方式。