HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Building a Tree from Breadcrumbs

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
frombreadcrumbsbuildingtree

Problem

I need to transform

List("home", "mens", "clothing", "jackets")


into

List(
  "/home",
  "/home/mens",
  "/home/mens/clothing",
  "/home/mens/clothing/jackets"
)


This is what I have so far:

val nodes = Array("home", "mens", "clothing", "jackets")
val (rootNode, otherNodes) = nodes.splitAt(1)
val tree = otherNodes.foldLeft(rootNode) { (list, token) =>
    list :+ (list.last + "/" + token)
}


What do you think? any obvious problems?

Solution

It looks like you need a variation of the prefix sum algorithm applied to your list. In Scala this can be accomplished with scan:

val xs = List("home", "mens", "clothing", "jackets")
xs.scan("")(_ + "/" + _).tail

Code Snippets

val xs = List("home", "mens", "clothing", "jackets")
xs.scan("")(_ + "/" + _).tail

Context

StackExchange Code Review Q#123031, answer score: 3

Revisions (0)

No revisions yet.