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

Ответ 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 почти то же самое, за исключением того, что конструкторы вызываются в аппликативном стиле. Это означает, что мы можем иметь (побочные) эффекты при восстановлении дерева. Аппликация почти такая же, как монады, за исключением того, что эффекты не могут зависеть от предыдущих результатов. В этом примере это означает, что вы не могли бы сделать что-то другое с правой ветвью node в зависимости от результатов перестройки левой ветки, например.

Класс Traversable также содержит монадическую версию mapM, где эффекты могут в принципе зависеть от предыдущих результатов. (Хотя вы определенно не должны этого делать.) Например, выполните эффект f дважды, если левая ветвь Empty:

mapM f (Node l k r) = do
  l' <- mapM f l
  k' <- case l' of
    Empty -> do _ <- f k; f k
    _     -> f k
  r' <- mapM f r
  return $ Node l' k' r'

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

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

Реализация этого как это ограничивает вас эффектами, которые позволяет язык. Если вы f.e. хотите не детерминировать (который экземпляр списка Аппликативных моделей) и ваш язык не имеют его встроенного, вам не повезло.

Ответ 2

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

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

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

Итак, если число четное, мы получаем половину его (внутри a 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]]

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

So 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"]

Конечно, в этом случае он эквивалентен mapM из Prelude. Это становится более интересным при использовании на других типах контейнеров или с использованием других аппликаций.

Ответ 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 :: Monad m => (a -> m b) -> [a] -> m [b]

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

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

Ответ 5

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

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