时间戳

首页 > 解决方案 > 是否可以在执行前优化 Free Monad 程序？

scala - 是否可以在执行前优化 Free Monad 程序？

问题描述

我最近使用猫学习了 Free Monad 模式，试图创建一个可以在执行前“简化”的 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]?

标签： scalascala-catsfree-monad

解决方案

通过在递归 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
  }

这样做的缺点是我不能免费获得堆栈安全性，并且必须确保我的优化和执行方法得到正确的蹦床。

推荐阅读