Реализация `` traverse` и sequenceA`

Question

Я пытаюсь реализовать traverse и sequenceA по себе:

Вот моя реализация traverse' с точки зрения sequenceA:

traverse' :: (Functor t, Foldable t, Applicative f) => (a -> f b) -> t a -> f (t b) 
traverse' f x = sequenceA' $ fmap f x 

Однако, я застрял в реализации sequenceA.

sequenceA' :: (Functor t, Foldable t, Applicative f) => t (f a) -> f (t a) 
sequenceA' x = foldr (\a _ -> fmap helper a) (error "...") x 

Я использовал заполнитель для b (error "...") - я не знаю, как создать b данные этих типов.

helper :: (Functor t, Foldable t) => a -> t a 
helper x = error "TODO" 

Кроме того, я использовал функцию helper, чтобы получить этот код, чтобы проверять тип. Но, опять же, это просто звонок error. Пожалуйста, дайте мне понять, как в целом реализовать sequenceA.

Answer 1

Дано:

traverse' :: (Functor t, Foldable t, Applicative f) => (a -> f b) -> t a -> f (t b) 
traverse' a2fb ta = sequenceA' (fmap a2fb ta) 

sequenceA' :: (Functor t, Foldable t, Applicative f) => t (f a) -> f (t a) 
sequenceA' tfa = _ 

Идеальное использование отверстий! Мы даем название всем нашим параметрам (нет необходимости идти впустую и сделать нашу жизнь труднее еще совсем) и приклеить дыру, где должно быть определение. Это дает:

src/Main.hs:8:14: Found hole ‘_’ with type: f (t a) … 

теперь отбрасывать вокруг функции, которая возвращает что-то вроде f (t a). Как назло, traverse' делает и теперь мы можем уточнить нашу дыру в:

sequenceA' :: (Functor t, Foldable t, Applicative f) => t (f a) -> f (t a) 
sequenceA' tfa = traverse _ _ 

src/Main.hs:8:27: Found hole ‘_’ with type: a0 -> f a … 
src/Main.hs:8:29: Found hole ‘_’ with type: t a0 … 

Это первый выглядит неаккуратно, но мы знаем то, что подходит к t a0 для второго, который является нашим tfa. Подключи и пыхтение:

sequenceA' :: (Functor t, Foldable t, Applicative f) => t (f a) -> f (t a) 
sequenceA' tfa = traverse _ tfa 

src/Main.hs:8:27: Found hole ‘_’ with type: f a -> f a … 

Ну, мы знаем функции с этой подписью, и это id. Таким образом, наш окончательный ответ:

traverse' :: (Functor t, Foldable t, Applicative f) => (a -> f b) -> t a -> f (t b) 
traverse' a2fb ta = sequenceA' (fmap a2fb ta) 

sequenceA' :: (Functor t, Foldable t, Applicative f) => t (f a) -> f (t a) 
sequenceA' tfa = traverse id tfa 

Теперь мы можем идти молодой, дикий, и pointfree (-ish):

traverse' :: (Functor t, Foldable t, Applicative f) => (a -> f b) -> t a -> f (t b) 
traverse' a2fb = sequenceA' . fmap a2fb 

sequenceA' :: (Functor t, Foldable t, Applicative f) => t (f a) -> f (t a) 
sequenceA' = traverse id 

Which matches the definitions in Prelude. ~ отверстия ~