CODEWITHSUNDEEP
javaalgorithmscalalinked-list
Vladimir Kostyukov
Vladimir Kostyukov

Reputation: 2552

Is it possible to make a cycle in an immutable linked list?

Suppose that we have the following structure in 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 has built-in support for immutable singly-linked list. It would be:

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

So, is it possible to make a cycle in this kind of lists (immutable singly-linked list). By cycle, I mean the following:

enter image description here

Upvotes: 9

Views: 898

Answers (4)

Petr
Petr

Reputation: 63389

As already mentioned, you can't create an immutable, cyclic structure without some kind of laziness. However, you can take an advantage of scalaz's Name. It has several implementations, of which Need provides lazily evaluated values. This allows us to define a linked list whose next can be deferred:

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);
  }
}

This allows us to define functions like cycle, which defer the evaluation of the last cyclic reference using Need. All the other references don't need to be lazy, so we just wrap them in Value (which doesn't defer anything).

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;
  }
}

Upvotes: 0

Shadowlands
Shadowlands

Reputation: 15074

Another way to do this is to use the fact that the 'this' pointer already exists before the constructor has finished executing, and as part of the constructor you can call a function that was passed in as a parameter (instead of passing in the direct reference to the 'next' node) passing the 'this' pointer to that function. The function is responsible for generating the reference to the next node, based possibly on the passed-in node value. A rough example is as follows:

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

Of course, if you don't put in place enough control over when this constructor gets called then all sorts of rubbish could be passed in as the genNext function...

Upvotes: 0

Régis Jean-Gilles
Régis Jean-Gilles

Reputation: 32719

It is not possible, simply by design. Scala's list is immutable, and all you can do to an existing list is basically remove its head (which yields the tail, in other words a list that is itself immutable) or prepend an element, yielding a new immutable list. You can take an element of a list and prepend it again, but this will just create a longer list where two elements are the same instance, this does not create a cycle.

You could also have two lists that share part (or all) of their tails, but you still cannot create loops. This is simply because to create a longer list, all you can do is prepend to a preexisting list, which means that in a list head nodes are (by design) older instances that tail nodes. This is always the case. From this it follows that having loops would be a contradiction.

So the short answer is no, you cannot create cycles with scala's (immutable) list.

AS an aside, the reason why it is possible with Streams (as shown by senia's answer) and not with Lists (even though both are immutable collections) is that Streams add a critical ingredient: lazyness. Stream nodes are constructed lazily (a node basically stores a thumb to the actual node's content), which allows a later node to reference an earlier (and not yet constrcuted) node, thus allowing loops.

Upvotes: 2

senia
senia

Reputation: 38045

You should use lazy collection to create infinite collection. You could use 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)

Upvotes: 11

Related Questions