누군가 Haskell의 트래버스 기능을 설명 할 수 있습니까?

누군가 Haskell의 트래버스 기능을 설명 할 수 있습니까?

---

에서 traverse기능을 시도하고 실패했습니다 Data.Traversable. 나는 그 요점을 볼 수 없다. 내가 명령형 배경에서 왔기 때문에 누군가 명령형 루프 측면에서 나에게 설명해 주시겠습니까? 의사 코드를 많이 주시면 감사하겠습니다. 감사.

---

traversefmap데이터 구조를 재 구축하는 동안 효과를 실행할 수 있다는 점을 제외 하면과 동일 합니다.

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생성자가 실용적 스타일이라고를 제외하고 인스턴스는 거의 동일합니다. 이것은 우리가 트리를 재건하는 동안 (부작용) 효과를 가질 수 있음을 의미합니다. Applicative는 효과가 이전 결과에 의존 할 수 없다는 점을 제외하면 모나드와 거의 동일합니다. 이 예에서는 예를 들어 왼쪽 분기를 다시 빌드 한 결과에 따라 노드의 오른쪽 분기에 다른 작업을 수행 할 수 없음을 의미합니다.

역사적인 이유로, Traversable클래스는의 모나드 버전이 들어 traverse라는를 mapM. 모든 의도와 목적 mapM에 대해 동일 합니다. 나중에 야 슈퍼 클래스가 traverse되었기 때문에 별도의 메서드로 존재합니다 .ApplicativeMonad

이를 불순한 언어로 구현하면 부작용을 방지 할 수있는 방법이 없기 때문에과 fmap동일 traverse합니다. 데이터 구조를 재귀 적으로 탐색해야하므로 루프로 구현할 수 없습니다. 다음은 Javascript에서 수행하는 방법에 대한 작은 예입니다.

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

이렇게 구현하면 언어가 허용하는 효과로 제한됩니다. 비결정론 (응용 모델의 목록 인스턴스)을 원하고 언어에 기본 제공되지 않는 경우 운이 좋지 않습니다.

---

traverses를 사물로 만드는 함수가 주어지면 내부의 사물을 "내부"사물 Traversable로 바꿉니다 .TraversableApplicativeApplicative

하자의 사용 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]]

---

나는 다음과 같이 정의 할 수 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 takes some structure, and applies f to transform every element in the structure into some applicative, it then sequences up the effects of those applicatives from left to right, returning a structure with the same shape containing the results.

You can also compare it to Foldable, which defines the related function traverse_.

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

So you can see that the key difference between Foldable and Traversable is that the latter allows you to preserve the shape of the structure, whereas the former requires you to fold the result up into some other value.

---

A simple example of its usage is using a list as the traversable structure, and IO as the applicative:

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

While this example is rather unexciting, things get more interesting when traverse is used on other types of containers, or using other applicatives.

---

It's kind of like fmap, except that you can run effects inside the mapper function, which also changes the result type.

Imagine a list of integers representing user IDs in a database: [1, 2, 3]. If you want to fmap these user IDs to usernames, you can't use a traditional fmap, because inside the function you need to access the database to read the usernames (which requires an effect -- in this case, using the IO monad).

The signature of traverse is:

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

With traverse, you can do effects, therefore, your code for mapping user IDs to usernames looks like:

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

---

There's also a function called mapM:

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

Any use of mapM can be replaced with traverse, but not the other way around. mapM only works for monads, whereas traverse is more generic.

If you just want to achieve an effect and not return any useful value, there are traverse_ and mapM_ versions of these functions, both of which ignore the return value from the function and are slightly faster.

---

traverse is the loop. Its implementation depends on the data structure to be traversed. That might be a list, tree, Maybe, Seq(uence), or anything that has a generic way of being traversed via something like a for-loop or recursive function. An array would have a for-loop, a list a while-loop, a tree either something recursive or the combination of a stack with a while-loop; but in functional languages you do not need these cumbersome loop commands: you combine the inner part of the loop (in the shape of a function) with the data structure in a more directly manner and less verbose.

With the Traversable typeclass, you could probably write your algorithms more independent and versatile. But my experience says, that Traversable is usually only used to simply glue algorithms to existing data structures. It is quite nice not to need to write similar functions for different datatypes qualified, too.

참고URL : https://stackoverflow.com/questions/7460809/can-someone-explain-the-traverse-function-in-haskell