将基于选项的链表转换为“列表”

Question

实现这种功能的最佳方式是什么

case class Node(prev: Option[Node])

def flatIt(n: Node): List[Node] = ???

val n1 = Node(None)
val n2 = Node(Some(n1))
val n3 = Node(Some(n2))

flatIt(n3) shouldBe List(n3, n2, n1)

我是这样做的

def flatIt(n: Node): List[Node] = n :: (n.prev match {
  case None => Nil
  case Some(prev) => flatIt(prev)
})

但是看起来不简单，也不是尾递归。有更好的想法吗？

更新：

事实上...我不需要特别List。我需要一种使用 find/take/map/etc 方法将链表包装为类似列表的简单特征的方法。有什么好的解决方案吗？

Answer 1

你的解决方案就这样很好，但如果你想要尾部记录，你可以这样做：

def flatIt(n: Node): List[Node] = {
    @tailrec
    def acc(n: Node, list: List[Node]): List[Node] = {
      n.prev match {
        case Some(node) => acc(node, list :+ n)
        case None       => list :+ n
      }
    }
    acc(n, Nil)
  }

Answer 2

编辑：@jwvh 的建议可能是最好的主意。您的节点已经像一个链表，通过创建 List[Node]，您只是在不必要地创建额外的引用。 完全免责声明：我无耻地从 this page 复制了这个。这不是一个完美的解决方案，您可能需要（大量）修改它

case class Node(prev: Option[Node])
    extends Iterable[Node]
    with IterableOps[Node, Iterable, Iterable[Node]]
    with IterableFactoryDefaults[Node, Iterable]
    with StrictOptimizedIterableOps[Node, Iterable, Iterable[Node]] {
  def iterator: Iterator[Node] = new NodeIterator(this)
}

class NodeIterator(n: Node) extends Iterator[Node] {
  private var curr: Node = n

  def hasNext: Boolean = curr.prev != None
  def next() = {
    val n = curr
    curr = curr.prev.get
    n
  }
}

这是一个尾递归方法，但我不确定它是否是您想要的。之后你就得倒车了。

def flatIt(n: Node): List[Node] = {
  @annotation.tailrec
  def flat(o: Option[Node], curr: List[Node]): List[Node] = o match {
    case None    => curr
    case Some(n) => flat(n.prev, n :: curr)
  }
  flat(Some(n), Nil).reverse
}

不过，为了简单起见，您可能更喜欢其他东西。在这种情况下，尾递归可能无关紧要

def flatIt(n: Node): List[Node] = n :: n.prev.map(flatIt).getOrElse(Nil)

or

def flatIt(n: Node): List[Node] = List.unfold(Option(n))(_.map(x => (x, x.prev)))

将基于选项的链表转换为“列表”

Convert Option based linked list to a `List`

functional-programming

scala

tail-recursion