SHARE
TWEET

Untitled

a guest Mar 20th, 2017 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //example of 2 levels of recursion
  2.  
  3.  
  4.  def flatMapSublists[A,B](ls: List[A])(f: (List[A]) => List[B]): List[B] =
  5.     ls match {
  6.       case Nil => Nil
  7.       case sublist@(_ :: tail) => f(sublist) ::: flatMapSublists(tail)(f)
  8.     }
  9.  
  10.     def combinations[A](n: Int, ls: List[A]): List[List[A]] =
  11.     if (n == 0) List(Nil)
  12.     else flatMapSublists(ls) { sl =>
  13.       combinations(n - 1, sl.tail) map {sl.head :: _}
  14.     }
  15.  
  16.     //note val f = (s:Int) => List(Nil).map(s :: _)
  17.     equates to List(List(s))
  18.  
  19. // answer should be List(List(1,2),List(1,3),List(1,4),List(2,3),List(2,4),List(3,4))
  20. // for input of combinations(2,List(1,2,3,4))
  21.  
  22. //stage 1 - starting from inside combinations
  23.  
  24.         FM(List(1,2,3,4) { s1 => C(1, List(2,3,4) map {s1.head :: _} }
  25. //stage 2
  26.         FM(List(1,2,3,4) { s1 => FM(List(2,3,4) { s1 => C(0,List(3,4)) map {s1.head :: _}} map {s1.head :: _}}
  27. //stage 3
  28.                              
  29.         FM(List(1,2,3,4) { s1 => FM(List(2,3,4) { s1 => List(Nil) map {s1.head :: _}} map {s1.head :: _}}
  30.  //stage 4
  31.                
  32.         FM(List(1,2,3,4) { s1 => List(List(2),List(3),List(4)) map {s1.head :: _}}
  33.  
  34.  note up to stage 4 we have only expanded the inner recursion. that is starting from FM(List(1,2,3,4) { s1 =>
  35.  the result of stage 4 would be List(List(1,2),List(1,3),List(1,4)). Remember though the outer FM is also recursive as shown in stage 5      
  36.  
  37.  //stage 5
  38.  
  39.  f(List(1,2,3,4) ::: f(List(2,3,4)) ::: f(List(3,4)) ::: f(List(4))
  40.  
  41.  we have already expanded out the first term, the function (f) is inside the braces of stage 4,  the second f term of stage 5 will have
  42.  a similar pattern. its function will be
  43.  
  44.  {s1 => List(List(3),List(4)) map {s1.head :: _ }}
  45.  
  46.  this will generate the List(List(2,3), List(2,4)) terms
  47.  
  48.  similarly the third term of stage 5 f function is  {s1 => List(List(4)) map {s1.head :: _}}
  49.  
  50.  this will generate the term List(List(3,4))
  51.  
  52.  the last case f(List(4)) is as follows:
  53.    
  54. FM(List(4) { s1 => C(1,List()) map {s1.head :: _}}
  55.  
  56. ths expands to
  57.  
  58. FM(List(4) { s1 => Nil}
  59. hence this term is dropped.
  60.  
  61. must admit i think 2 levels of recursion (a function that has 2 recursive functions) seems confusing, maybe it eventually becomes as simple
  62. as a function that just calls itself (one level of recursion) once you are familiar with it ???
RAW Paste Data
Top