누군가가 Haskell에서 traverse 함수를 설명 할 수 있습니까?

Question

저는 Haskell의 초심자입니다. 나는 Data.Traversable 단위에서 traverse 기능을 사로 잡는 것을 시도하고 실패하고있다. 나는 그 요점을 볼 수 없습니다. 나는 긴급한 배경에서 왔기 때문에 누군가가 명령형 루프의 관점에서 설명해 줄 수 있습니까? 의사 코드는 크게 감사 할 것입니다. 감사.

Answer 1

으로 이해하는 것이 가장 쉽다고 생각합니다. 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은 구조를 취하고 구조의 모든 요소를 ​​응용 프로그램에 맞게 변환 한 다음 해당 응용 프로그램의 부작용을 왼쪽에서 오른쪽으로 정렬하여 결과가 포함 된 동일한 모양의 구조체를 반환합니다.

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 동일하다. 다른 유형의 컨테이너 나 다른 응용 프로그램을 사용할 때 더욱 흥미로워집니다.

Answer 2

traverse은 fmap과 동일하지만 데이터 구조를 다시 작성하는 동안 효과를 실행할 수 있습니다.

Data.Traversable 설명서의 예를 참조하십시오.

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

Tree의 Functor 예는 다음과 같습니다 그것은 모든 값 f을 적용, 전체 트리를 재 구축

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) 

. 생성자가 실용적 스타일이라고를 제외하고

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 클래스에는 원칙적으로 이전 결과에 영향을 줄 수있는 모나드 버전 mapM도 포함되어 있습니다. (당신은 확실히 그렇게 안하고 있지만.) 왼쪽 분기 Empty이다 두 번 예를 들어, f의 효과를 수행

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. 비 결정론 (Applicative 모델의 목록 인스턴스)과 언어에 기본 제공 기능이 없기를 바란다면 운이 좋지 않습니다.

Answer 3

traverse 사물에서 Applicative의를 만드는 기능을 지정해, Applicative "내부"사물의 Traversable에 Traversable 내부 일을집니다.

Maybe을 Applicative으로 사용하고 목록을 Traversable으로 지정하십시오. 다른 우리가 Nothing를 얻을 수도있는 경우

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

그래서, 우리는 (A Just) 안에 그것의 절반을 얻을 : 처음에 우리는 변환 기능이 필요합니다. 모두가 "잘"가는 경우는 다음과 같습니다

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

하지만 ... 인수

traverse half [1..10] 
-- Nothing 

이유는 <*> 기능은 결과를 작성하는 데 사용된다는 점이다

, 하나를 Nothing이면 Nothing이 다시 나타납니다.

다른 예 :이 함수는 콘텐츠 x 예컨대 길이와 x 목록을 생성

rep x = replicate 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 4

traverse는 루프입니다. 구현은 통과 할 데이터 구조에 따라 다릅니다. 그 목록, 트리, 어쩌면, Seq (ence), 또는 behing의 일반적인 방법은 sth를 통해 통과했다 아무것도있을 수 있습니다. for-loop 또는 recursive 함수와 같습니다. Array는 for 루프, List는 while 루프, tree는 sth 중 하나를 가질 수 있습니다. 재귀 적 또는 스택과 while 루프의 결합; 함수형 언어에서는 이러한 복잡한 루프 명령이 필요하지 않습니다. 루프의 내부 부분 (함수 모양)을 데이터 구조와 더 직접적으로 덜 모호하게 결합합니다.

Traversable typeclass를 사용하면 알고리즘을보다 독립적이고 다재다능하게 작성할 수 있습니다. 그러나 Traversable은 일반적으로 알고리즘을 기존 데이터 구조에 붙이기 위해서만 사용됩니다. 다른 데이터 유형에 대해 유사한 함수를 작성할 필요가 없도록하는 것이 좋습니다.

Answer 5

mapper 함수 내부에서 부작용을 실행할 수 있다는 점을 제외하고는 fmap과 비슷합니다. 이는 결과 유형을 변경합니다.

데이터베이스에있는 사용자 ID를 나타내는 정수 목록을 생각해보십시오 : [1, 2, 3]. 이 사용자 ID를 사용자 이름에 fmap으로 지정하려면 사용자 이름을 읽으려면 데이터베이스에 액세스해야하는 함수 (이 경우 부작용이 필요합니다.이 경우 IO 모나드를 사용하기 때문에)를 사용하여 전통적인 fmap을 사용할 수 없습니다).

traverse의 서명은 다음과 같습니다

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

---

가있다 : traverse와

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

, 당신이 할 수있는 부작용 따라서, 사용자 이름 매핑 사용자 ID에 대한 코드는 같습니다 또한 mapM이라는 함수 :

mapM :: Monad m => (a -> m b) -> [a] -> m [b] 

mapM의 모든 용도는 traverse으로 바꿀 수 있지만 다른 방법으로는 사용할 수 없습니다. mapM은 보통 traverse보다 우수하지만, mapM은 목록이있는 모나드에서만 작동하며, traverse은보다 일반적인 것입니다.

부작용을 피하고 유용한 값을 반환하지 않으려는 경우이 함수의 traverse_ 및 mapM_ 버전이 있으며 둘 다 함수의 반환 값을 무시하고 약간 빠릅니다.