CODEWITHSUNDEEP
scalafunctional-programmingtail-recursion
kan
kan

Reputation: 28981

Convert Option based linked list to a `List`

What is a nicest way to implement such function

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)

I did it as

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

but it does not look simple and is not tail-recursive. Any better ideas?

Update:

In fact... I don't need to have the List specifically. I need a way to wrap the linked list as a simple List-like trait with find/take/map/etc methods. Any nice solution?

Upvotes: 0

Views: 121

Answers (2)

user
user

Reputation: 7604

Edit: What @jwvh suggested is probably the best idea. Your nodes are already like a linked list, and by creating a List[Node], you're just unnecessarily creating extra references. Full disclaimer: I shamelessly copied this from this page. This is not a perfect solution, and you may need to (heavily) modify it

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

Here's a tail recursive method, though I'm not sure it's what you want. You'll have to reverse afterwards.

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
}

You might prefer something else for simplicity, though. Tail-recursion probably doesn't matter in this case

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

Upvotes: 3

Pedro Correia Luis
Pedro Correia Luis

Reputation: 1095

Your solution is fine as it is, but if you want it tail rec you could do this:

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

Upvotes: 2

Related Questions