Объяснить реализацию Traverse [List] в scalaz-seven - PullRequest
Новая
       36

Объяснить реализацию Traverse [List] в scalaz-seven

7 голосов
/ 15 марта 2012

Я пытаюсь понять реализацию traverseImpl в scalaz-seven : 

def traverseImpl[F[_], A, B](l: List[A])(f: A => F[B])(implicit F: Applicative[F]) = {
  DList.fromList(l).foldr(F.point(List[B]())) {
     (a, fbs) => F.map2(f(a), fbs)(_ :: _)
  }
}

Может кто-нибудь объяснить, как List взаимодействует с Applicative? В конечном счете, я хотел бы иметь возможность реализовать другие экземпляры для Traverse.

Ответы [ 3 ]

9 голосов
/ 15 марта 2012

Аппликатив позволяет применять функцию в контексте к значению в контексте.Например, вы можете применить some((i: Int) => i + 1) к some(3) и получить some(4).Давайте забудем это сейчас.Я вернусь к этому позже.

Список имеет два представления: либо Nil, либо head :: tail.Вы можете использовать его для сворачивания, используя foldLeft, но есть другой способ сложить его: 

def foldr[A, B](l: List[A], acc0: B, f: (A, B) => B): B = l match {
   case Nil => acc0
   case x :: xs => f(x, foldr(xs, acc0, f))
}

Учитывая List(1, 2), мы сворачиваем список, применяя функцию, начиная с правой стороны - дажехотя мы действительно деконструируем список с левой стороны! 

f(1, f(2, Nil))

Это можно использовать для вычисления длины списка.Дано List(1, 2): 

foldr(List(1, 2), 0, (i: Int, acc: Int) => 1 + acc)
// returns 2

Это также может быть использовано для создания другого списка: 

foldr[Int, List[Int]](List(1, 2), List[Int](), _ :: _)
//List[Int] = List(1, 2)

Так дан пустой список и функция ::мы смогли создать еще один список.Что если наши элементы находятся в некотором контексте ?Если наш контекст является аппликативным, мы все равно можем применить наши элементы и :: в этом контексте.Продолжая с List(1, 2) и Option в качестве нашего аппликатива.Мы начинаем с some(List[Int]())), мы хотим применить функцию :: в контексте Option.Это то, что делает F.map2.Он принимает два значения в их контексте Option, помещает предоставленную функцию двух аргументов в контекст Option и применяет их вместе.

Итак, вне контекста мы имеем (2, Nil) => 2 :: Nil

В контексте имеем: (Some(2), Some(Nil)) => Some(2 :: Nil)

Возвращаясь к исходному вопросу: 

// do a foldr 
DList.fromList(l).foldr(F.point(List[B]())) {
  // starting with an empty list in its applicative context F.point(List[B]())
  (a, fbs) => F.map2(f(a), fbs)(_ :: _)
  // Apply the `::` function to the two values in the context
}

Я не уверен, почему используется разница DList.Что я вижу, так это то, что он использует батуты, так что надеюсь, что эта реализация будет работать без потери стека, но я не пробовал, поэтому я не знаю.

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

Например, учитывая: 

trait Tree[+A]
object Leaf extends Tree[Nothing]
case class Node[A](a: A, left: Tree[A], right: Tree[A]) extends Tree[A]

Fold будет определен следующим образом (который действительно следует тому же подходу, что и для List): 

def fold[A, B](tree: Tree[A], valueForLeaf: B, functionForNode: (A, B, B) => B): B = {
  tree match {
    case Leaf => valueForLeaf
    case Node(a, left, right) => functionForNode(a, 
        fold(left, valueForLeaf, functionForNode), 
        fold(right, valueForLeaf, functionForNode)
      )
  }
}

Иtraverse будет использовать это fold с F.point(Leaf) и применить его к Node.apply.Хотя F.map3 нет, так что это может быть немного громоздко.

6 голосов
/ 15 марта 2012

Это не так легко понять. Я рекомендую прочитать статью в начале моего блога на тему .

Я также сделал презентацию на эту тему во время последней встречи по функциональному программированию в Сиднее, и вы можете найти слайды здесь .

Если я попытаюсь объяснить в нескольких словах, traverse будет обходить каждый элемент списка один за другим, в конечном итоге перестраивая список (_ :: _), но накапливая / выполняя некоторые "эффекты" как дается F Applicative. Если F равен State, он отслеживает некоторое состояние. Если F является аппликативом, соответствующим Monoid, оно агрегирует какую-то меру для каждого элемента списка.

Основное взаимодействие списка и аппликатива происходит с приложением map2, где оно получает элемент F[B] и присоединяет его к другим элементам F[List[B]] по определению F как Applicative и использование конструктора List :: в качестве специальной функции для применения.

Оттуда вы видите, что реализация других экземпляров Traverse - это всего лишь apply использование конструкторов данных структуры данных, которую вы хотите пройти. Если вы посмотрите на связанную презентацию PowerPoint, вы увидите несколько слайдов с обходом двоичного дерева.

2 голосов
/ 16 марта 2012

List#foldRight сносит стек для больших списков.Попробуйте это в REPL: 

List.range(0, 10000).foldRight(())((a, b) => ())

Как правило, вы можете перевернуть список, использовать foldLeft, а затем отменить результат, чтобы избежать этой проблемы.Но с traverse нам действительно нужно обработать элементы в правильном порядке, чтобы убедиться, что эффект обрабатывается правильно.DList - это удобный способ сделать это, благодаря прыжкам на батуте.

В конце эти тесты должны пройти:

https://github.com/scalaz/scalaz/blob/scalaz-seven/tests/src/test/scala/scalaz/TraverseTest.scala#L13 https://github.com/scalaz/scalaz/blob/scalaz-seven/tests/src/test/scala/scalaz/std/ListTest.scala#L11 https://github.com/scalaz/scalaz/blob/scalaz-seven/core/src/main/scala/scalaz/Traverse.scala#L76

...