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

Я читал о Applicative в Haskell от Hutton's Programming in Haskell. Чтобы лучше понять это, я придумал следующее определение для 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. Я предполагаю, что первое определение, вероятно, более полезно? Есть ли какие-то конкретные причины для такого выбора?


person coder_bro    schedule 05.06.2018    source источник
comment
hackage.haskell.org/package/ база-4.11.1.0/документы/   -  person leftaroundabout    schedule 05.06.2018
comment
@duplode Я думаю, что это не совсем дубликат, потому что экземпляр, о котором здесь спрашивали, на самом деле не ZipList (хотя идея, похоже, в этом).   -  person leftaroundabout    schedule 05.06.2018
comment
@leftaroundabout О, здесь тоже проявляется проблема (:[]) и repeat. Хорошо подмечено; открытие. (Для полноты предложенный вопрос был < i>Почему ZipList не является прикладным экземпляром по умолчанию для списка.)   -  person duplode    schedule 05.06.2018
comment
В List уже есть реализация для Monad, которая заставляет экземпляр Application (ap может быть записан в терминах return и >>= для любой Monad и быть идентичным <*>.   -  person mb14    schedule 05.06.2018


Ответы (2)


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

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

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

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

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

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

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

Далее следуют два исправления-кандидата.

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

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

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

person pigworker    schedule 06.06.2018
comment
Хотя каждый instance Applicative [] порождает моноид на [()], мне совсем не ясно, что всегда возможен другой путь. В частности, типы требуют, чтобы [] <*> _ = [] и _ <*> [] = [] в любом (общем) экземпляре; но есть много моноидов на числах, для которых 0 не является аннулятором. Действительно, после Product (ваш первый предложенный пример) очевидным следующим выбором будет Sum, у которого нет этого свойства. Таким образом, числа являются моноидами во многих отношениях, это не означает, что [] есть Applicative во многих отношениях (даже несмотря на то, что последнее оказывается правдой). - person Daniel Wagner; 07.06.2018
comment
С другой стороны, ваше наблюдение о том, что любой моноид положительных чисел можно превратить в моноид натуральных чисел (у которого действительно есть 0 в качестве аннулятора, хотя вы об этом не упомянули), было весьма интересным. , и дальнейшие размышления над вариантом Sum привели меня к следующему причудливому экземпляру Applicative: pure x = [x]; fs@(f:ft) <*> xs@(x:_) = map f xs ++ map ($x) ft (+ базовые случаи). Законы, кажется, выполняются (согласно QuickCheck, я слишком ленив для полного доказательства...), но я нахожу его поведение довольно странным, и вы были правы: это была забавная игра! - person Daniel Wagner; 07.06.2018
comment
@DanielWagner, который кажется похожим на аппликативный экземпляр этой монады, обсуждаемый в этой записи Reddit . - person Potato44; 14.06.2018

В основном это 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.

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

person leftaroundabout    schedule 05.06.2018
comment
Другое исправление может состоять в том, чтобы сделать app симметричным при обработке концов списка. например app [] [] = []; app [f] [x] = [f x]; app [f] xs = map f xs; app fs [x] = map ($x) fs; app (f:fs) (x:xs) = f x : app fs xs. Держите pure x = [x] как в вопросе. Похоже, это будет действительно другой Applicative, отличный от стандартного экземпляра или ZipList, будет нормально работать для конечных списков, и моя интуиция подсказывает, что это не должно нарушать ни один из законов (хотя я правда не проверял). - person Daniel Wagner; 05.06.2018
comment
@DanielWagner моя интуиция подсказывает, что это, вероятно, нарушит закон композиции ... кажется, что оно ведет себя непоследовательно WRT, следует ли обрезать более длинный список или расширить более короткий. Но я не уверен, что на самом деле это может быть изоморфно MaybeT (WriterT (Min Word) ZipList) или что-то в этом роде. - person leftaroundabout; 05.06.2018
comment
Он не более несовместим, чем того требует тип: пустые списки распространяются (как и должно быть в любом тотальном экземпляре), а в противном случае более короткий список всегда расширяется. - person Daniel Wagner; 05.06.2018
comment
QuickCheck говорит, что он удовлетворяет всем законам, с одной небольшой поправкой: ему нужны два базовых случая для [] _ и _ [] вместо одного базового случая [] []. Вот код. - person Daniel Wagner; 06.06.2018
comment
Экземпляр (измененный) действительно легален — (<*>) сводится к расширению более короткого списка и последующему использованию экземпляра ZipList; это не может потерпеть неудачу по отношению к ассоциативности. Это аккуратно. - person duplode; 06.06.2018
comment
Благодаря приведенным выше комментариям я смог изменить определение, чтобы выполнить расширение более короткого списка: instance Applicative' [] where pure' x = [x] app _ [] = [] app [g] [x] = [(g x)] app (g:gs) [x] = [(g x)] ++ app gs [x] app [g] (x:xs) = [(g x)] ++ app [g] xs app (g:gs) (x:xs) = [(g x)] ++ app gs xs - person coder_bro; 06.06.2018
comment
@Ngm Вам также нужен чехол app [] _ = []. В остальном выглядит хорошо для меня! - person Daniel Wagner; 06.06.2018
comment
Это не ZipList. - person pigworker; 06.06.2018
comment
анти-ziplist - person coder_bro; 07.06.2018