Почему экземпляр Applicative не выполняет одноразовое приложение?

Question

Я читал о Applicative в Хаскеле из книги Хаттона по программированию в Хаскеле.Чтобы лучше это понять, я придумал следующее определение для Applicative для списков:

-- Named as pure' and "app" to avoid confusion with builtin versions 
class Applicative' f where
 pure' :: a -> f a
 app :: f (a->b) -> f a -> f b

instance Applicative' [] where
 pure' x = [x]
 app _ [] = []
 app [g] (x:xs) = [(g x)] ++ app [g] xs
 app (g:gs) (x:xs) = [(g x)] ++ app gs xs

-- fmap functions could be defined as:
fmap1' :: (Applicative' f)=>(a->b) -> f a -> f b
fmap1' g x = app (pure' g) x

fmap2' :: (Applicative' f)=>(a->b->c) -> f a -> f b -> f c
fmap2' g x y = app (app (pure' g) x) y


fmap3' :: (Applicative' f)=>(a->b->c->d) -> f a -> f b -> f c -> f d
fmap3' g x y z = app (app (app (pure' g) x) y) z

Пример использования fmap2' следующий:

Ok, one module loaded.
*Main> g = \x y -> x*y
*Main> arr1 = [1,2,3]
*Main> arr2 = [4,5,6]
*Main> fmap2' g arr1 arr2
[4,10,18]
*Main>

НоСтандартное определение для Applicative Функция <*> для списка определяется как:

gs <*> xs = [g x | g <- gs, x <- xs]

Таким образом, в результате

pure (*) <*> [1,2], [3,4]
[3,4,6,8]

Мне было интересно, почему он определен в виде for all arr1, for all arr2, apply function вместо take corresponding elements arr1, arr2 apply function.Я думаю, что первое определение, вероятно, более полезно?Есть ли конкретные причины для этого выбора?

Answer 1

Основная причина, по которой Applicative [] имеет поведение генерации всех возможных комбинаций, а не какое-либо поведение zippy, заключается в том, что Applicative является суперклассом Monad и предназначен для поведения в соответствии сMonad экземпляр, когда он существует.Monad [] обрабатывает списки как неудачный и приоритетный выбор, как и экземпляр Applicative [].Люди часто проводят рефакторинг монадического кода, используя аппликативный интерфейс, чтобы уменьшить количество промежуточных имен, необходимых для значений, и увеличить возможности параллелизма.Было бы довольно страшно, если бы это вызвало значительный сдвиг в функциональной семантике.

Кроме того, правда в том, что вы избалованы выбором для Applicative [] экземпляров, и даже более того, если вы считаете пустым /непустые и конечные / коиндуктивные / бесконечные вариации.Почему это так?

Ну, как я уже говорил в в этом ответе , каждый Applicative f начинает свою жизнь как Monoid (f ()), объединяя формы данныхпрежде чем мы начнем беспокоиться о значениях .Списки являются показательным примером.

[()] в основном тип чисел.Числа во многих отношениях являются моноидами.

Взятие Applicative [] из Monad [] равносильно выбору моноида, генерируемого 1 и *.

Между тем, Applicative ZipList эксплуатирует Haskell'sкоиндуктивное слияние и сводится к выбору моноида, порожденного бесконечностью и минимумом.

Вопрос предлагает случай, который не является законным, но близок к тому, который есть.Вы заметите, что <*> не определено для пустого списка функций, но для непустых списков функций, оно дополняет список аргументов.Асимметрично он усекается, когда заканчиваются аргументы.Что-то не совсем правильно.

Далее следуют два возможных варианта исправления.

Один из них - обрезать пустое с обеих сторон, а затем вы должны взять pure = repeat и у вас будет ZipList.

Другое - исключить пустые списки и блокнот с обеих сторон.Затем вы получаете Applicative, сгенерированное из Monoid на положительных чисел, сгенерированных 1 и максимумом .Так что это не ZipList вообще.Это то, что я назвал PadMe в этом ответе .Причина, по которой вам нужно исключить 0, заключается в том, что для каждой позиции в выходных данных <*> вам нужно указывать на позицию в обоих входах, откуда берутся функция и ее аргументы (соответственно).Вы не можете набивать, если вам нечего набивать.

Это забавная игра.Выберите Monoid для чисел и посмотрите, сможете ли вы превратить его в Applicative для списков!

Answer 2

В основном это аппликативный экземпляр ZipList.Основное отличие -

pure x = repeat x

вместо вашего pure x = [x].

Это необходимо для соблюдения применимых законов.А именно, ваша реализация нарушает закон обмена:

[id, id] <*> pure 1 ≡ [id,id] <*> [1]
                    ≡ [id 1] ++ ([id] <*> [])
                    ≡ [id 1] ++ []
                    ≡ [1]
‡ pure ($ 1) <*> [id,id] ≡ [1,1]

Требование бесконечного pure делает ZipList несколько забавным на практике.Стандартная реализация в основном является самой естественной конечной только реализацией.Возможно, было бы лучше, если бы в прелюдии были отдельные типы для конечных массивов и, возможно, бесконечных списков, и если у списков был экземпляр ZipList.

Судя по комментариям, ваша реализация на самом деле тоже хорошахотя, если только вы дополняете оба списка, если это необходимо.Ницца!