Требуется объяснение базового синтаксиса блока do

Aug 19 2020

В ghci я написал:

 let x = do
    i <- [1..5]
    j <- [2..4]
    return i 

Ожидаемый результат:

[1,2,3,4,5]

Фактический результат:

[1,1,1,2,2,2,3,3,3,4,4,4,5,5,5]

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

Я также пробовал эквивалентную форму в List-computing, и результат тот же, что означает, что есть что-то основное, что я здесь неправильно понял.

Ответы

5 leftaroundabout Aug 19 2020 at 13:08

Я также пробовал эквивалентную форму в понимании списка, и результат тот же

Хорошая идея. Так получилось, что для списков doнотация делает то же самое, что и понимание списков. (На самом деле, существует синтаксическое расширение, которое позволяет вам использовать нотацию со списком для любой монады, как вы можете использовать doнотацию для любой монады.)

Итак, вы спрашиваете, почему [a | a<-[0,1], b<-[2,3]]дает [0,0,1,1]вместо [0,1]. Это выглядит удивительно, если вы думаете о списках как о наборах, которые вы можете найти в математике. Но списки не являются наборами, хотя Haskellers часто используют списки в качестве импровизированной замены для наборов. Если понимание списков действовало как понимание набора, то

  [x | x <- [0,1,0]]

также должен давать только [0,1]результат (или, по крайней мере, должен давать тот же результат, что [x|x<-[0,1]]и результат ).

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

6 jpmarinier Aug 19 2020 at 12:54

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

Смотрите, вы всегда получаете 3 * 5 = 15 значений независимо от внутреннего кода:

 λ> 
 λ> xs1 = do { i <- [1..5] ; j <- [2..4] ; return i }
 λ> xs1
[1,1,1,2,2,2,3,3,3,4,4,4,5,5,5]
 λ> 
 λ> xs2 = do { i <- [1..5] ; j <- [2..4] ; return 9 }
 λ> xs2
[9,9,9,9,9,9,9,9,9,9,9,9,9,9,9]
 λ> 
 λ> xs3 = do { i <- [1..5] ; j <- [2..4] ; return (i,j) }
 λ> xs3
[(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,2),(3,3),(3,4),(4,2),(4,3),(4,4),(5,2),(5,3),(5,4)]
 λ> 
 λ> length xs1
15
 λ> length xs2
15
 λ> length xs3
15
 λ> 

Насколько я могу судить, это совершенно стандартное поведение, которое Haskell разделяет с C, C ++, Fortran, Python ...

Пример эквивалента C ++:

#include  <vector>
#include  <iostream>

int main()
{
    std::vector<int>  vi{1,2,3,4,5};
    std::vector<int>  vj{2,3,4};

    for (int i: vi)
        for (int j: vj)
            std::cout << i << ", ";

    std::cout << std::endl;

    return EXIT_SUCCESS;
}

Вывод C ++:

$ ./a.out 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, $