Объединение фрагментов кода Haskell для получения большей картины

Question

Это код, который я где-то нашел, но хочу знать, как это работает:

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

Вывод: findIndices (== 0) [1,2,0,3,0] == [2,4], где pred is (==0) & xs is [1,2,0,3,0]

Я покажу некоторые из моих пониманий:

    (zip [0..] xs)

То, что делает строка выше, это помещает индексы для всего в списке. Для ввода, приведенного выше, это будет выглядеть так: [(0,1),(1,2),(2,0),(3,3),(4,0)].

    (pred . snd)

Я обнаружил, что это означает что-то вроде pred (snd (x)). У меня вопрос, является ли x список из строки zip? Я склоняюсь к да, но мое предположение ненадежно.

Далее, мое понимание fst и snd. Я знаю, что

    fst(1,2) = 1 

и

    snd(1,2) = 2

Как эти две команды имеют смысл в коде?

Мое понимание filter состоит в том, что он возвращает список предметов, которые соответствуют условию. Например,

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

даст [6,7,8,9,10]

Мое понимание карты состоит в том, что она применяет функцию к каждому элементу в списке. Например,

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

даст [4,8,12,16,20]

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

Answer 1

Я обнаружил, что это означает что-то вроде pred (snd (x)). У меня вопрос, является ли список x из строки zip? Я склоняюсь к да, но мое предположение неубедительно.

Ну pred . snd, значит \x -> pred (snd x). Таким образом, это в основном создает функцию, которая отображает элемент x на pred (snd x).

Таким образом, это означает, что выражение выглядит следующим образом:

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

Здесь x, таким образом, представляет собой 2 кортеж, сгенерированный zip. Итак, чтобы узнать, если (0, 1), (1,2), (2, 0), et c. сохраняются в результате, snd x возьмет второй элемент этих 2-х кортежей (т. е. 1, 2, 0, et c.) и проверит, если pred на этом элементе доволен или нет. Если он удовлетворен, он сохранит элемент, в противном случае этот элемент (2-кортеж) будет отфильтрован.

Так что, если (== 0) - это pred icate, то filter (pred . snd) (zip [0..] xs) будет содержать 2 -tuples [(2, 0), (4, 0)].

Но теперь результатом является список из 2-х кортежей. Если нам нужны индексы, нам как-то нужно избавиться от 2-кортежа и второго элемента этих 2-кортежей. Для этого мы используем fst :: (a, b) -> a: это отображает 2-кортеж на его первый элемент. Так что для списка [(2, 0), (4, 0)], map fst [(2, 0), (4, 0)] вернет [2, 4].

Answer 2

В Haskell мы хотели бы сказать, следуют за типами . Действительно, части соединяются, как если бы они проводились от типа к соответствующему типу:

(во-первых, композиция функций это:

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

и тип композиции функций Правило вывода :

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

Теперь,

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>[b]</b>        ->        <b>[(Int,b)]</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) ::                    <b>[(Int,b)]</b> -> <b>[(Int,b)]</b>
---------------------------------------------------------------------------
    fst ::                                   (a,   b) -> a
map     ::                                  (t        -> s) -> [t] -> [s]
map fst ::                                                 [(a,b)] -> [a]
map fst ::                                               <b>[(Int,b)]</b> -> <b>[Int]</b>

Итак, в целом,

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

Вы спрашивали, как эти части

Вот как.

---

При понимании списка ваша функция записывается как

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

, которая в псевдокоде читает :

"список результатов содержит i для каждого (i,x) в zip [0..] xs, так что pred x содержит" .

Это делается путем превращения n -длинной

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

в

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

, где [a | True] равно [a] и [a | False] равно [].