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

Ответ 1

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

Вывод do-block:

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 генерируют свои результаты лениво, по требованию, а не нетерпеливо и сразу.

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

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 enated. Функция отображения - это остаток блока do, поэтому первое связывание эффективно создает вокруг него внешний цикл.

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

Ответ 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

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

Если вы хотите, чтобы десурагирование с do обозначение на реальные операторы привязки >>=, оно выглядит так:

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

Обратите внимание, как "тело внутреннего контура"

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

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

Технический mumbo-jumbo: причина, по которой вы получаете петли foreach из привязанных стрелок, связана с конкретной монадой, с которой вы работаете. Стрелки означают разные вещи для разных монад, и чтобы знать, что они означают для определенной монады, вам нужно немного поработать и понять, как эта монада работает вообще.

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

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

λ> [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 для монады списка. (Это похоже на то, что вы работаете с одиночными значениями, когда на самом деле вы просто генерируете все возможные комбинации!)

Ответ 3

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

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

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

Ответ 4

после совета nponeccop,

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" здесь. В вложенной моде, то есть.