пятница, 29 января 2010, Yuriy Bogomolov

Итак, я продолжаю цикл статей по F#. В этой статье я познакомлю читателей с базовым синтаксисом языка F# и сделаю сравнение быстродействия F# и C# на примере вычисления детерминанта матрицы произвольного размера. В связи с большими текстами примеров и комментариями к ним я решил разбить первую статью на несколько частей, первый из которых я представляю вашему вниманию.

Элементы базового синтаксиса, необходимые для понимание текста примера
0. Использование так называемого «легкого синтаксиса», который гораздо человечнее стандартного:

#light

1. Подключение пространств имен:

open System 
open Microsoft.FSharp.Core

2. Объявление функций:

let sayHello name = printfn "Hello, %A" name

Тут name — параметр (аргумент) функции, имеющей имя sayHello. Функция printfn является аналогом Console.WriteLine() (который, кстати, тоже доступен), также есть функция printf — она эквивалентна Console.Write().
3. Соспоставление именной метки с результатом вычислений (aka «тут нет переменных»):

let x = 1 //пускай имени «х» соответствует числовое значение 1 
let x = x +1 //пускай имени х соответствует значение «х+1». При этом иксы слева и справа — разные! 
let z = sum x y //результат вычислений какой-то функции

4. Сопоставление с образцом (аналог switch):

let myFun x = 
    match x with 
    | 1 -> printfn "You entered 1" 
    | 2 -> printfn "You entered 2" 
    | _ -> printfn "You printed other digit"

Символ «_» можно читать «не важно, какое значение». Под него подпадают все варианты вводимых данных. Поскольку сопоставление с образцом идет свер-ху вниз, то сопоставление с _ производят в самом конце.
5. Циклы:
В процедурном стиле:

for i = 0 to 10 do 
    printf "%i " i

Вывод: 0 1 2 3 4 5 6 7 8 9 10
С использованием диапазонного генератора:

for i in 0..10 do 
    printf "%i " i

Вывод: 0 1 2 3 4 5 6 7 8 9 10
Еще пример:

for i in 0..2..10 do 
    printf "%i " i

Вывод: 0 2 4 6 8 10
То есть в диапазоне можно неявно указать шаг прироста путем задания диа-пазона в виде a1,a2..an.
6. Потоковая (конвейерная) обработка:

let x = [1..10] |> List.sum |> printfn "%i"

Весьма интересный и полезный оператор |> — он сначала вычисляет значение слева от себя и передает его в качестве аргумента функции справа от себя. Данный пример является несколько надуманным, но в реальном про-граммировании |> используется довольно часто, так как упрощает понимание и повышает читабельность кода. По сути, оператор |> является синтаксиче-ским сахаром.
7. Приведение типов:
Осуществляется вызовом конструктора определенного типа:

let x = int64(123456)

8. Работа с массивами:
Создание:

let a = Array2D.create 2 3 4 //двухмерный массив 2х3, заполненный числом 4

Получение размерностей:

printfn "%i" Array2D.length1 a //выведет 2 
printfn "%i" Array2D.length2 a //выведет 3

9. Обработка исключительных ситуаций:

try 
    doSomeStuff myWrongBalue 
with 
MyException e -> printf "%A" e

Тут MyException — это исключение, описанное пользователем в таком виде:

exception MyException of string //описывается вне тела функции

Пример: вычисление детерминанта матрицы
Код примера с небольшими комментариями:

#light 

open System 
open System.IO 
open System.Collections.Generic 

exception ZeroSizeException of string //наше собственное исключение 

//Простая вспомогательная функция с обработкой ошибок 
let rec GetInt (message:string) =  
    Console.Write(message) 
    try 
        int(Console.ReadLine()) 
    with 
    | _ as e -> 
        Console.WriteLine("Not an integer value, try again") 
        GetInt message 

//Транспонирование матрицы, написанное в императивном стиле 
let transpose (mtx : int [,]) = 
    array2D [ for i in 0..((Array2D.length2 mtx)-1) do 
                yield 
                    [for j in 0..((Array2D.length1 mtx)-1) do 
                        yield mtx.[j, i]]] 

//Удаление из массива определенной строки 
let cut (list:int[,]) index =  
    match index with 
    | index when index >= Array2D.length1 list -> list 
    | index when index < 0 -> list 
    | _ -> array2D [ for i in 0..((Array2D.length1 list)-1) do 
                      if i <> index then  
                            yield [for j in 0..((Array2D.length2 list)-1) do 
                                    yield list.[i,j]]] 

//Вычисление минора матрицы 
let minor (matrix:int[,]) rejX rejY =  
    cut (cut matrix rejX  
         |> transpose) rejY  
    |> transpose 

//Собственно, сам детерминант. 
//Пришлось написать его с учетом возможного выхода за границы Int32.MaxValue. 
let rec determinant (matrix:int[,]) = 
    match Array2D.length1 matrix with 
    | 0 -> ZeroSizeException "Determinant: 0-by-0 matrix error" |> raise 
    | 1 -> int64(matrix.[0,0]) 
    | _ -> (seq {for j in 0..((Array2D.length2 matrix)-1) do  
                            yield (int64(Math.Pow(-1.0, float (j+1)))  
                                    * int64(matrix.[0,j])  
                                    * determinant (minor matrix 0 j))})  
                            |> Seq.sum 

//Функция-оболочка, выполняющая подготовительную работу 
let testDeterminant n =  
    let rnd = Random(Environment.TickCount) 
    let matrix = Array2D.create n n 0 //создаем матрицы n*n, заполненную нулями 
    Console.WriteLine("Matrix:") 
    for i = 0 to n - 1 do 
        for j = 0 to n - 1 do 
            matrix.[i,j] <- rnd.Next(100) 
            Console.Write("{0,3}", matrix.[i,j]) 
        Console.WriteLine() 
    try 
        let det = determinant matrix 
        Console.WriteLine("Determinant is: {0}", det) 
    with  
        ZeroSizeException e -> Console.WriteLine(e) 

[<EntryPoint>] 
let main(args) =  
    let timer = System.Diagnostics.Stopwatch() 
    let n = GetInt "Please, enter size of square matrix: " 
    timer.Start() 
    testDeterminant n 
    timer.Stop() 
    Console.WriteLine("Determinant calculations took {0} ticks", timer.ElapsedTicks) 
    0

Примечания:
1. Формула вычисления детерминанта взята с Википедии.
2. В программе используется обработка исключительных ситуаций.
3. Работа оператора yield совпадает с таковой в C#.

Теперь пару комментариев по поводу собственно процесса написания про-граммы. Наиболее разительное отличие — приходится думать по-другому.

Во-первых, после C# сложно отучить себя думать в классических терминах цик-лов и переменных. В частности, то же вычисление минора первым порывом было желание написать в духе:

for (int i=0; i<n; i++) 
{ 
    for (int j=0; j<n; j++) 
    { 
        if (i != restricted) 
            do copy stuff... 
    } 
}

Вместо этого я сел, подумал «а как это можно сделать в терминах работы над всей матрицей как единым целым?» и пришел к результату выше, который я считаю вполне изящным.
То же самое и с функцией вычисления детерминанта — ее тоже можно было написать с применением какого-то аккумулятора и т.д. Но если вы действи-тельно хотите освоить функциональный стиль программирования, надо в первую очередь менять стиль вашего мышления.

И напоследок — неожиданная ложка дёгтя в бочку мёда с названием «F#» — сравнение скорости идентичных программ на F# и C#.
F#:
Please, enter size of square matrix: 6
Matrix:
74 96 21 11 52 92
87 83 87 66 96 76
6 7 40 59 23 82
65 65 7 89 33 66
93 31 10 58 62 42
70 90 38 64 24 46
Determinant is: 77878506078
Determinant calculations took 261668 ticks

C#:
Please, enter size of square matrix: 6
Matrix:
2 84 42 26 66 13
99 81 86 84 41 76
76 81 77 52 89 46
38 46 80 42 40 9
80 12 75 77 35 30
38 61 67 2 48 25
Determinant is: -4449512536
Determinant calculations took 22737 ticks

Код на C# с алгоритмической точки зрения был полной копией кода на F#. Если кого заинтересует — код в приложениях.
Впереди — более интересные примеры. Следите за обновлениями! :)

---