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

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 как об обратном порядке двух функторов, например, переход от списка действий к действию, возвращающему списокresults.

Итак, 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, за исключением того, что вы можете запускать эффекты внутри функции отображения, которая также меняет тип результата.

Представьте список целых чисел, представляющих идентификаторы пользователей в базе данных: [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 обычно используется только для простого склеивания алгоритмов с существующими структурами данных.Неплохо не писать одинаковые функции для разных типов данных.