Значение `<-` в блоке do в Haskell

Question

Я пытаюсь понять монады Haskell, читая "Monads for the Curious Programmer". Я бежал в пример списка Монады:

tossDie=[1,2,3,4,5,6] 

toss2Dice = do 
    n <- tossDie 
    m <- tossDie 
    return (n+m) 

main = print toss2Dice 

То, как do блок производит список m, как 36-элементный я вроде понимаю - он отображает каждый элемент n в виде списка из 6 элементов, а затем присоединяет те списки. Я не понимаю, как n изменен присутствием m <- tossDie, из 6 элементов списка до 36 элементов. Очевидно, что «мы сначала связываем n, а затем связываем m», здесь неправильно, но что правильно?

Я также не совсем понимаю, как применяется функция с двумя аргументами в блоке . Я подозреваю, что это случай клятвы, но я немного туманно о том, как именно он работает.

Может кто-нибудь объяснить эти две загадки?

Answer 1

Для списков (например, как tossDie), в do обозначении действует как список понимание - то есть скажем, как будто каждое связывание переменных было вложенным циклом foreach.

Выражение сделай блок:

toss2Dice = do { n <- tossDie; m <- tossDie; return (n+m) } 

делает то же самое, как этот список понимание:

toss2Dice = [ n+m | n <- tossDie, m <- tossDie ] 

Результат сравнит со следующим императивным псевдокодом:

toss2Dice = [] 
foreach n in tossDie: 
    foreach m in tossDie: 
     toss2Dice.push_back(n+m) 

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

---

Если вы посмотрите на монады, например для списков, вы можете увидеть, как это работает:

instance Monad [] where 
    xs >>= f = concat (map f xs) 
    return x = [x] 

Начиная с началом do блока, каждое переменное связывание создает цикл в течение оставшейся части блок:

do { n <- tossDie; m <- tossDie; return (n+m) } 
===> tossDie >>= \n -> do { m <- tossDie; return (n+m) } 
===> concat (map (\n -> do { m <- tossDie; return (n+m) }) tossDie) 

Обратите внимание, что map функции перебирает элементы в списке tossDie, и разрешение ≤ concat. Функция отображения - это остаток блока do, поэтому первое связывание эффективно создает вокруг него внешний цикл.

Дополнительные привязки создают последовательно вложенные петли; и, наконец, функция return создает одиночный список из каждого вычисленного значения (n+m), так что функция «привязки» >>= (которая ожидает списки) может их конкатенировать должным образом.

Answer 2

Интересное бит я предполагаю, это:

toss2Dice = do 
    n <- tossDie 
    m <- tossDie 
    return (n+m) 

Это несколько эквивалентно следующий Python:

def toss2dice(): 
    for n in tossDie: 
     for m in tossDie: 
      yield (n+m) 

Когда дело доходит до списка монады, вы можете просмотреть обязательные стрелки (<-) в обозначении как традиционные императивные «foreach» петли. Все, после

n <- tossDie 

принадлежит к «телу цикла» этого Еогеасп цикла, и так будет оцениваться один раз для каждого значения в tossDie присвоенного n.

Если вы хотите desugaring от do записи фактических операторов связывания >>=, это выглядит следующим образом:

toss2Dice = 
    tossDie >>= (\n -> 
    tossDie >>= (\m -> 
     return (n+m) 
    ) 
) 

Обратите внимание, как «внутреннее тело цикла»

(\n -> 
    tossDie >>= (\m -> 
    return (n+m) 
) 
) 

Получит выполняется один раз для каждое значение в tossDie. Это в значительной степени эквивалентно вложенным петлям Python.

---

Технический фетиш: Причина вы получаете «Еогеасп» петли от связывания стрелок должен делать с конкретной монады вы работаете. Стрелки означают разные вещи для разных монадов, и чтобы знать, что они означают для определенной монады, вам нужно немного поработать и понять, как эта монада работает вообще.

Стрелков получают обессахаренную в вызовы оператора связывания, >>=, который работает по-разному для разных монад, а также - это причина, по которой связывает стрелки <- также работают по-разному для разных монад!

В случае монады списка оператор привязки >>= берет список влево и функцию, возвращающую список справа, и сортировка применяет эту функцию к каждому элементу списка.Если мы хотим, чтобы удвоить каждый элемент в списке в громоздкой образом, мы могли бы представить себе это делать, как

λ> [1, 2, 3, 4] >>= \n -> return (n*2) 
[2,4,6,8] 

(return требуется, чтобы типы работать. >>= ожидает функцию, которая возвращает список, и return будет, для списка монады, оберните значение в списке.) для того, чтобы проиллюстрировать, возможно, более мощный пример, мы можем начать воображать функцию

λ> let posneg n = [n, -n] 
λ> posneg 5 
[5,-5] 

Тогда мы можем написать

λ> [1, 2, 3, 4] >>= posneg 
[1,-1,2,-2,3,-3,4,-4] 

считать натуральные числа от -4 до 4.

Причины список монада работает таким образом, что это Конкретное поведение привязки оператора >>= и return делает монаду законы держать. Законы монады важны для нас (и, возможно, авантюрного компилятора), потому что они позволяют нам менять код так, как мы знаем, ничего не сломают.

Очень милый побочный эффект от этого заключается в том, что он делает списки очень удобными для представления неопределенности в значениях. Скажем, вы создаете объект OCR, который должен смотреть на изображение и превращать его в текст. Вы можете столкнуться с символом, который может быть либо 4, либо A или H, но вы не уверены. Позволив OCR thingey работать в списке монады и вернет список ['A', '4', 'H'], вы применили свои базы. Фактически работа со сканированным текстом становится очень простой и читаемой с помощью do нотации для монады списка. (Это Сорт выглядит, как вы работаете с одиночными значениями, когда на самом деле вы просто генерировать все возможные комбинации!)

Answer 3

Добавление @kqr ответа:

>>= для списка монады фактически concatMap, функция, которая отображает элементы списков элементов и присоединяет списки, но с аргументами перевернутых:

concatMap' x f = concat (map f x) 

или альтернативно

concatMap' = flip concatMap 

return просто

singleElementList x = [x] 

Теперь мы можем заменить >>= с concatMap' и singleElementList:

toss2Dice = 
    concatMap' tossDie (\n -> 
    concatMap' tossDie (\m -> 
     singleElementList (n+m) 
    ) 
) 

Теперь мы можем заменить 2 функции с их телами:

toss2Dice = 
    concat (map (\n -> 
    concat (map (\m -> 
     [n+m] 
    ) tossDice) 
) tossDice) 

Удалить дополнительные разрывы строк:

toss2Dice = concat (map (\n -> concat (map (\m -> [n+m]) tossDice)) tossDice) 

Или короче с concatMap:

toss2Dice = concatMap (\n -> concatMap (\m -> [n+m]) tossDice) tossDice 

Answer 4

ниже nponeccop's advice с

for = flip concatMap 

ваш код становится

toss2Dice = 
    for {- n in -} tossDie {- call -} 
     (\n-> for {- m in -} tossDie {- call -} 
        (\m-> [n+m])) 

где это ясно видно, что мы имеем вложенные функции, один внутри другого ; поэтому внутренняя функция (\m-> [n+m]), находящаяся в области области аргумента внешней функции n, имеет к ней доступ (к аргументу n, который есть). Таким образом, он использует значение аргумента для внешней функции, которое равно тому же при каждом вызове внутренней функции, однако много раз он вызывается во время тем же самым вызовом внешней функции.

Это может быть переписана с именованными функциями,

toss2Dice = 
    for {- each elem in -} tossDie {- call -} g 
    where g n = for {- each elem in -} tossDie {- call -} h 
       where h m = [n+m] 

Функция h определяется внутриg, то есть в области видимости g «ы аргумента. И вот как h использует как m, так и n, хотя только аргумент m.

Так что на самом деле мы действительно «сначала связываем n, а затем связываем m» здесь.В nested fashion, то есть.