В Haskell, какова внутренняя работа понимания списка?

Question

Я довольно новичок в Haskell и смотрел этот пост здесь: Cartesian product of 2 lists in Haskell.

В ответ есть этот фрагмент кода:

cartProd xs ys = [(x,y) | x <- xs, y <- ys] 

Что с этими двумя списками:

xs = [1,2,3] 
ys = [4,5,6] 

даст

[(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)] 

Если бы я не видел этого результата I предположил бы, что он только что вернул

[(1,4),(2,5),(3,6)] 

потому что он будет проходить оба списка одновременно.

Но теперь - к языкам программирования, я лучше знаю, - выглядит как двойной цикл используется для обхода матрицы:

for (int x = 1; x < 4; x++) 
    for(int y = 4; y < 7; y++) 
     //make tuple (x,y) 

Что вызывает список понимание, чтобы вести себя таким образом?

Answer 1

Этот introduction объясняет синтаксис из списка. В принципе можно сказать, что каждый x <- list означает дополнительный вложенный «for» -loop для генерации кортежей, и каждый предикат просто протестирован. Таким образом, выражение:

[(x,y) | x <- xs, even x, y <- ys, even 3*y-div x 2] 

бы быть переведено на императивном языке, как:

for (var x : xs) { 
    if(even(x)) { 
    for(var y : ys) { 
     if(even(3*y-x/2)) { 
      yield (x,y) 
     } 
    } 
} 

yield это ключевое слово, которое иногда используются с сопрограммами. Кроме того, что касается yield, оценка выполняется лениво. Это позволяет, например, генерировать всех даже целые, как:

[x|x <-[2..],even x] 

Список монады

Чтобы понять список понимания принципиально, нужно знать, что Monads есть. Каждое понимание списка может быть переведено в список monad. Например ваш пример переводится на:

do x <- xs 
    return 
     (do y <- ys 
      return (x,y)) 

который снова синтаксический сахар для:

xs >>= (\x -> (ys >>= \y -> return (x,y))) 

монады важное понятие в функциональном программировании (и, вероятно, один лучше читает страницу википедии), потому что это немного сложно освоить. Иногда говорят, что монады похожи на burritos, ....

Как только вы более или менее понимаете монаду: монада - это тип-класс с оператором return и оператором кантации >>.Теперь return заявления для внутренней части легко:

return x = [x] 

Так что означает, что каждый раз, когда x и y установлены, вы будете создавать кортеж (x,y) и вернуть его в качестве одноэлементного списка: таким образом [(x,y)]. Теперь оператору «связывать» >>= необходимо «приклеить» ys и \y -> return (x,y) вместе. Это делается путем его реализации, как:

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

Другими словами, вы делаете отображение и сцепить результат отображения.

Теперь, если взять вторую часть unsugared выражения во внимание:

ys >>= \y -> return (x,y) 

Это означает, что для данного x (мы теперь абстрагировать), мы будем карта каждого элемента в ys к кортежу (x,y) и верни это. Таким образом, мы сгенерируем список списков, каждый из которых будет синглетом, содержащим кортеж. Нечто подобное (если ys=[1,2]):

[[(x,1)],[(x,2)]] 

Теперь >>= будет более того concat его в:

\x -> [(x,1),(x,2)] 

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

xs >>= \x -> [(x,1),(x,2)] 

Если xs=[3,5], это означает, что мы создадим снова списки:

[[(3,1),(3,2)],[(5,1),(5,2)]] 

и после CONCAT:

[(3,1),(3,2),(5,1),(5,2)] 

Какие что мы ожидаем от:

[(x,y)|x<-[3,5],y<-[1,2]] 

Answer 2

Цитирование из отчета Haskell, списочные оцениваются следующим образом:

[ e | True ] = [e] 
[ e | q ]  = [ e | q, True ] 
[ e | b, Q ] = if b then [ e | Q ] else [] 
[ e | p <- l, Q ] = let ok p = [ e | Q ] 
         ok _ = [] 
        in concatMap ok l 
[ e | let decls, Q ] = let decls in [ e | Q ] 

В вашем случае соответствующая часть, так как шаблон p это просто переменная x:

[ e | x <- l, Q ] = concatMap (\x -> [ e | Q ]) l 

Более конкретно , осознание [(x,y) | x <- xs, y <- ys] переводится на

concatMap (\x -> [(x,y) | y <- ys]) xs 

который, по определению, из concatMap

concat (map (\x -> [(x,y) | y <- ys]) xs) 

замещающих конкретные значения Давайте для xs, ys:

concat (map (\x -> [(x,y) | y <- [4,5,6]]) [1,2,3]) 

Применение map:

concat [ [(1,y) | y <- [4,5,6]] 
     , [(2,y) | y <- [4,5,6]] 
     , [(3,y) | y <- [4,5,6]] ] 

Оценка внутренних постижений списка: (они могут быть переведены снова используя законы выше, но я сделаю это коротким)

concat [ [(1,4),(1,5),(1,6)] 
     , [(2,4),(2,5),(2,6)] 
     , [(3,4),(3,5),(3,6)] ] 

И, объединив приведенные выше списки, мы получим результат.

---

Обратите внимание, что GHC также реализует как расширение Haskell так называемые параллельных списочных, которые делают работать, как вы ожидали:

> :set -XParallelListComp 
> [(x,y)| x<-[1,2,3] | y <-[4,5,6]] 
[(1,4),(2,5),(3,6)] 

Внутренне они используют zip (или, вернее, zipWith) функция.