• Sign Up
• Login
• API
• FAQ
• Tools
• Trends
• Archive
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