Как стать автором
Обновить

Влюбляемся в F#: Доза 2: Строим фрактальное изображение, или множество Мандельброта своими руками

Время на прочтение 3 мин
Количество просмотров 5.7K

На прошлом уроке мы рассмотрели основные понятия функционального программирования, теперь давайте попробуем применить их на практике. Поскольку функциональное программирование, как вы наверное поняли, идеально подходит для решения математических задач, то рассмотрим именно такую задачу — построение изображения множества Мандельброта, самого известного фрактального множества.



image


Математически, множество Мандельброта определяется следующим образом. Рассмотрим последовательность комплексных чисел z(n+1) = z(n)^2+c, z(0)=0. Для различных c эта последовательность либо сходится, либо расходится Например, для c=0 z(i) = 0, а для c=2 имеем расходящуюся последовательность. Так вот, множество Мандельброта — это множество тех c, для которых последовательность сходится.


Переходим к реализации алгоритма на F#. Для начала, определим исходную функцию



let mandelf (c:Complex) (z:Complex) = z*z+c;;


Здесь нам пришлось в явном виде указать тип Complex (это надо сделать хотя бы для одной из переменных, но мы для симметрии сделали для двух), поскольку по умолчанию для операции + полагается целый тип. Для того, чтобы тип Complex стал доступен, в начале придется указать преамбулу:



open Microsoft.FSharp.Math;;
open System;


Чтобы проверить сходимость, мы примем небольшое допущение. Будем считать, что последователность сходится, если |z(20)|<1. Для вычисления z(20) используем следующую функцию многократной композиции, рекурсивно применяющую указанную функцию заданное число раз:



let rec rpt n f =
    if n=0 then (fun x->x)
    else f >> (rpt (n-1) f);;

Здесь знак >> обозначает композицию функций, а запись fun x->x — тождественную функцию. Вообще говоря, конструкция fun x -> ... позволяет нам задать функциональную константу, т.е. выражение типа функции от одного аргумента. Например, следующие две конструкции — эквивалентны:



let double x = x*2
let double = fun x -> x*2

В нашем случае функция rpt принимает один аргумент целого типа n (число повторений), и некоторую функцию f, т.е. имеет тип rpt: int -> ('a -> 'a) -> ('a -> 'a). Для n=0 возвращается тождественная функция, а для n>0 — композиция f и (n-1)-кратного применения f. Запись 'a означает полиморфный тип, т.е. вместо него может быть любой допустимый тип данных.


Возврящаясь к нашей задаче, вспомним, что для фиксированного c частичное применение каррированной функции (mandelf c) будет функцией одного аргумента (x), и применим к этой функции функцию многократной композиции. В результате, |z(20)| вычислится как rpt 20 (mandelf c) (Complex.zero). Действительно, rpt 20 (mandelf c) будет обозначать
20-кратное применение функции mandelf с, которое затем мы применяем к 0. Тогда функция принадлежности комплексного числа к множеству Мандельброта запишется как


let ismandel c = Complex.Abs(rpt 20 (mandelf c) (Complex.zero))<1.0;;

Остальное — дело техники. Определяем функцию масштабирования scale (она будет в качестве аргументов брать пары чисел — диапазоны изменения переменных типа float*float и
int*int), и в двойном цикле печатаем множество на консоли:



let scale (x:float,y:float) (u,v) n = float(n-u)/float(v-u)*(y-x)+x;;
for i = 1 to 60 do
 for j = 1 to 60 do
   let lscale = scale (-1.2,1.2) (1,60) in
   let t = complex (lscale j) (lscale i) in 
   System.Console.Write(if ismandel t then "*" else " ");
 System.Console.WriteLine("")
;;

Но это ещё не всё! Вспомним, что программисту на F# доступна вся мощь платформы Microsoft.NET! Поэтому мы можем построить графическое изображение в окне, используя
Windows Forms и библиотеку System.Drawing! Соответствующий код:



#light
open System.Drawing
open System.Windows.Forms

let form =
   let image = new Bitmap(400, 400)
   let lscale = scale (-1.2,1.2) (0,image.Height-1)
   for i = 0 to (image.Height-1) do
     for j = 0 to (image.Width-1) do
       let t = complex (lscale i) (lscale j) in
       image.SetPixel(i,j,if ismandel t then Color.Black else Color.White)
   let temp = new Form()
   temp.Paint.Add(fun e -> e.Graphics.DrawImage(image, 0, 0))
   temp

[<STAThread>]
do Application.Run(form);;

Что из этого получилось — см. на картинке ниже:


image


Конечно, для получения полноценного цветного изображения множества Мандельброта на F# надо ещё немного поработать! Предоставляю моим читателям сделать это в качестве
упражнения. Если получится — пишите в комментариях!

Теги:
Хабы:
+28
Комментарии 18
Комментарии Комментарии 18

Публикации

Истории

Ближайшие события

Московский туристический хакатон
Дата 23 марта – 7 апреля
Место
Москва Онлайн
Геймтон «DatsEdenSpace» от DatsTeam
Дата 5 – 6 апреля
Время 17:00 – 20:00
Место
Онлайн