Терминология концепции Traversable

Question

Почему мы называем переворот структуры "последовательностью" и почему мы говорим о "обходе" и "обходе"?

Я добавляю реализацию в haskell этих концепций как предмет обсуждения...

class (Functor t, Foldable t) => Traversable t where
    {-# MINIMAL traverse | sequenceA #-}

    -- | Map each element of a structure to an action, evaluate these actions
    -- from left to right, and collect the results. For a version that ignores
    -- the results see 'Data.Foldable.traverse_'.
    traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
    traverse f = sequenceA . fmap f

    -- | Evaluate each action in the structure from left to right, and
    -- and collect the results. For a version that ignores the results
    -- see 'Data.Foldable.sequenceA_'.
    sequenceA :: Applicative f => t (f a) -> f (t a)
    sequenceA = traverse id

Answer 1

Давайте начнем с рассмотрения fmap:

fmap :: Functor t => (a -> b) -> t a -> t b

Мы можем описать, что он делает, как найти все a значения в t a и применяя к ним функцию. Обратите внимание, что бесконечные структуры shenanigans в стороне, порядок, в котором реализация fmap достигает a значения для их изменения не имеют значения для конечного результата.

Теперь давайте посмотрим на traverse:

traverse :: (Applicative f, Traversable t) => (a -> f b) -> t a -> f (t b)

подобно fmap, traverse также включает применение функции к значениям, найденным в структуре (это неудивительно, traverseПредтечей называли mapM). traverseОднако, также производит аппликативные эффекты для каждого из a значения (f в a -> f b), и это включает в себя объединение этих эффектов в некотором порядке, чтобы получить общее f (t b) результат. В общем (т.е. пока f не является коммутативным аппликативом, таким как Maybe), порядок эффектов влияет на результат. Это так, любой Traversable Экземпляр соответствует определенному порядку, в котором значения в структуре будут посещаться. Название "траверс" (то есть, как указывает Уилл Несс "путешествие через или через") предназначено для передачи этого чувства направления.

На связанной ноте, traverse может быть разложен в простое отображение, которое производит эффекты с последующим упорядочением этих эффектов...

sequenceA :: (Applicative f, Traversable t) => t (f a) -> f (t a)

traverse f = sequenceA . fmap f
sequenceA = traverse id

... значит "последовательность" имени.

Стоит также подчеркнуть, что traverse фиксирует различные способы прохождения структуры и выполнения действий на каждой остановке (ср. for быть именем для flip traverse). В частности, мы выздоравливаем fmap выбирая Identity в качестве аппликативного функтора (т.е. фактически не генерируя никаких эффектов), и foldMap (то есть складывание по типу списка) путем выбора Monoid m => Const m вместо. Вещи, которые мы не можем сделать с traverse включает в себя удаление, дублирование или перестановку элементов - это не позволяет разрушать структуру данных произвольным образом, как это делает обычная складка / катаморфизм. С traverseмы можем пройти через Traversable структура, но мы не можем изменить ее.

Answer 2

Это "последовательность", а не "а". Т.е. "Упорядочить в определенном порядке", здесь слева направо. И это обобщение sequence :: Monad m => [m a] -> m [a] (обратите внимание на старый base версия), что может сделать имя более очевидным.