Хватка неизменных структур данных

Question

Я изучаю scala и, будучи хорошим учеником, я стараюсь соблюдать все правила, которые я нашел.

Одно из правил: НЕИЗБЕЖНОСТЬ !!!

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

Но сегодня я подумал про себя: единственное важное, что у объекта / класса не должно быть изменяемого состояния. Я не обязан кодировать все методы в неизменном стиле, потому что эти методы не влияют друг на друга.

Мой вопрос: Я прав или есть какие-то проблемы / недостатки, которых я не вижу ?

EDIT:

Пример кода для айшварьи:

def logLikelihood(seq: Iterator[T]): Double = {
  val sequence = seq.toList
  val stateSequence = (0 to order).toList.padTo(sequence.length,order)
  val seqPos = sequence.zipWithIndex

  def probOfSymbAtPos(symb: T, pos: Int) : Double = {
    val state = states(stateSequence(pos))
    M.log(state( seqPos.map( _._1 ).slice(0, pos).takeRight(order), symb))
  }

  val probs = seqPos.map( i => probOfSymbAtPos(i._1,i._2) )

  probs.sum
}  

Объяснение: Это метод для вычисления логарифмической вероятности однородной марковской модели переменного порядка. Метод применения состояния принимает все предыдущие символы и предстоящий символ и возвращает вероятность этого.

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

Answer 1

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

Принцип ссылочной прозрачности (RT) таков:

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

Обратите внимание, что если e создает и мутирует некое локальное состояние, это не нарушает RT, поскольку никто не может наблюдать это.

Тем не менее, я очень сомневаюсь, что ваша реализация более проста с vars.

Answer 2

Случай для функционального программирования - один из вариантов , который является лаконичным в вашем коде и вводит более математический подход . Это может уменьшить вероятность ошибок и сделать ваш код меньше и более читабельным. Что касается простоты или нет, это требует, чтобы вы думали о своих проблемах по-другому. Но как только вы привыкнете мыслить с помощью функциональных паттернов, вполне вероятно, что функционал станет легче, чем более императивный стиль.

Действительно трудно быть полностью функциональным и иметь нулевое изменяемое состояние, но очень выгодно иметь минимальное изменяемое состояние . Следует помнить, что все, что нужно сделать , должно быть сбалансировано, а не до крайности . Сокращая количество изменяемого состояния, вы в конечном итоге усложняете написание кода с непредвиденными последствиями. Обычным примером является наличие изменяемой переменной, значение которой является неизменным. Таким образом, тождество (именованная переменная) и значение (неизменяемый объект, которому может быть присвоена переменная) разделены.

var acc: List[Int] = Nil
// lots of complex stuff that adds values
acc ::= 1
acc ::= 2
acc ::= 3
// do loop current list
acc foreach { i => /* do stuff that mutates acc */ acc ::= i * 10 }
println( acc ) // List( 1, 2, 3, 10, 20, 30 )

foreach зацикливается на значении acc во время запуска foreach. Любые мутации в acc не влияют на цикл. Это намного безопаснее, чем типичные итераторы в java, где список может измениться в середине итерации.

Существует также проблема параллелизма. Неизменяемые объекты полезны из-за спецификации модели памяти JSR-133 , которая утверждает, что инициализация конечных элементов объекта произойдет до того, как какой-либо поток сможет увидеть эти элементы, точка! Если они не являются окончательными, то они «изменчивы», и нет гарантии правильной инициализации.

Актеры - идеальное место для изменения состояния . Объекты, которые представляют данные, должны быть неизменными. Возьмите следующий пример.

object MyActor extends Actor {
  var acc: List[Int] = Nil
  def act() {
    loop {
      react {
        case i: Int => acc ::= i
        case "what is your current value" => reply( acc )
        case _ => // ignore all other messages
      }
    }
  }
}

В этом случае мы можем отправить значение acc (которое представляет собой List) и не беспокоиться о синхронизации, поскольку List является неизменным aka все члены объекта List являются окончательными. Также из-за неизменности мы знаем, что никакой другой актер не может изменить базовую структуру данных, которая была отправлена, и, таким образом, никакой другой актер не может изменить изменяемое состояние этого актера .

Answer 3

Поскольку Apocalisp уже упомянул материал, на котором я собирался процитировать его, я буду обсуждать код. Вы говорите, что это просто умножение, но я не вижу этого - оно ссылается как минимум на три важных метода, определенных снаружи: order, states и M.log. Я могу сделать вывод, что order является Int, и что states возвращает функцию, которая принимает List[T] и T и возвращает Double.

Там также происходят некоторые странные вещи ...

def logLikelihood(seq: Iterator[T]): Double = {
  val sequence = seq.toList

sequence никогда не используется, кроме как для определения seqPos, так зачем это делать?

  val stateSequence = (0 to order).toList.padTo(sequence.length,order)
  val seqPos = sequence.zipWithIndex

  def probOfSymbAtPos(symb: T, pos: Int) : Double = {
    val state = states(stateSequence(pos))
    M.log(state( seqPos.map( _._1 ).slice(0, pos).takeRight(order), symb))

На самом деле, вы могли бы использовать sequence здесь вместо seqPos.map( _._1 ), поскольку все, что нужно, это отменить zipWithIndex. Кроме того, slice(0, pos) это просто take(pos).

  }

  val probs = seqPos.map( i => probOfSymbAtPos(i._1,i._2) )

  probs.sum
}

Теперь, учитывая отсутствующие методы, трудно утверждать, как это действительно должно быть написано в функциональном стиле. Хранение таинственных методов даст:

def logLikelihood(seq: Iterator[T]): Double = {
  import scala.collection.immutable.Queue
  case class State(index: Int, order: Int, slice: Queue[T], result: Double)

  seq.foldLeft(State(0, 0, Queue.empty, 0.0)) {
    case (State(index, ord, slice, result), symb) =>
      val state = states(order)
      val partial = M.log(state(slice, symb))
      val newSlice = slice enqueue symb
      State(index + 1, 
            if (ord == order) ord else ord + 1, 
            if (queue.size > order) newSlice.dequeue._2 else newSlice,
            result + partial)
  }.result
}

Только я подозреваю, что материал state / M.log может быть также частью State. Я замечаю другие оптимизации сейчас, когда я написал это так. Раздвижное окно, которое вы используете, напоминает мне, конечно, sliding:

seq.sliding(order).zipWithIndex.map { 
  case (slice, index) => M.log(states(index + order)(slice.init, slice.last))
}.sum

Это начнется только с элемента orderth, так что некоторая адаптация будет в порядке. Не слишком сложно, хотя. Итак, давайте перепишем это снова:

def logLikelihood(seq: Iterator[T]): Double = {
  val sequence = seq.toList
  val slices = (1 until order).map(sequence take) ::: sequence.sliding(order)
  slices.zipWithIndex.map { 
    case (slice, index) => M.log(states(index)(slice.init, slice.last))
  }.sum
}

Хотел бы я видеть M.log и states ... Держу пари, я мог бы превратить это map в foldLeft и покончить с этими двумя методами. И я подозреваю, что метод, возвращаемый states, может принять весь срез вместо двух параметров.

Все же ... неплохо, не правда ли?