Combinando fragmentos de Haskell Code para obtener una imagen más grande

12

Este es el código que encontré en alguna parte, pero quiero saber cómo funciona esto:

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

Salida: findIndices (== 0) [1,2,0,3,0]==[2,4] , donde predes (==0)y xses[1,2,0,3,0]

Mostraré algo de mi comprensión:

    (zip [0..] xs)

Lo que hace la línea anterior es poner índices a todo en la lista. Para la entrada dada anteriormente, sería el siguiente: [(0,1),(1,2),(2,0),(3,3),(4,0)].

    (pred . snd)

Descubrí que esto significa algo así pred (snd (x)). Mi pregunta es, ¿ xla lista está hecha desde la ziplínea? Me estoy inclinando hacia sí, pero mi suposición es débil.

A continuación, es mi comprensión de fsty snd. Yo sé eso

    fst(1,2) = 1 

y

    snd(1,2) = 2

¿Cómo tienen sentido estos dos comandos en el código?

Entiendo filterque devuelve una lista de elementos que coinciden con una condición. Por ejemplo,

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

daría [6,7,8,9,10]

Según tengo entendido, map aplica una función a cada elemento de la lista. Por ejemplo,

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

daría [4,8,12,16,20]

¿Cómo funciona esto en general? Creo que he sido comprensivo en lo que sé hasta ahora, pero no puedo armar las piezas. ¿Alguien puede ayudarme?

Shreeman Gautam
fuente
77
Solo me gustaría decir que leer esta pregunta fue un placer raro. Obtenemos "¿cómo diablos funciona este código?" pregunta con frecuencia, pero rara vez con este nivel de explicación de lo que el autor de la pregunta hace y no entiende. Eso hace que sea realmente divertido escribir una buena respuesta específica sobre exactamente las brechas que tiene.
Daniel Wagner
Gracias Daniel! Pasé mucho tiempo en este problema y es por eso que pude identificar con qué necesitaba ayuda.
Shreeman Gautam
Me gustaría agregar que la respuesta @WillNess también funciona. Es mucho más fácil de ver y fácil de entender.
Shreeman Gautam

Respuestas:

2

En Haskell nos gusta decir, sigue los tipos . De hecho, las piezas se conectan como si fueran cables que van del tipo al tipo correspondiente:

(primero, la composición de la función es:

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

y la regla de inferencia de tipo de composición de función es:

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

Ahora, )

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]

entonces, en general,

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

Usted ha preguntado, ¿cómo encajan estas piezas?

Así es como.


Con las comprensiones de listas , su función se escribe como

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

que en pseudocódigo lee:

msgstr "la lista de resultados contiene ipara cada uno (i,x)de forma zip [0..] xsque se pred xmantenga" .

Lo hace girando el nlargo

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

dentro

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

donde [a | True]es [a]y [a | False]es [].

Will Ness
fuente
8

Descubrí que esto significa algo así pred (snd (x)). Mi pregunta es, ¿es x la lista hecha de la tirolina? Me estoy inclinando hacia sí, pero mi suposición es débil.

Bueno pred . snd, significa \x -> pred (snd x). Así que esto básicamente construye una función que mapea un elemento xde pred (snd x).

Esto significa que la expresión se ve así:

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

Aquí xhay una tupla 2 generada por zip. Así que con el fin de saber si (0, 1), (1,2), (2, 0), etc., están retenidos en el resultado, snd xse llevará el segundo elemento de estas 2-tuplas (así 1, 2, 0, etc.), y comprobar si el predTha elemento se cumple o no. Si está satisfecho, retendrá el elemento; de lo contrario, ese elemento (la tupla 2) se filtrará.

Entonces, si (== 0)es el predicate, filter (pred . snd) (zip [0..] xs)contendrá las 2 tuplas [(2, 0), (4, 0)].

Pero ahora el resultado es una lista de 2-tuplas. Si queremos los índices, de alguna manera necesitamos deshacernos de las 2 tuplas y el segundo elemento de estas 2 tuplas. Usamos fst :: (a, b) -> apara eso: esto asigna una tupla de 2 en su primer elemento. Entonces, para una lista [(2, 0), (4, 0)], map fst [(2, 0), (4, 0)]volveremos [2, 4].

Willem Van Onsem
fuente
1
Hola Willem, ¡qué gran explicación! He entendido el código completo ahora. ¡Gracias Señor!
Shreeman Gautam