Проблемы с пониманием перечня

Я только начал изучать haskell (буквально, сегодня!), и я немного затрудняюсь понять логику понимания списков, более конкретно оператор <-. Небольшой пример в Learn You Some Haskell Находит все кортежи длиной менее 10:

ghci> let triangles = [ (a,b,c) | c <- [1..10], b <- [1..10], a <- [1..10] ]

мое первоначальное понимание заключалось в том, что все они будут увеличиваться вместе, но после просмотра вывода я действительно не понимаю метод incrementing для этих списков. Другой пример, который, кажется, меня достает:

ghci> let rightTriangles = [ (a,b,c) | c <- [1..10], b <- [1..c], a <- [1..b], a^2 + b^2 == c^2]

Я был бы очень благодарен за небольшое объяснение по этому поводу, спасибо за ваше терпение из-за моего отсутствия интеллекта haskell.

Ответ 1

Прочитайте [ как "список", | как "для", <- как "in", , как "и".

Перечисления выполняются вложенным образом. [ (a,b,c) | c <- [1..10], b <- [1..c], a <- [1..b], a^2 + b^2 == c^2] действительно

for c from 1 to 10 step 1:
   for b from 1 to c step 1:
      for a from 1 to b step 1:
          if (a^2 + b^2 == c^2):
             emit (a,b,c)

Однако в Haskell вышеупомянутое достигается следующим переводом

[1..10] >>= (\c->               -- (a function of 'c', producing ...
  [1..c]  >>= (\b->               -- (a function of 'b', producing ...
    [1..b]  >>= (\a->               -- (a function of 'a', producing ...
      if a^2+b^2==c^2 then [(a,b,c)] else []
      -- or: [(a,b,c) | a^2+b^2==c^2]
      )))

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

(xs >>= f) = concatMap f xs = concat (map f xs)

f здесь называется (через map) для каждого элемента из xs по порядку. Он должен создавать списки, чтобы их можно было комбинировать с concat. Поскольку пустые списки [] удаляются на concat (например, concat [[1], [], [3]] == [1,3]), все элементы, которые не проходят тест, исключаются из окончательного вывода.

Полный перевод см. в разделе раздел 3.11 "Пояснения к списку" отчета Haskell 98. В общем случае понимание списка может содержать шаблон, а не только имя переменной. Понимание

[e | pat <- ls, ...]

переводится как

ls >>= (\x -> case x of pat -> [e | ...] ;
                        _   -> [] )

где pat - некоторый шаблон, а x - новая переменная. Когда происходит несоответствие шаблона, создается пустой список (вместо ошибки времени выполнения) и этот элемент x of ls пропускается. Это полезно для дополнительной фильтрации на основе шаблонов, например, например. [x | Just x <- ls, even x], где все Nothing в ls игнорируются.

Ответ 2

[ (a,b,c) | c <- [1..10], b <- [1..10], a <- [1..10] ] означает, что для всех комбинаций (a, b, c), где a находится в [1..10], b находится в [1..10], c находится в [1..10]

Если вы хотите типы (1,1,1) (2,2,2), вы должны использовать zip: zip [1..10] [1..10] или для 3 списков, zip3 [1..10] [1..10] [1..10]

Ответ 3

Я думаю о синтаксисе понимания списка, так как Haskell пытается получить Notification set-builder на этом языке. Мы используем '[', а не '{' и '< -', а не '∈'. Синтаксис синтаксиса List может даже обобщать на произвольные монады.