Может кто-нибудь объяснить функцию перемещения в Хаскеле?

Question

Я пытаюсь и не могу ухватить traverse функция от Data.Traversable, Я не могу понять его смысл. Так как я имею императивное происхождение, может кто-нибудь объяснить мне это с точки зрения императивного цикла? Псевдокод будет высоко ценится. Благодарю.

Answer 1

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

Взгляните на пример из Data.Traversable документация.

 data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)

Functor экземпляр Tree было бы:

instance Functor Tree where
  fmap f Empty        = Empty
  fmap f (Leaf x)     = Leaf (f x)
  fmap f (Node l k r) = Node (fmap f l) (f k) (fmap f r)

Восстанавливает все дерево, применяя f к каждому значению.

instance Traversable Tree where
    traverse f Empty        = pure Empty
    traverse f (Leaf x)     = Leaf <$> f x
    traverse f (Node l k r) = Node <$> traverse f l <*> f k <*> traverse f r

Traversable Экземпляр почти такой же, за исключением того, что конструкторы вызываются в аппликативном стиле. Это означает, что мы можем иметь (побочные) эффекты при перестройке дерева. Аппликатив почти такой же, как монады, за исключением того, что эффекты не могут зависеть от предыдущих результатов. В этом примере это означает, что вы не могли сделать что-то отличное от правой ветви узла в зависимости, например, от результатов перестройки левой ветви.

По историческим причинам Traversable класс также содержит монадическую версию traverse называется mapM, Для всех намерений и целей mapM такой же как traverse - существует как отдельный метод, потому что Applicative только позже стал суперклассом Monad,

Если бы вы реализовали это на нечистом языке, fmap будет так же, как traverse, так как нет способа предотвратить побочные эффекты. Вы не можете реализовать его как цикл, так как вы должны рекурсивно обходить свою структуру данных. Вот небольшой пример того, как я бы сделал это в Javascript:

Node.prototype.traverse = function (f) {
  return new Node(this.l.traverse(f), f(this.k), this.r.traverse(f));
}

Реализация его таким образом ограничивает эффекты, которые допускает язык. Если вы хотите недетерминированности (например, списка экземпляров Applicative моделей), а в вашем языке нет встроенных функций, вам не повезло.

Answer 2

traverse превращает вещи в Traversable в Traversable вещей "внутри" и Applicative, учитывая функцию, которая делает Applicativeиз вещей.

Давайте использовать Maybe как Applicative и перечислить как Traversable, Сначала нам понадобится функция преобразования:

half x = if even x then Just (x `div` 2) else Nothing

Так что, если число четное, мы получаем половину его (внутри Just), иначе мы получим Nothing, Если все идет хорошо, это выглядит так:

traverse half [2,4..10]
--Just [1,2,3,4,5]

Но...

traverse half [1..10]
-- Nothing

Причина в том, что <*> Функция используется для построения результата, и когда один из аргументов Nothing, мы получаем Nothing назад.

Другой пример:

rep x = replicate x x

Эта функция генерирует список длины x с содержанием xнапример, rep 3 знак равно [3,3,3], Каков результат traverse rep [1..3]?

Мы получаем частичные результаты [1], [2,2] а также [3,3,3] с помощью rep, Теперь семантика списков как Applicatives "взять все комбинации", например (+) <$> [10,20] <*> [3,4] является [13,14,23,24],

"Все комбинации" [1] а также [2,2] два раза [1,2], Все комбинации по два раза [1,2] а также [3,3,3] шесть раз [1,2,3], Итак, мы имеем:

traverse rep [1..3]
--[[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3],[1,2,3]]

Answer 3

Я думаю, что это проще всего понять с точки зрения sequenceA, как traverse можно определить следующим образом.

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

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

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

Вы также можете думать о sequenceA как изменение порядка двух функторов, например, переход от списка действий к действию, возвращающему список результатов.

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

Вы также можете сравнить его с Foldable, который определяет связанную функцию traverse_,

traverse_ :: (Foldable t, Applicative f) => (a -> f b) -> t a -> f ()

Итак, вы можете видеть, что ключевое различие между Foldable а также Traversable в том, что последнее позволяет вам сохранить форму структуры, тогда как первое требует, чтобы вы свернули результат в какое-то другое значение.

---

Простым примером его использования является использование списка в качестве прослеживаемой структуры, и IO в качестве аппликативного:

λ> import Data.Traversable
λ> let qs = ["name", "quest", "favorite color"]
λ> traverse (\thing -> putStrLn ("What is your " ++ thing ++ "?") *> getLine) qs
What is your name?
Sir Lancelot
What is your quest?
to seek the holy grail
What is your favorite color?
blue
["Sir Lancelot","to seek the holy grail","blue"]

Хотя этот пример довольно неинтересен, все становится интереснее, когда traverse используется на других типах контейнеров, или с использованием других аппликативов.

Answer 4

Это вроде как fmap, за исключением того, что вы можете запускать эффекты внутри функции mapper, которая также меняет тип результата.

Представьте себе список целых чисел, представляющих идентификаторы пользователей в базе данных: [1, 2, 3], Если хотите fmap эти идентификаторы пользователей к именам пользователей, вы не можете использовать традиционные fmapпотому что внутри функции вам нужен доступ к базе данных для чтения имен пользователей (что требует эффекта - в этом случае, используя IO монада).

Подпись traverse является:

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

С traverseВы можете создавать эффекты, поэтому ваш код для сопоставления идентификаторов пользователей с именами пользователей выглядит следующим образом:

mapUserIDsToUsernames :: (Num -> IO String) -> [Num] -> IO [String]
mapUserIDsToUsernames fn ids = traverse fn ids

---

Там также есть функция под названием mapM:

mapM :: (Traversable t, Monad m) => (a -> m b) -> t a -> m (t b)

Любое использование mapM можно заменить на traverse, но не наоборот. mapM работает только для монад, тогда как traverse является более общим.

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

Answer 5

traverse это петля. Его реализация зависит от структуры данных, которую необходимо пройти. Это может быть список, дерево, Maybe, Seq(uence), или что-нибудь, что имеет общий способ обхода через что-то вроде цикла for или рекурсивной функции. Массив будет иметь цикл for, список цикла while, дерево либо что-то рекурсивное, либо комбинацию стека с циклом while; но в функциональных языках вам не нужны эти громоздкие команды цикла: вы комбинируете внутреннюю часть цикла (в форме функции) со структурой данных более прямым и менее многословным способом.

С Traversable Класс типов, вы могли бы написать свои алгоритмы более независимыми и универсальными. Но мой опыт говорит, что Traversable обычно используется только для простого склеивания алгоритмов с существующими структурами данных. Неплохо не писать одинаковые функции для разных типов данных.