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

12

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

    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есть (==0)& xsесть[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]

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

Шриман Гаутам
источник
7
Я просто хотел бы сказать, что чтение этого вопроса было редким удовольствием. Мы получаем "как, черт возьми, этот код работает?" Часто задаваемые вопросы, но редко с этим уровнем объяснения того, что спрашивающий делает и не понимает. Это делает действительно интересным написать хороший адресный ответ именно о тех пробелах, которые у вас есть.
Даниэль Вагнер
Спасибо, Даниэль! Я потратил много времени на эту проблему, и поэтому я мог точно определить, в чем мне нужна помощь.
Шриман Гаутам
Я хотел бы добавить, что ответ @WillNess также работает. Это намного проще для глаз и легко понять.
Шриман Гаутам

Ответы:

2

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

(во-первых, состав функции :

   (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]        ->        [(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]

так что в целом

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

Вы спросили, как эти части сочетаются друг с другом?

Это как.


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

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]есть [].

Уилл Несс
источник
8

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

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

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

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

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

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

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

Виллем Ван Онсем
источник
1
Эй, Виллем, какое замечательное объяснение! Теперь я понял полный код. Спасибо, сэр!
Шриман Гаутам