Попытка сделать генератор треугольника Серпинского в стиле функционального программирования - PullRequest
Новая
       14

Попытка сделать генератор треугольника Серпинского в стиле функционального программирования

0 голосов
/ 14 ноября 2009

У меня есть функция в Scala и та же функция в JavaScript, но я не думаю, что она в функциональном стиле. 

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);
}

Я надеюсь, что это будет итератор, а не рекурсивный, поэтому я могу продолжать получать следующую итерацию, и она будет печатать следующий уровень, поэтому моя программа сначала создает внешний треугольник, а затем рисует первый внутренний треугольник. Сделав его итератором, я мог ждать нажатия клавиши, чтобы выполнить следующую итерацию, возможно, каждый раз меняя цвета.

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

  1. Нарисуйте 3 треугольника, по одному на каждой стороне центрального треугольника
  2. Нарисуйте 9 треугольников, по одному на каждой стороне. из трех треугольников из предыдущая итерация.
  3. Нарисуйте 27 треугольников

...

UPDATE:

Извините, я забыл вопросительный знак, поэтому трудно увидеть вопрос.

По сути, я хотел бы изменить ее с рекурсивной на ту, которую я могу вызывать по требованию, и сделать так, чтобы она рисовала следующую итерацию. Как я могу это сделать?

Обновление 2:

У меня есть решение, которое работает, но я не знаю, какое решение лучше, мое или решение, которое также является ответом на этот вопрос: 

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;
}

Ответы [ 4 ]

2 голосов
/ 15 ноября 2009

Ваша функция возвращает пару. Левая половина содержит треугольники для текущей итерации. Правая половина содержит функцию, которая возвращает пару, содержащую треугольники для следующей итерации, и функцию ...

РЕДАКТИРОВАТЬ Вот как можно переписать свое решение: 

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)))
}

Я не пробовал это, но что-то очень много с этой целью даст вам поток итераций, каждая из которых представляет собой список треугольников. Чтобы нарисовать итерацию, просто вытолкните ее из потока и назовите ваш drawTriangle.

Советы по стилю: избегайте foreach. Используйте 2 или 3 пробела вместо вкладок. Используйте краткие имена, где вы можете сойти с рук, это облегчает поиск кода для структуры. Точка с запятой это ненужный шум.

1 голос
/ 14 ноября 2009

Я думаю, что код ниже точно воспроизводит ваш код. Вы создаете 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)
  }
}

Пример использования: 

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

Теперь, как ясно показывает var, это полностью не работает. Если вы хотите сделать это итеративно, но функционально, вам нужно передать «состояние» в качестве аргументов функции, аналогичной тому, что делает next: 

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)
  }
}

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

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()
1 голос
/ 14 ноября 2009

Потоки инкапсулируют ленивые вычисления потенциально неограниченных последовательностей. С ними может быть сложно работать - или, по крайней мере, удивительно, - но они соответствуют вашим требованиям. Проверьте Scaladoc, поищите блоги и поищите в архивах списков рассылки Scala множество историй о горе, которые окружают их использование, из-за отсутствия достаточного понимания того, что значит быть ленивым, а также недостатков реализации в библиотеке 2.7. ..

Извините, что был настолько расплывчатым, но хотя я использовал их один раз, я не чувствую себя достаточно квалифицированным, чтобы попытаться быть более конкретным ...

Рэндалл Шульц

0 голосов
/ 16 ноября 2009

Вот окончательный ответ, к которому я пришел, но я никогда бы не подумал о карри-функциях, кроме ответа от Апоскалиспа.

Я не знаю, должен ли я использовать Черту, чтобы улучшить это, но я думаю, что это лучший способ перебора. 

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;
}
...