Precisa de explicação para a sintaxe básica do block

Aug 19 2020

No ghci, escrevi:

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

Resultado esperado:

[1,2,3,4,5]

Resultado atual:

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

Não entendo a lógica por trás dessa saída. Acho que o motivo pode ser algo sobre mônada, mas sou muito novo na programação funcional, gostaria que alguém pudesse me explicar um pouco.

Também tentei a forma equavalente na compreensão de lista e o resultado é o mesmo, o que significa que há algo básico que não entendi aqui.

Respostas

5 leftaroundabout Aug 19 2020 at 13:08

Eu também tentei a forma equavalente em compreensão de lista e o resultado é o mesmo

Boa ideia. Acontece que, para listas, a donotação faz exatamente o mesmo que as compreensões de lista. (Na verdade, há uma extensão sintática que permite usar a notação de compreensão de lista para qualquer mônada, da mesma forma que você pode usar a donotação para qualquer mônada.)

Então, você está perguntando por que [a | a<-[0,1], b<-[2,3]]dá em [0,0,1,1]vez de [0,1]. A forma como isso parece surpreendente é se você pensar em compreensões de lista como compreensões de conjunto, como você encontraria em matemática. Mas as listas não são conjuntos, embora os Haskellers freqüentemente usem listas como um substituto improvisado para conjuntos. Se as compreensões de listas atuaram como compreensão de conjunto, então

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

também deve produzir apenas [0,1]como seu resultado (ou, pelo menos, deve produzir o mesmo resultado [x|x<-[0,1]]que).

Em geral, esse tipo de eliminação de duplicatas requer verificações de igualdade e, se você quiser torná-lo eficiente, também um método de ordenação ou hash. Listas não fazem nada disso, então se você deseja um comportamento semelhante ao de conjunto, deve usar uma estrutura de dados de implementação de conjunto. Sete HashSetsão os mais comuns.

6 jpmarinier Aug 19 2020 at 12:54

Isso ocorre porque o mecanismo do não se importa (felizmente) se o código mais interno se refere ou não a (algumas das) variáveis ​​de loop.

Veja que você sempre obtém 3 * 5 = 15 valores, independentemente do código mais interno:

 λ> 
 λ> 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
 λ> 

Pelo que eu posso dizer, este é um comportamento perfeitamente padrão, que Haskell compartilha com C, C ++, Fortran, Python ...

Um exemplo equivalente em 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;
}

Saída C ++:

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