Что такое правильное понимание монады или последовательности как для карты, так и для переноса состояния?

Ответ 1

С комбинатором карт с аккумулятором (простой способ)

Вы можете выбрать более высокий порядок mapAccumL. Это в стандартной библиотеке Haskell , но для Scala вам нужно будет использовать что-то вроде Scalaz..

Сначала импортируем (обратите внимание, что я использую Scalaz 7 здесь, для предыдущих версий вы импортируете Scalaz._):

import scalaz._, syntax.std.list._

И затем это однострочный:

scala> d.mapAccumLeft(initialState, computeResultAndNewState)
res1: (State, List[ResType]) = (State(3),List(1, 3, 5))

Обратите внимание, что мне пришлось отменить порядок ваших аргументов оценщика и кортеж возвращаемого значения в соответствии с сигнатурами, ожидаемыми mapAccumLeft (сначала укажите сначала в обоих случаях).

С государственной монадой (немного менее простой способ)

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

Прежде всего, Scalaz предоставляет mapM -и называемый traverse (что немного более общее, как отмечает Петр Пудлак в своем комментарии). Итак, предположим, что у нас есть следующее (я снова использую Scalaz 7):

import scalaz._, Scalaz._

type ResType = Int
case class Container(i: ResType)

val initial = Container(0)
val d = List("1", "2", "3")

def compute(s: String): State[Container, ResType] = State {
  case Container(i) => (Container(i + 1), s.toInt + i)
}

Мы можем написать это:

d.traverse[({type L[X] = State[Container, X]})#L, ResType](compute).run(initial)

Если вам не нравится лямбда уродливого типа, вы можете избавиться от него следующим образом:

type ContainerState[X] = State[Container, X]

d.traverse[ContainerState, ResType](compute).run(initial)

Но это становится еще лучше! Scalaz 7 дает вам версию traverse, которая специализируется на государственной монаде:

scala> d.traverseS(compute).run(initial)
res2: (Container, List[ResType]) = (Container(3),List(1, 3, 5))

И как будто этого было недостаточно, есть даже версия с встроенным run:

scala> d.runTraverseS(initial)(compute)
res3: (Container, List[ResType]) = (Container(3),List(1, 3, 5))

Все еще не так хорошо, как версия mapAccumLeft, на мой взгляд, но довольно чистая.

Ответ 2

То, что вы описываете, - это вычисление в государственной монаде. Я считаю, что ответ на ваш вопрос

Это не сгиб, потому что результаты выходят как карта. Это не карта из-за поддержки штата.

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

Значения государственной монады - это вычисления, которые считывают некоторое внутреннее состояние, возможно, изменяют его и возвращают некоторое значение. Он часто используется в Haskell (см. здесь или здесь).

Для Scala в библиотеке ScalaZ есть trait, называемая State, которая ее моделирует (см. также источник). В States существуют методы утилиты для создания экземпляров State. Обратите внимание, что с монадической точки зрения State является просто монадическим значением. Сначала это может показаться запутанным, потому что оно описывается функцией, зависящей от состояния. (Монадическая функция будет чем-то типа A => State[B].)

Далее вам нужна монадическая функция карты, которая вычисляет значения ваших выражений, пронизывая состояние через вычисления. В Haskell существует библиотечный метод mapM, который делает именно это, когда он специализируется на государственной монаде.

В Scala нет такой библиотечной функции (если она есть, пожалуйста, исправьте меня). Но это возможно создать. Чтобы привести полный пример:

import scalaz._;

object StateExample
  extends App
  with States /* utility methods */
{
  // The context that is threaded through the state.
  // In our case, it just maps variables to integer values.
  class Context(val map: Map[String,Int]);

  // An example that returns the requested variable value
  // and increases it value in the context.
  def eval(expression: String): State[Context,Int] =
    state((ctx: Context) => {
      val v = ctx.map.get(expression).getOrElse(0);
      (new Context(ctx.map + ((expression, v + 1)) ), v);
    });

  // Specialization of Haskell mapM to our State monad.
  def mapState[S,A,B](f: A => State[S,B])(xs: Seq[A]): State[S,Seq[B]] =
    state((initState: S) => {
      var s = initState;
      // process the sequence, threading the state
      // through the computation
      val ys = for(x <- xs) yield { val r = f(x)(s); s = r._1; r._2 };
      // return the final state and the output result
      (s, ys);
    });


  // Example: Try to evaluate some variables, starting from an empty context.
  val expressions = Seq("x", "y", "y", "x", "z", "x");

  print( mapState(eval)(expressions) ! new Context(Map[String,Int]()) );
}

Таким образом, вы можете создавать простые функции, которые принимают некоторые аргументы и возвращают State, а затем объединяют их в более сложные, используя State.map или State.flatMap (или, возможно, лучше используя for), а затем вы может выполнить все вычисление в списке выражений с помощью mapM.

См. также http://blog.tmorris.net/posts/the-state-monad-for-scala-users/

Изменить: Обратите внимание на Travis Brown, он описал, как лучше использовать государственную монаду в Scala.

Он также спрашивает:

Но почему, когда есть стандартный комбинатор, который делает именно то, что вам нужно в этом случае? (Я прошу об этом как о том, кого ударили за использование государственной монады, когда сделал бы mapAccumL.)

Это потому, что исходный вопрос спросил:

Это не сгиб, потому что результаты выходят как карта. Это не карта из-за поддержки штата.

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

Использование mapAccumL, безусловно, быстрее, как меньше памяти, так и накладных расходов процессора. Но государственная монада фиксирует концепцию происходящего, суть проблемы. Я считаю, что во многих случаях (если не в большинстве) это более важно. Когда мы осознаем суть проблемы, мы можем либо использовать концепции высокого уровня, чтобы красиво описать решение (возможно, немного пожертвовав скоростью/памятью), либо оптимизировать его, чтобы быть быстрым (или, возможно, даже сделать это).

С другой стороны, mapAccumL решает эту конкретную проблему, но не дает более широкого ответа. Если нам нужно немного изменить его, возможно, это не сработает. Или, если библиотека начинает быть сложной, код может начать быть беспорядочным, и мы не будем знать, как его улучшить, как снова сделать оригинальную идею.

Например, в случае оценки выражений с выражением состояния библиотека может стать сложной и сложной. Но если мы используем государственную монаду, мы можем построить библиотеку вокруг небольших функций, каждая из которых принимает некоторые аргументы и возвращает что-то вроде State[Context,Result]. Эти атомные вычисления могут быть объединены с более сложными методами flatMap или for, и, наконец, мы построим желаемую задачу. Принцип останется неизменным во всей библиотеке, и конечной задачей будет также то, что возвращает State[Context,Result].

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

Ответ 3

Вы можете сделать это рекурсивно:

def testTheRecWay(xs: Seq[String]) = {
  def innerTestTheRecWay(xs: Seq[String], priorState: State = initialState, result: Vector[ResType] = Vector()): Seq[ResType] = {
    xs match {
      case Nil => result
      case x :: tail =>
        val (res, newState) = computeResultAndNewState(x, priorState)
        innerTestTheRecWay(tail, newState, result :+ res)
    }
  }
  innerTestTheRecWay(xs)
}

Рекурсия - обычная практика в функциональном программировании, и в большинстве случаев ее легче читать, писать и понимать, чем циклы. Фактически scala не имеет никаких петель, кроме while. fold, map, flatMap, for (что является просто сахаром для flatMap/map) и т.д. являются рекурсивными.

Этот метод является хвостом рекурсивным и будет оптимизирован компилятором, чтобы не строить стек, поэтому он абсолютно безопасен в использовании. Вы можете добавить аннотацию @annotation.tailrec, чтобы заставить компилятор применить исключение хвостовой рекурсии. Если ваш метод не является tailrec, тогда компилятор будет жаловаться.

edit: переименованный внутренний метод, чтобы избежать двусмысленности