2

一个带有 flatMap/map 的简单类，它什么都不做，只是懒惰地存储一个值：

[注 1：这个类可以替换为任何带有 flatMap/map 的类。选项只是一个具体的例子，这个问题是关于一般情况的]

[注2：scalaz 是一个有趣的库，但这个问题与它无关。如果除了我在下面发布的内容之外没有 std scala 库解决方案，那是可以接受的。]

class C[A](value : => A) {
   def flatMap[B](f: A => C[B]) : C[B] = { f(value) }
   def map[B](f: A => B) : C[B] = { new C(f(value)) }
   override def toString = s"C($value)"
}
object C {
   def apply[A](value : => A) = new C[A](value)
}

一个迭代地将 flatMap 应用于其成员的函数：

def invert[A](xs: Traversable[C[A]], acc: List[A] = Nil) : C[List[A]] =
  if(xs.nonEmpty) {
    xs.head flatMap { a => invert(xs.tail, a :: acc) }
  } else {
    C(acc.reverse)
  }

实际作用：

scala> val l = List(C(1),C(2),C(3))
l: List[C[Int]] = List(C(1), C(2), C(3))

scala> invert(l)
res4: C[List[Int]] = C(List(1, 2, 3))

有没有办法习惯性地重写“反转”？此外，是否有一个功能性“动词”可以捕捉我在这里所做的事情？

4

2 回答 2

1

您的解决方案的问题在于它会给大型列表带来堆栈溢出，因为它是完全（不仅仅是尾）递归的。我会折叠：

def invert[A](xs: Traversable[C[A]]) =
  (C(List[A]()) /: xs){ (c,x) => c.flatMap(l => x.map(_ :: l)) }.map(_.reverse)
于 2013-02-19T15:49:37.560 回答
0

您可能会invert使用模式匹配更清楚一点，但它本质上是相同的代码：

xs match {
  case x0 :: xMore => x0.flatMap(a => invert(xMore, a :: acc))
  case Nil => C(acc.reverse)
}
于 2013-02-19T15:31:22.143 回答