Combinando fragmentos do Código Haskell para obter uma imagem maior

12

Este é o código que encontrei em algum lugar, mas quero saber como isso funciona:

    findIndices :: (a -> Bool) -> [a] -> [Int]
    findIndices _ [] = []
    findIndices pred xs = map fst (filter (pred . snd) (zip [0..] xs))

Saída: findIndices (== 0) [1,2,0,3,0]==[2,4] , onde predestá (==0)& xsé[1,2,0,3,0]

Vou mostrar um pouco do meu entendimento:

    (zip [0..] xs)

O que a linha acima faz é colocar índices para tudo na lista. Para a entrada dada acima, que seria parecido com este: [(0,1),(1,2),(2,0),(3,3),(4,0)].

    (pred . snd)

Eu descobri que isso significa algo como pred (snd (x)). Minha pergunta é: xa lista é feita a partir da ziplinha? Estou inclinado a sim, mas meu palpite é frágil.

Em seguida, é o meu entendimento de fste snd. Eu sei disso

    fst(1,2) = 1 

e

    snd(1,2) = 2

Como esses dois comandos fazem sentido no código?

Pelo que entendi, filterele retorna uma lista de itens que correspondem a uma condição. Por exemplo,

    listBiggerThen5 = filter (>5) [1,2,3,4,5,6,7,8,9,10]

daria [6,7,8,9,10]

Meu entendimento do mapa é que ele aplica uma função a todos os itens da lista. Por exemplo,

    times4 :: Int -> Int
    times4 x = x * 4
    listTimes4 = map times4 [1,2,3,4,5]

daria [4,8,12,16,20]

Como isso funciona em geral? Eu acho que tenho sido abrangente no que sei até agora, mas não consigo juntar as peças. Alguém pode me ajudar?

Shreeman Gautam
fonte
7
Gostaria apenas de dizer que ler esta pergunta foi um prazer raro. Ficamos com "como diabos esse código funciona?" perguntas com frequência, mas raramente com esse nível de explicação sobre o que o solicitante faz e ainda não entende. Isso torna realmente divertido escrever uma resposta boa e direcionada sobre exatamente as lacunas que você tem.
Daniel Wagner
Obrigado Daniel! Passei muito tempo nesse problema e é por isso que pude identificar com o que precisava de ajuda.
Shreeman Gautam
Gostaria de acrescentar que a resposta @WillNess também funciona. É muito mais fácil para os olhos e fácil de entender.
Shreeman Gautam

Respostas:

2

Em Haskell, gostamos de dizer, siga os tipos . De fato, as peças se conectam como se por fios passando do tipo para o tipo correspondente:

(primeiro, a composição da função é:

   (f >>> g) x  =  (g . f) x  =        g (f x)
   (f >>> g)    =  (g . f)    =  \x -> g (f x)

e a regra de inferência do tipo de composição de funções é:

    f        :: a -> b                   --      x  :: a
          g  ::      b -> c              --    f x  :: b
   -------------------------             -- g (f x) :: c
    f >>> g  :: a ->      c
    g  .  f  :: a ->      c

Agora, )

findIndices :: (b -> Bool) -> [b] -> [Int]
findIndices pred  = \xs -> map fst ( filter (pred . snd) ( zip [0..] xs ))
                  =        map fst . filter (pred . snd) . zip [0..]
                  =  zip [0..]  >>>  filter (snd >>> pred)  >>>  map fst
---------------------------------------------------------------------------
zip :: [a] ->          [b]        ->        [(a,  b)]
zip  [0..] ::          [b]        ->        [(Int,b)]
---------------------------------------------------------------------------
        snd           :: (a,b) -> b
                pred  ::          b -> Bool
       ------------------------------------
       (snd >>> pred) :: (a,b)      -> Bool
---------------------------------------------------------------------------
filter ::               (t          -> Bool) -> [t]   -> [t]
filter (snd >>> pred) ::                      [(a,b)] -> [(a,b)]
filter (snd >>> pred) ::                    [(Int,b)] -> [(Int,b)]
---------------------------------------------------------------------------
    fst ::                                   (a,   b) -> a
map     ::                                  (t        -> s) -> [t] -> [s]
map fst ::                                                 [(a,b)] -> [a]
map fst ::                                               [(Int,b)] -> [Int]

então, no geral,

zip  [0..] ::          [b]        ->        [(Int,b)]
filter (snd >>> pred) ::                    [(Int,b)] -> [(Int,b)]
map fst ::                                               [(Int,b)] -> [Int]
---------------------------------------------------------------------------
findIndices pred ::    [b] ->                                         [Int]

Você perguntou: como essas peças se encaixam?

É assim.


Com a compreensão de lista , sua função é escrita como

findIndices pred xs = [ i | (i,x) <- zip [0..] xs, pred x ]

que em pseudocódigo diz:

"lista de resultados contém ipara cada (i,x)em zip [0..] xstal que pred xdetém" .

Faz isso girando o nbotão -long

xs = [a,b,...,z] = [a] ++ [b] ++ ... ++ [z]

para dentro

  [0 | pred a] ++ [1 | pred b] ++ ... ++ [n-1 | pred z]

onde [a | True]está [a]e [a | False]está [].

Will Ness
fonte
8

Eu descobri que isso significa algo como pred (snd (x)). Minha pergunta é: x é a lista feita a partir da tirolesa? Estou inclinado a sim, mas meu palpite é frágil.

Bem pred . snd, significa \x -> pred (snd x). Portanto, este basicamente constrói uma função que mapeia um elemento xem pred (snd x).

Isso significa que a expressão se parece com:

filter (\x -> pred (snd x)) (zip [0..] xs)

Aqui xestá, portanto, uma 2-tupla gerada por zip. Portanto, a fim de saber se (0, 1), (1,2), (2, 0), etc. são mantidos no resultado, snd xlevará o segundo elemento destes 2-tuplas (assim 1, 2, 0, etc.), e verifique se o predon tha elemento está satisfeito ou não. Se estiver satisfeito, ele reterá o elemento, caso contrário, esse elemento (a 2-tupla) será filtrado.

Então, se (== 0)é o predicate, ele filter (pred . snd) (zip [0..] xs)conterá as 2 tuplas [(2, 0), (4, 0)].

Mas agora o resultado é uma lista de 2 tuplas. Se queremos os índices, precisamos, de alguma forma, nos livrar da tupla 2 e do segundo elemento dessas 2 tuplas. Usamos fst :: (a, b) -> apara isso: isso mapeia uma 2-tupla em seu primeiro elemento. Então, para uma lista [(2, 0), (4, 0)], map fst [(2, 0), (4, 0)]retornará [2, 4].

Willem Van Onsem
fonte
11
Hey Willem, que ótima explicação! Eu entendi o código completo agora. Obrigado senhor!
Shreeman Gautam 05/04