Статьи

Итерация в Scala — эффективная, но функциональная

Декабрь 17, 2018

Одна из работ , которые повлияли на меня много в 2010 году
Суть Лабиринта итератора Джереми Gibbons и Бруно С. д. С. Оливейра. Он основан на том, что Макбрайд и Патерсон оставили в своем трактате «
Аппликативные функторы» . В статье Гиббона обсуждаются различные аспекты построения обходных структур при наличии эффектов.

В этом посте я расскажу о некоторых функциональных реализациях шаблонов обхода с использованием scalaz. В статье о аппликативных функторах Макбрайд и Патерсон определяют ход как аппликативную операцию отображения.

traverse :: Applicative f => (a -> f b) -> [a] -> f [b]

Gibbons et. и др. использует эту абстракцию для изучения различных структур обхода при наличии эффектов . Статья начинается с фрагмента кода C #, который использует синтаксический сахар foreach для обхода коллекции элементов.

public static int loop<MyObj> (IEnumerable<MyObj> coll){
  int n = 0;
  foreach (MyObj obj in coll){
    n = n+1;
    obj.touch();
  }
  return n;
}

В приведенном выше методе цикла мы делаем две вещи одновременно:

  1. mapping — выполнение некоторой операции touch () над элементами coll с ожиданием того, что мы получим модифицированную коллекцию в конце цикла
  2. накопление — подсчет элементов, который является операцией с состоянием для каждой итерации и которая не зависит от операции, которую мы делаем над элементами

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

В последние выходные я изучал, сколько из этих эффективных функциональных обходов можно выполнить с помощью
скалаза , наиболее близкого к Haskell, который вы можете получить с помощью Scala. Раздел 4.2 оригинальной статьи говорит о двух определенных моделях эффективного обхода. Оба из этих шаблонов объединяют отображение и накопление (как код C # выше), но умело разделяют проблемы, используя функциональные методы. Давайте посмотрим, сколько из этого мы можем справиться с помощью скалярных функторов.

Образец № 1

Первый шаблон обхода накапливает элементы effectfully , но изменяет элементы коллекции чисто и независимо от этого накопления . Вот скалярная реализация collect (см. Оригинальную статью о реализации haskell).

def collect[T[_]:Traverse, A, B, S](f: A => B, t: T[A], g: S => S) =
  t.traverse[({type λ[x] = State[S,x]})#λ, B](a => state((s: S) => (g(s), f(a))))

Для непосвященных аннотация типа в traverse выглядит некрасиво — она ​​существует потому, что scalac не может вывести частичное применение конструкторов типов, и эта проблема будет исправлена, как только Adriaan исправит ошибку 2712 в Scala Trac.

Traverse — один из функторов в скаляре, аналогичный модели Data.Traversable в Haskell.

trait Traverse[T[_]] extends Functor[T] {
  def traverse[F[_] : Applicative, A, B](f: A => F[B], t: T[A]): F[T[B]]

  import Scalaz._

  override def fmap[A, B](k: T[A], f: A => B) = traverse[Identity, A, B](f(_), k)
}

и scalaz определяет реализации класса типов Traverse для множества классов, для которых вы можете вызывать traverse.

Вышеуказанная реализация использует монаду State для обработки эффективных вычислений. Для ознакомления с государственной монадой в скалазе, посмотрите на этот пост от Тони Морриса.

Обратите внимание, что f — это чистая функция, которая отображается на элементах коллекции, g — это функция, которая осуществляет эффективное накопление через монаду State. Используя коллекцию, вот версия метода цикла C #, который мы делали в начале.

val loop = collect((a: Int) => 2 * a, List(10, 20, 30, 40), (i: Int) => i + 1)
loop(0) should equal((4, List(20, 40, 60, 80)))

Теперь у нас есть эффективная итерация без использования изменяемых переменных.

Образец № 2

Второй шаблон обхода изменяет элементы чисто, но зависит от некоторого состояния, которое развивается независимо от элементов. Gibbons et. и др. называет эту абстракцию дисперсией, реализация скаляза которой может быть следующей:

def disperse[T[_]: Traverse, A, S, B](t: T[A], s: A => State[S, B]) =
  t.traverse[({type λ[x] = State[S,x]})#λ, B](s)

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

def label[T[_]: Traverse, A](t: T[A]) = 
  disperse(t, ((a: A) => state((i: Int) => (i+1, i)))) ! 0

label (List (10, 20, 30, 40)) должен равняться (List (0, 1, 2, 3)) и

может также использоваться для реализации примера wordCount, поставляемого с распределением скалаза. На самом деле он считает количество символов и строк в потоке.

def charLineCount[T[_]:Traverse](t: T[Char]) =
  disperse(t, ((a: Char) => state((counts: (Int, Int)) =>
    ((counts._1 + 1, counts._2 + (if (a == '\n') 1 else 0)), (counts._1, counts._2))))) ! (1,1)

charLineCount («кот в шляпе \ n сел на коврик \ n» .toList) .last должно быть равно ((35, 2))

От http://debasishg.blogspot.com/2011/01/iteration-in-scala-effectful-yet.html

37
Share: