Можно ли оптимизировать программу Free Monad перед выполнением? - PullRequest
Новая
       28

Можно ли оптимизировать программу Free Monad перед выполнением?

2 голосов
/ 27 января 2020

Я недавно выбрал шаблон Free Monad, используя cats , пытаясь создать DSL, который можно «упростить» перед выполнением. Например, скажем, я создаю язык для взаимодействия со списками: 

  sealed trait ListAction[A]
  case class ListFilter[A](in: List[A], p: A => Boolean) extends ListAction[List[A]]
  case class ListMap[A, B](in: List[A], f: A => B) extends ListAction[List[B]]

  type ListProgram[A] = Free[ListAction, A]

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

// Pseudo code - doesn't compile, just illustrates my intent

def optimise[A](program: ListProgram[A]): ListProgram[A] = {
  case ListFilter(ListFilter(in, p1), p2) => optimise(ListFilter(in, { a: A => p1(a) && p2(a) }))
  case ListMap(ListMap(in, f1), f2) => optimise(ListMap(in, f2 compose f1))
}

Возможно ли это с помощью Free Monad, либо путем проверки последнего действия при добавлении в программу, либо путем оптимизации, как указано выше? Большое спасибо.

Ниже приведен код, который я использовал для создания своих программ: 

  trait ListProgramSyntax[A] {
    def program: ListProgram[List[A]]

    def listFilter(p: A => Boolean): ListProgram[List[A]] = {
      program.flatMap { list: List[A] =>
        Free.liftF[ListAction, List[A]](ListFilter(list, p))
      }
    }

    def listMap[B](f: A => B): ListProgram[List[B]] = program.flatMap { list =>
      Free.liftF(ListMap(list, f))
    }
  }

  implicit def syntaxFromList[A](list: List[A]): ListProgramSyntax[A] = {
    new ListProgramSyntax[A] {
      override def program: ListProgram[List[A]] = Free.pure(list)
    }
  }

  implicit def syntaxFromProgram[A](existingProgram: ListProgram[List[A]]): ListProgramSyntax[A] = {
    new ListProgramSyntax[A] {
      override def program: ListProgram[List[A]] = existingProgram
    }
  }

Например: 

  val program = (1 to 5).toList
    .listMap(_ + 1)
    .listMap(_ + 1)
    .listFilter(_ % 3 == 0)

РЕДАКТИРОВАТЬ : После того, как мой коллега искал "Free Monad optimize", используя американское правописание, мы нашли хороший ответ на этот вопрос, утверждая, что невозможно сделать до интерпретация.

Однако, безусловно, должна быть возможность интерпретировать программу для создания ее оптимизированной версии, а затем интерпретировать ее для получения List[A]?

1 Ответ

0 голосов
/ 29 января 2020

Мне удалось получить то, что я хочу, просто определив мою «программную» структуру в рекурсивном ADT: 

  sealed trait ListAction[A]
  case class ListPure[A](list: List[A]) extends ListAction[A]
  case class ListFilter[A](previous: ListAction[A], p: A => Boolean) extends ListAction[A]
  case class ListMap[A, B](previous: ListAction[A], f: A => B) extends ListAction[B]

  trait ListActionSyntax[A] {
    def previousAction: ListAction[A]

    def listFilter(p: A => Boolean): ListFilter[A] = ListFilter(previousAction, p)

    def listMap[B](f: A => B): ListMap[A, B] = ListMap(previousAction, f)
  }

  implicit def syntaxFromList[A](list: List[A]): ListActionSyntax[A] = {
    new ListActionSyntax[A] {
      override def previousAction: ListAction[A] = ListPure(list)
    }
  }

  implicit def syntaxFromProgram[A](existingProgram: ListAction[A]): ListActionSyntax[A] = {
    new ListActionSyntax[A] {
      override def previousAction: ListAction[A] = existingProgram
    }
  }

  def optimiseListAction[A](action: ListAction[A]): ListAction[A] = {
    def trampolinedOptimise[A](action: ListAction[A]): Eval[ListAction[A]] = {
      action match {

        case ListFilter(ListFilter(previous, p1), p2) =>
          Eval.later {
            ListFilter(previous, { e: A => p1(e) && p2(e) })
          }.flatMap(trampolinedOptimise(_))

        case ListMap(ListMap(previous, f1), f2) =>
          Eval.later {
              ListMap(previous, f2 compose f1)
          }.flatMap(trampolinedOptimise(_))

        case ListFilter(previous, p) =>
          Eval.defer(trampolinedOptimise(previous)).map { optimisedPrevious =>
            ListFilter(optimisedPrevious, p)
          }

        case ListMap(previous, f) =>
          Eval.defer(trampolinedOptimise(previous)).map { optimisedPrevious =>
            ListMap(optimisedPrevious, f)
          }

        case pure: ListPure[A] => Eval.now(pure)
      }
    }

    trampolinedOptimise(action).value
  }

  def executeListAction[A](action: ListAction[A]): List[A] = {
    def trampolinedExecute[A](action: ListAction[A]): Eval[List[A]] = {
      action match {
        case ListPure(list) =>
          Eval.now(list)

        case ListMap(previous, f) =>
          Eval.defer(trampolinedExecute(previous)).map { list =>
            list.map(f)
          }

        case ListFilter(previous, p) =>
          Eval.defer(trampolinedExecute(previous)).map { list =>
            list.filter(p)
          }
      }
    }

    trampolinedExecute(action).value
  }

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

...