Napisałem poniższy program w SML, aby wygenerować drzewo fraktalne na stronę internetową (jestem dumny z tego dumny 😅). Użyłem funkcji rekurencyjnej, ponieważ nie ma dla pętli w SML.

val width = 1000.0;
val height = 1000.0;
val length = 350.0;
val scale = 1.0 / 1.618;
val header = "<!DOCTYPE html><html><body><svg width='1000' height='1000' version='1.1' xmlns='http://www.w3.org/2000/svg'> \n";
val footer = "</svg></body></html>";
val outfile = TextIO.openOut "fractal-tree.html";

fun tree(x, y, length, angle) =
    if length > 1.0 then (
        let
            val x2 = x + length * (Math.cos angle)
            val y2 = y + length * (Math.sin angle)
            val outString = "<line x1='" ^ Real.toString x ^ "'"
            ^ " y1='" ^ Real.toString y ^ "'"
            ^ " x2='" ^ Real.toString x2 ^ "'"
            ^ " y2='" ^ Real.toString y2 ^ "'"
            ^ " style='stroke:dodgerblue;stroke-width:2'/> \n"
        in
            TextIO.output(outfile, outString);
            tree(x2, y2, length * scale, angle + Math.pi / 2.5);
            tree(x2, y2, length * scale, angle - Math.pi / 2.5)
        end
    )else ();
    
    
TextIO.output(outfile, header);
tree(width / 2.0, height, length, 3.0 * Math.pi / 2.0);
TextIO.output(outfile, footer);
TextIO.closeOut outfile;

Teraz chciałbym pomocy na części kodu, który należy zmienić, aby obrócić tę funkcję do funkcji iteracyjnej.

Jest to tylko drugorzędne, ale chciałbym wiedzieć, czy istnieje sposób na wyświetlenie mojego drzewa w konsoli. Kiedy próbuję, otrzymuję tylko sekwencję liczb rzeczywistych, a następnie zatrzymuje się program.

1
IndifineGenome 27 październik 2020, 02:16

1 odpowiedź

Najlepsza odpowiedź

Wspaniała robota!

Chciałbym pomocić na części kodu, który należy zmienić, aby obrócić tę funkcję do funkcji iteracyjnej.

Identyfikuję trzy części swojego kodu:

  1. Część generuje ciąg SVG
  2. Część, która współdziała z plikami
  3. Część, która wywołuje się rekurencyjnie

Oddzieliłbym te części, abyś mógł je skomponować jakikolwiek sposób, który lubisz, nie w zależności od drugiego. Na przykład, że możesz skomponować efekty fraktali bez konieczności komponowania efektów systemu plików.

Jeśli chodzi o iteracji vs. Recursion, ponieważ jesteś w języku funkcjonalnym, polecam kontynuowanie rekurencji. Ale ponieważ twój rekurencyjny wzór jest w kształcie drzewa (każde połączenie potencjalnie tworzy dwa inne połączenia), ryzyko rekurencji przepełnionej pamięci sterty.

Tak więc rozwiązanie iteracyjne rozwiązanie i roztwór Recursive osiągnąłoby to samo: Odkąd powtarzasz zarówno w lewo, jak i prawej, ale nie w tym samym czasie, możesz wyraźnie raczej niż domyślnie sklep, używając stosu, To też ponownie wracasz do drugiego.


Oto przepisanie; Komentarz poniżej:

datatype Line = Line of { x1 : real, y1 : real, x2 : real, y2 : real }
datatype Seed = Seed of { x : real, y : real, length : real, angle : real }

val scale = 1.0 / 1.618
val initialAngle = 3.0 * Math.pi / 2.0

fun makeLine (Seed { x = x1, y = y1, length = length, angle = angle }) =
    let
      val x2 = x1 + length * (Math.cos angle)
      val y2 = y1 + length * (Math.sin angle)
    in
      Line { x1 = x1, y1 = y1, x2 = x2, y2 = y2 }
    end

fun makeSplits (Line line) (Seed seed) =
    let
      val newx = #x2 line
      val newy = #y2 line
      val newlen = #length seed * scale
      val left = Seed { x = newx, y = newy, length = newlen, angle = (#angle seed) + Math.pi / 2.5 }
      val right = Seed { x = newx, y = newy, length = newlen, angle = (#angle seed) - Math.pi / 2.5 }
    in
      [ left, right ]
    end

fun isBelowThreshold (Seed { length = derp, ... }) =
    derp < 1.0

fun makeLines seeds =
    let
      fun go [] lines = lines
        | go (seed :: stack) lines =
          if isBelowThreshold seed
          then go stack lines
          else let
            val line = makeLine seed
            val splits = makeSplits line seed
          in
            go (splits @ stack) (line :: lines)
          end
    in
      go seeds []
    end

val toStr = Real.toString

fun drawLine (Line { x1 = x1, y1 = y1, x2 = x2, y2 = y2 }) =
    String.concat
      [ "<line x1='", toStr x1, "'"
      , " y1='", toStr y1, "'"
      , " x2='", toStr x2, "'"
      , " y2='", toStr y2, "'"
      , " style='stroke:dodgerblue;stroke-width:2'/>\n"
      ]

fun drawLines lines =
    String.concat (List.map drawLine lines)

fun drawFractal width height length =
    let
      val header = String.concat
        [ "<!DOCTYPE html><html><body>"
        , "<svg width='", toStr width, "'"
        , " height='", toStr height, "'"
        , " version='1.1' xmlns='http://www.w3.org/2000/svg'>\n"
        ]
      val initialSeed = Seed {
            x = width / 2.0,
            y = height,
            length = length,
            angle = initialAngle
          }
      val lines = makeLines [ initialSeed ]
      val footer = "</svg></body></html>"
    in
      String.concat [ header, drawLines lines, footer ]
    end

fun writeToFile path s =
    let val fd = TextIO.openOut path
    in TextIO.output (fd, s)
     ; TextIO.closeOut fd
    end

Tak więc typy danych Line i {{X1} Korzystanie z jednego z tych aliasów:

type Line = { x1 : real, y1 : real, x2 : real, y2 : real }
type Seed = real * real * real * real

Ale punkty są (1), aby wyrazić linie i punkty początkowe w celu rekurencji jako coś abstrakcyjnego, który nie ma nic wspólnego z SVGS lub operacji systemów plików, i (2), aby odróżnić jedną 4-krotkę od drugiego przez nazewnictwo.

Miła rzecz o owijaniu ich w datatype To sprawia, że różnica między

val makeLines = fn : (real * real * real * real) list -> (real * real * real * real) list
val makeLines = fn : Seed list -> Line list

Jestem pewien, że istnieje jeszcze prostsze podejście, w którym kąt w Seed jest wywnioskowany z Line, ale z moim ograniczonym, mechanicznym zrozumieniem fraktali, przynajmniej mam dwie nazwy dla "części wyniku" (Line) i "część rekurencji" (Seed).

Jeśli chodzi o rekurencję, twoja funkcja tree jest nazwana makeLines, a do osiągnięcia odzyskiwania ogona, wykonany jest funkcja wewnętrzna go. Nazywany seed :: stack). Każdy seed generuje jeden line i niektóre nowe nasiona; Które te są przeniesione do makeSplits, tylko aby wyjaśnić, że go głównie robi rekursję.

Niezależnie od tego, czy makeLines (lub twój {x1}}) kończy się dla wszystkich wejść zależy od niektórych rozumowania geometrycznego. Nie będąc matematykiem, to nie jest tak pocieszające. Ale przynajmniej, jeśli popełnisz błąd, w tym momencie program zabraknie pamięci i nie wypełnia harddisk z fraktalami. :-RE

Pomysły na poprawę:

  • Chciałbym zobaczyć wersję tego drzewa, który ma losowo dwa lub trzy gałęzie. Dotyczy to wezwania do generatora liczb pseudo-losowej w makeSplits i wygeneruj bieżące dwa dzielenia lub trzy podziały o innym kątem.
  • Możesz rozpocząć fraktal w centrum i podzielić go 3-, 4-, 5 sposobów lub 6 sposobów, aby zrobić płatek śniegu. Ale wydaje się, że z obecną konstelacją niektóre z nich wymagają mniejszych długości początkowej, aby uniknąć nakładania się.
  • Oddziały mogą lekko zamuścić swój kolor na podstawie rodzica.
2
Simon Shine 27 październik 2020, 21:57