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

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));
}

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