Trying to make sierpinski triangle generator in a functional programming style

Question

I have a function in Scala, and the same function in JavaScript, but I don't think it is in a functional style.

def drawSurroundingTriangles(startx : Double, starty : Double, width : Double) {
 var newwidth = width/2;
 var newstartx = startx + newwidth / 2;
 var newstarty = starty - newwidth;
 drawTriangle(newstartx, newstarty, newwidth);
 drawTriangle(newstartx - newwidth, starty + newwidth, newwidth);
 drawTriangle(newstartx + newwidth, starty + newwidth, newwidth);
 if(newwidth < 6)
  return;
 drawSurroundingTriangles(newstartx, newstarty, newwidth);
 drawSurroundingTriangles(newstartx - newwidth, starty + newwidth, newwidth);
 drawSurroundingTriangles(newstartx + newwidth, starty + newwidth, newwidth);
}

My hope is to have this be an iterator, rather than having it be recursive, so I can keep getting the next iteration, and it would print the next level, so my program initially creates the outer triangle, then draws the first inner triangle. By making it an iterator I could wait for a key press to do the next iteration, perhaps changing colors each time.

After that, it gets to this function, where it will loop, so on each iteration:

1. Draw 3 triangles, one on each side of the central triangle
2. Draw 9 triangles, one on each side of the three triangles from the previous iteration.
3. Draw 27 triangles

...

UPDATE:

Sorry, I forgot a question mark, so it is hard to see the question.

Basically, I would like to change it from a recursive function to one that I can call on demand, and have it draw the next iteration. How can I do that?

Update 2:

I have a solution that works, but I don't know which solution is better, mine or the one that is also an answer in this question:

def drawSurroundingTriangles(indexlist : List[(Double, Double, Double)]) : List[(Double, Double, Double)] = {
 var mylist = ListBuffer[(Double, Double, Double)]()
 indexlist.foreach{ 
  case (startx, starty, width) => { mylist ++ drawSingleTriangle(startx, starty, width) } }

 mylist.toList;
}

def drawSingleTriangle(startx : Double, starty : Double, width : Double) : List[(Double, Double, Double)] = {
 val newwidth = width/2;
 val newstartx = startx + newwidth / 2;
 val newstarty = starty - newwidth;
 var list = List((newstartx, newstarty, newwidth),
   ((newstartx - newwidth, starty + newwidth, newwidth)),
   (newstartx + newwidth, starty + newwidth, newwidth));
 list.foreach{ case (nstartx, nstarty, nwidth) => drawTriangle(nstartx, nstarty, nwidth)}
 list;
}

Answer 1

Streams encapsulate lazy computations of potentially unbounded sequences. They can be tricky to work with—or surprising, at least—but do fit your requirements. Check the Scaladoc, look for blogs and search the Scala mailing list archives for the many stories of woe that surround their use in the absence of sufficient understanding of what it means for them to be lazy, as well as implementation defficiencies in the 2.7 library...

Sorry to be so vague, but while I've used them once, I don't feel qualified to try to be more specific...

Randall Schulz

Answer 2

I think the code below faithfully reproduces your code. You create an Iterator, and then just loop like any other iterator.

case class Triangle(startx: Double, starty: Double, width: Double)

class drawSurroundingTrianglesIterator(original: Triangle) extends Iterator[Unit] {
  private case class Iteration(old: Triangle, `new`: Triangle)
  private var iteration = List(newIteration(original))

  def hasNext = ! iteration.isEmpty
  def next = {
    iteration = iteration flatMap variants map newIteration
    iteration map (_.old) foreach draw
    iteration = iteration filter (_.`new`.width > 5)
  }

  private def newIteration(triangle: Triangle) = {
    import triangle._
    Iteration(triangle, Triangle(startx + width / 4, starty - width / 2, width / 2))
  }

  private def variants(iteration: Iteration) = {
    import iteration._
    import `new`._
    List(Triangle(startx, starty, width),
         Triangle(startx - width, old.starty + width, width),
         Triangle(startx + width, old.starty + width, width))
  }

  private def draw(triangle: Triangle) = {
    import triangle._
    drawTriangle(startx, starty, width)
  }
}

Usage example:

scala> new drawSurroundingTrianglesIterator(Triangle(100, 100, 40))
res1: drawSurroundingTrianglesIterator = non-empty iterator

scala> res1 foreach (x => x)
Drawing 110,000000, 80,000000, 20,000000
Drawing 90,000000, 120,000000, 20,000000
Drawing 130,000000, 120,000000, 20,000000
Drawing 115,000000, 70,000000, 10,000000
Drawing 105,000000, 90,000000, 10,000000
Drawing 125,000000, 90,000000, 10,000000
Drawing 95,000000, 110,000000, 10,000000
Drawing 85,000000, 130,000000, 10,000000
Drawing 105,000000, 130,000000, 10,000000
Drawing 135,000000, 110,000000, 10,000000
Drawing 125,000000, 130,000000, 10,000000
Drawing 145,000000, 130,000000, 10,000000

Now, as the var in it clearly shows, this is completely non-functional. If you want to do it iteratively but functionally, you need to pass the "state" as arguments to a function similar to what next is doing:

case class Triangle(startx: Double, starty: Double, width: Double)
case class Iteration(old: Triangle, `new`: Triangle)

object TriangleIterator {
  def iterate(from: List[Iteration]) = {
    val iteration = from flatMap variants map newIteration
    iteration map (_.old) foreach draw
    iteration filter (_.`new`.width > 5)
  }

  def newIteration(triangle: Triangle) = {
    import triangle._
    Iteration(triangle, Triangle(startx + width / 4, starty - width / 2, width / 2))
  }

  private def variants(iteration: Iteration) = {
    import iteration._
    import `new`._
    List(Triangle(startx, starty, width),
         Triangle(startx - width, old.starty + width, width),
         Triangle(startx + width, old.starty + width, width))
  }

  private def draw(triangle: Triangle) = {
    import triangle._
    drawTriangle(startx, starty, width)
  }
}

In this case I made newIteration public so you can produce the first one. Here is an usage example:

scala> List(TriangleIterator.newIteration(Triangle(100, 100, 50)))
res0: List[Iteration] = List(Iteration(Triangle(100.0,100.0,50.0),Triangle(112.5,75.0,25.0)))

scala> TriangleIterator.iterate(res0)
Drawing 112,500000, 75,000000, 25,000000
Drawing 87,500000, 125,000000, 25,000000
Drawing 137,500000, 125,000000, 25,000000
res1: List[Iteration] = List(Iteration(Triangle(112.5,75.0,25.0),Triangle(118.75,62.5,12.5)), Iteration(Triangle(87.5,12
5.0,25.0),Triangle(93.75,112.5,12.5)), Iteration(Triangle(137.5,125.0,25.0),Triangle(143.75,112.5,12.5)))

scala> TriangleIterator.iterate(res1)
Drawing 118,750000, 62,500000, 12,500000
Drawing 106,250000, 87,500000, 12,500000
Drawing 131,250000, 87,500000, 12,500000
Drawing 93,750000, 112,500000, 12,500000
Drawing 81,250000, 137,500000, 12,500000
Drawing 106,250000, 137,500000, 12,500000
Drawing 143,750000, 112,500000, 12,500000
Drawing 131,250000, 137,500000, 12,500000
Drawing 156,250000, 137,500000, 12,500000
res2: List[Iteration] = List(Iteration(Triangle(118.75,62.5,12.5),Triangle(121.875,56.25,6.25)), Iteration(Triangle(106.
25,87.5,12.5),Triangle(109.375,81.25,6.25)), Iteration(Triangle(131.25,87.5,12.5),Triangle(134.375,81.25,6.25)), Iterati
on(Triangle(93.75,112.5,12.5),Triangle(96.875,106.25,6.25)), Iteration(Triangle(81.25,137.5,12.5),Triangle(84.375,131.25
,6.25)), Iteration(Triangle(106.25,137.5,12.5),Triangle(109.375,131.25,6.25)), Iteration(Triangle(143.75,112.5,12.5),Tri
angle(146.875,106.25,6.25)), Iteration(Triangle(131.25,137.5,12.5),Triangle(134.375,131.25,6.25)), Iteration(Triangle(15
6.25,137.5,12.5),Triangle(159.375,131.25,6.25)))

scala> TriangleIterator.iterate(res2)
Drawing 121,875000, 56,250000, 6,250000
Drawing 115,625000, 68,750000, 6,250000
Drawing 128,125000, 68,750000, 6,250000
Drawing 109,375000, 81,250000, 6,250000
Drawing 103,125000, 93,750000, 6,250000
Drawing 115,625000, 93,750000, 6,250000
Drawing 134,375000, 81,250000, 6,250000
Drawing 128,125000, 93,750000, 6,250000
Drawing 140,625000, 93,750000, 6,250000
Drawing 96,875000, 106,250000, 6,250000
Drawing 90,625000, 118,750000, 6,250000
Drawing 103,125000, 118,750000, 6,250000
Drawing 84,375000, 131,250000, 6,250000
Drawing 78,125000, 143,750000, 6,250000
Drawing 90,625000, 143,750000, 6,250000
Drawing 109,375000, 131,250000, 6,250000
Drawing 103,125000, 143,750000, 6,250000
Drawing 115,625000, 143,750000, 6,250000
Drawing 146,875000, 106,250000, 6,250000
Drawing 140,625000, 118,750000, 6,250000
Drawing 153,125000, 118,750000, 6,250000
Drawing 134,375000, 131,250000, 6,250000
Drawing 128,125000, 143,750000, 6,250000
Drawing 140,625000, 143,750000, 6,250000
Drawing 159,375000, 131,250000, 6,250000
Drawing 153,125000, 143,750000, 6,250000
Drawing 165,625000, 143,750000, 6,250000
res3: List[Iteration] = List()

Answer 3

Have your function return a pair. The left half contains the triangles for the current iteration. The right half contains a function that returns a pair containing the triangles for the next iteration and a function...

EDIT Here's how you might rewrite your solution:

type Triangle = (Double, Double, Double)

def fractal(width : Double): Stream[List[Triangle]] = {
  val w2 = width / 2
  def surrounding(t: Triangle) = match t case (startx, starty, width) => {
    val w = width/2
    val x = startx + w / 2
    val y = starty - w
    List((x, y, w),
         (x - w, starty + w, w),
         (x + w, starty + w, w))
  }
  def s(tris: List[Triangle]): Stream[List[Triangle]] =
    Stream.cons(tris, s(tris.flatMap(surrounding(_))))
  s(List((w2/2, w2, w2)))
}

I've not tried this out, but something very much to this effect will give you a stream of iterations, each iteration being a list of triangles. To draw an iteration, just pop it off the stream and call your drawTriangle on it.

Style tips: Avoid foreach. Use 2 or 3 spaces instead of tabs. Use terse names where you can get away with it, it makes code easier to scan for structure. The semicolon is unnecessary noise.

Answer 4

Here is the final answer I came to, but I would never had thought of curried functions except for the answer from Aposcalisp.

I don't know if I should use a Trait in order to make this better, but I think this is the best way to iterate through.

def drawFractal(width : Double) {
 val mywidth = width / 2;
 val drawSurroundingTriangles = drawSurroundingTrianglesComplete((startx, starty, width) => {
     val newwidth = width/2;
     val newstartx = startx + newwidth / 2;
     val newstarty = starty - newwidth;
     var list = List((newstartx, newstarty, newwidth),
       ((newstartx - newwidth, starty + newwidth, newwidth)),
       (newstartx + newwidth, starty + newwidth, newwidth));
     list.foreach{ case (nstartx, nstarty, nwidth) => drawTriangle(nstartx, nstarty, nwidth)}
     list;
 })_

 var mylist = drawSurroundingTriangles(List((mywidth/2, mywidth, mywidth)));
 mylist.foreach{ case (startx, starty, width) => print ("[" + startx + "," + starty + "," + width + "]\n")}
 print("\n");
 mylist = drawSurroundingTriangles(mylist);
 mylist.foreach{ case (startx, starty, width) => print ("[" + startx + "," + starty + "," + width + "]\n")}
}
def drawSurroundingTrianglesComplete(myfunc : (Double, Double, Double) => List[(Double, Double, Double)])
(indexlist : List[(Double, Double, Double)]) : 
 List[(Double, Double, Double)] = {
 var mylist = ListBuffer[(Double, Double, Double)]()
 indexlist.foreach{ 
  case (startx, starty, width) => { mylist ++= myfunc(startx, starty, width) } }
 mylist.toList;
}