Scala tail recursion пересекается между 2 списками

Question

Я довольно новичок в scala и программировании вообще (просто для удовольствия), и я пытаюсь понять хвостовую рекурсию и коллекции, но отладка действительно сложна.

Я 2 списка:

val quoters = List[Map[String,List[String]]] 

val quoted = List[Map[String,List[String]]] 

например:

val quoters = List(Map("author1"->List("1","7","8")),Map("author2"->List("2","4","6","3")),Map("author3"->List("5","2","1","3"))) 
val quoted = List(Map("author1"->List("5","6")),Map("author2"->List("5","8","1")),Map("author3"->List("4"))) 

"quoters" цитата "цитирует" и "цитировали" также цитируют "quoters".

В примере:

author1 quoted author2 with "1" and "8", 
author2 quoted author3 with "4", 
author3 quoted author1 with "5" & author2 with "5" + "1" 

Я хочу найти круги «quoters», что цитата «цитирует», что цитата «quoters» ...

выход должен быть что-то вроде :

val quotesCircle = List(
Map("quoter"->"author1","receiver"->"author2","quote"->"4"), 
Map("quoter"->"author2","receiver"->"author3","quote"->"2"), 
Map("quoter"->"author3","receiver"->"author1","quote"->"1") 
) 

Мои проблемы:

1/Я думаю, что я злоупотребляя коллекции (это, кажется, слишком много JSon как ...)

2/я могу получить пересечение только с Список списков с:

def getintersect(q1:List[List[String]],q2:List[List[String]])={ 
for(x<-q1;r<-q2; if (x intersect r) != Nil)yield x intersect r 
} 

, но не с структура списка карт.

3/Я попытался это для рекурсии, но это не работает, потому что ... ну я не знаю:

def getintersect(q1:List[List[String]],q2:List[List[String]])= { 
    def getQuotedFromIntersect(quoteMatching:List[String],quoted:List[List[String]]):List[List[String]]={ 
    for(x<-q1;r<-q2; if (x intersect r) != Nil) 
     getQuotedFromIntersect(x intersect r,quoted) 
    } 
} 

Я надеюсь, что я достаточно ясно:/

Спасибо заранее !

Felix

Answer 1

Я думаю, что у вас есть один дополнительный слой в ваших структурах данных. И я бы, вероятно, использовать имя «авторов» вместо «цитирует», чтобы избежать путаницы из-за созвучия между Quoter/цитируемого:

val quoters = List(
    Map("author1"->List("1","7","8")), 
    Map("author2"->List("2","4","6","3")), 
    Map("author3"->List("5","2","1","3"))) 

val authors = Map(
    "author1" -> List(5, 6), 
    "author2" -> List(5, 8, 1), 
    "author3" -> List(4)) 

С этим на месте, и небольшой функции, как это:

def findQuoters(article: Int): List[String] = { 
    quoters.keys.toList filter { name => 
    quoters(name) contains article 
    } 
} 

Вы можете начать экспериментировать с различными способами сбора и представления, который цитируемым автором которой и где, например:

// For each name in the 'authors' map: 
// For each article authored by this name: 
//  Find all quoters of this article 
//  Report that author 'name' has been quoted for article 'id' by 'whom'... 

for (name <- authors.keys) { 
    for (article <- authors(name)) { 
    val qq = findQuoters(article) 
    println("author %s has been quoted %d times for article %d by %s".format(
     name, qq.size, article, qq.mkString(" "))) 
    } 
} 

, который печатает такой вывод:

author author1 has been quoted 1 times for article 5 by author3 
author author1 has been quoted 1 times for article 6 by author2 
author author2 has been quoted 1 times for article 5 by author3 
author author2 has been quoted 1 times for article 8 by author1 
author author2 has been quoted 2 times for article 1 by author1 author3 
author author3 has been quoted 1 times for article 4 by author2 

Теперь подумайте немного о том, что вы сопоставляете с этими ассоциативными массивами. Вы можете эффективно построить матрицу смежности графа. Как бы вы могли найти все круги в ориентированном графе?