Какой идиоматический способ написания этой функции (которая обычно может называться filterA)? - PullRequest
Новая
       25

Какой идиоматический способ написания этой функции (которая обычно может называться filterA)?

2 голосов
/ 02 июня 2019

Я прохожу этот курс.

Есть раздел для Applicative, и меня просят реализовать функцию со следующим поведением и набрать 

-- | Filter a list with a predicate that produces an effect.
--
-- >>> filtering (ExactlyOne . even) (4 :. 5 :. 6 :. Nil)
-- ExactlyOne [4,6]
--
-- >>> filtering (\a -> if a > 13 then Empty else Full (a <= 7)) (4 :. 5 :. 6 :. Nil)
-- Full [4,5,6]
--
-- >>> filtering (\a -> if a > 13 then Empty else Full (a <= 7)) (4 :. 5 :. 6 :. 7 :. 8 :. 9 :. Nil)
-- Full [4,5,6,7]
--
-- >>> filtering (\a -> if a > 13 then Empty else Full (a <= 7)) (4 :. 5 :. 6 :. 13 :. 14 :. Nil)
-- Empty
--
-- >>> filtering (>) (4 :. 5 :. 6 :. 7 :. 8 :. 9 :. 10 :. 11 :. 12 :. Nil) 8
-- [9,10,11,12]
--
-- >>> filtering (const $ True :. True :.  Nil) (1 :. 2 :. 3 :. Nil)
-- [[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3]]
filtering :: Applicative f => (a -> f Bool) -> List a -> f (List a)

Я предложил следующую реализацию, которая удовлетворяет всем требованиям 

filtering f as =
  let x = sequence (f `map` as)
      y = zip as <$> x
      z = filter snd <$> y
   in map fst <$> z

но мне это кажется немного "круглым", и я не могу придумать более прямой способ сделать это.

Примечание: я расширился до x, y, z, потому что это облегчает (для меня) следить за тем, что происходит, и хотя я понимаю, что могу выразить все это в одной строке, я не считаю, что это больше » прямой и, следовательно, не ответ на мой вопрос.

Примечание 2: Этот курс, кажется, строит классы общего типа из фундаментальных частей. Мы начали с пользовательской реализации List, за которой следовал Functor, а теперь Applicative, поэтому я могу использовать только концепции из этих классов. Я пока не могу использовать что-либо от Monad.

Ответы [ 2 ]

4 голосов
/ 02 июня 2019

Моей первой идеей было бы начать с простого filter: 

filter :: (a -> Bool) -> List a -> List a
filter _ Nil = Nil
filter f (x :. xs) =
    let b = f x
        ys = filter f xs
    in
    if b then x :. ys else ys

... и попробуйте расширить его до Applicative: 

filtering :: (Applicative f) => (a -> f Bool) -> List a -> f (List a)
filtering _ Nil = pure Nil
filtering f (x :. xs) =
    let b = f x
        ys = filtering f xs
    in
    if b then x :. ys else ys

У этой попытки есть две проблемы: f x - это f Bool, а не Bool, поэтому if b then ... - это ошибка типа, а filtering f xs - это f (List a), а не List a , поэтому x :. ys является ошибкой типа.

Мы можем исправить эти проблемы, используя lift2 :: (Applicative f) => (a -> b -> c) -> f a -> f b -> f c: 

filtering f (x :. xs) =
    lift2 (\b ys -> if b then x :. ys else ys) (f x) (filtering f xs)

lift2 позволяет нам локально извлечь Bool и List a из f x и filtering f xs соответственно; или, точнее, мы завернули наши if ... then ... else вычисления в функцию, которая lift2 затем помещает в f.

В качестве альтернативы мы можем использовать <$> и <*> напрямую: 

filtering f (x :. xs) =
    (\b ys -> if b then x :. ys else ys) <$> f x <*> filtering f xs

Или напишите нашу вспомогательную функцию немного по-другому: 

filtering f (x :. xs) =
    (\b -> if b then (x :.) else id) <$> f x <*> filtering f xs
2 голосов
/ 02 июня 2019

Вот реализация в терминах foldr (и написана с использованием base типов и функций).Я вполне уверен, что это эквивалентно решению мельпомены . 

import Control.Applicative (liftA2)
import Data.Bool (bool)

filterA :: Applicative f => (a -> f Bool) -> [a] -> f [a]
filterA f = foldr (\x xs -> liftA2 (++) (bool [] [x] <$> f x) xs) (pure [])

Несколько деталей, на которые стоит обратить внимание:

  • bool y x b - это pointfreeдружественный сленг для if b then x else y.

  • Использование (++) вместо (:) для добавления элементов - это нормально, поскольку мы делаем это в начале списка.

  • xs буквально не список - он имеет тип f [a].

Демонстрация: 

GHCi> filterA (\x -> print x *> pure (x > 5)) [1..10]
1
2
3
4
5
6
7
8
9
10
[6,7,8,9,10]

Вот другой вариант, вдохновленный вашим оригинальным решением (обратите внимание, что sequence (map f xs) совпадает с traverse f xs): 

filterA :: Applicative f => (a -> f Bool) -> [a] -> f [a]
filterA f = fmap concat . traverse (\x -> bool [] [x] <$> f x)

(bool Nothing (Just x) и catMaybes от * 1042)* вместо bool [] [x] и concat также будет работать.)

Обратите внимание, что для этого решения требуется дополнительный проход по списку (-ам), поскольку traverse недостаточно для реализации фильтрации.Вот почему filter, catMaybes, filterA и друзья требуют различных классов , если они должны быть обобщены.

...