Есть ли разница в выразительности отложенных типов, основанных на паре или паре?
Нет, в выраженности нет никакой разницы.Каждая функция вместе с ее аргументами (т. Е. замыкание ) эквивалентна 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 к комонаде.
Нет, они эквивалентны.И 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
Я предпочитаю 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 и замыканием.
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 возвращает монаду, либо нет.Аналогично для deferPair и комонад.Следовательно, я предположил, что вы хотели сказать, что deferThunk возвращает монаду (но не комонаду) и наоборот для deferPair.
У Thunk нет контекста, поэтомунемного странно построить комонаду, верно?
Почему вы думаете, что у толка не может быть контекста?Вы сами сказали, что «у thunk тоже могут быть свободные зависимости». Кроме того, нет ничего странного в создании экземпляра comonad для thunks.Что заставляет вас думать, что это странно?
Кроме того, вы используете экзистенциалы, чтобы избежать b на LHS.Я не полностью понимаю это, но это не соответствует моему коду, который использует простую пару.И пара дает контекст, отсюда и экземпляр 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, как следует использовать закрытие.