9

假设我们在 Java 中有以下结构：

class List {
  // we're immutable
  final List next;
  final int value;

  public List(int value, List next) {
    this.next = next;
    this.value = value;
  }
}

Scala 内置了对不可变单链表的支持。这将是：

val l = List(1, 2, 3) // immutable

那么，是否可以在这种列表（不可变单链表）中创建一个循环。通过循环，我的意思是：

在此处输入图像描述

4

4 回答 4

11

您应该使用lazy集合来创建无限集合。你可以使用Stream：

def loopStream: Stream[Int] = {
  lazy val loop: Stream[Int] = 3 #:: 4 #:: 5 #:: 6 #:: 7 #:: 8 #:: loop
  1 #:: 2 #:: loop
}

loopStream.take(22).toList
// List(1, 2, 3, 4, 5, 6, 7, 8, 3, 4, 5, 6, 7, 8, 3, 4, 5, 6, 7, 8, 3, 4)
于 2013-08-14T10:07:09.247 回答
2

这是不可能的，只是设计使然。Scala 的列表是不可变的，您对现有列表所能做的基本上就是移除它的头部（这会产生尾部，换句话说就是一个本身不可变的列表）或添加一个元素，从而产生一个新的不可变列表。您可以获取列表的一个元素并再次添加它，但这只会创建一个更长的列表，其中两个元素是相同的实例，这不会创建循环。

您也可以有两个共享部分（或全部）尾部的列表，但您仍然无法创建循环。这仅仅是因为要创建更长的列表，您所能做的就是添加到预先存在的列表中，这意味着在列表中 head节点（按设计）是 tail节点的较旧实例。情况总是如此。由此可见，有循环将是一个矛盾。

所以简短的回答是否定的，你不能用 scala 的（不可变的）列表创建循环。

顺便说一句，为什么可以使用Streams （如senia的回答所示）而不是Lists （即使两者都是不可变的集合）是Streams 添加了一个关键因素：惰性。流节点是惰性构建的（节点基本上存储实际节点内容的拇指），这允许后面的节点引用较早的（尚未构建的）节点，从而允许循环。

于 2013-08-14T10:11:45.030 回答
0

另一种方法是使用“this”指针在构造函数完成执行之前已经存在的事实，并且作为构造函数的一部分，您可以调用作为参数传入的函数（而不是直接传入引用“下一个”节点）将“this”指针传递给该函数。该函数负责根据传入的节点值生成对下一个节点的引用。一个粗略的例子如下：

class ListNode(val value: Int, genNext: ListNode => ListNode) {
  val next = genNext(this)
}

def gen3(prev: ListNode): ListNode = new ListNode(3, any => prev)

def gen2(prev: ListNode): ListNode = new ListNode(2, gen3 _)

val loopingList = new ListNode(1, gen2 _) // will have 1 -> 2 -> 3 -> (back to) 2

当然，如果您没有对何时调用此构造函数进行足够的控制，那么各种垃圾都可能作为 genNext 函数传入......

于 2013-08-14T12:53:08.980 回答
0

如前所述，如果没有某种惰性，就无法创建不可变的循环结构。但是，您可以利用 scalaz 的Name。它有几个实现，其中Need提供了延迟评估的值。next这允许我们定义一个可以延迟的链表：

import scalaz._
import scalaz.Scalaz._

final case class LList[T](value: T, next: Name[LList[T]])
  extends Traversable[T]
{
  @annotation.tailrec
  override def foreach[U](f: T => U) {
    f(value);
    next.value.foreach(f);
  }
}

这允许我们定义函数，例如cycle，使用 推迟对最后一个循环引用的评估Need。所有其他引用都不需要是惰性的，所以我们只是将它们包装起来Value（这不会延迟任何东西）。

object LList {
  def cycle[T](xs: T*): LList[T] = {
    lazy val r: LList[T] =
      xs.foldRight[Name[LList[T]]](Need(r))(
        (x, r) => Value(LList(x,r))
      ).value;
    r;
  }
}
于 2013-08-14T13:05:02.853 回答