Вернулся из спячки

Что-то я давно ничего не писал. Буду исправляться.

За последнее время я слегка разочаровался в F# и находился в неком поиске себя и тех инструментов, которые мне было бы интересно изучить и использовать.

Наверно стоит сказать пару слов почему я отказался от F#.

• Плохой компилятор. В общем то всё хорошо, но дьявол кроется в мелочах. И одна из этих мелочей -  rec. Нет, он честно раскрывается в цикл, когда может, вот только когда функция чуть побольше пары строк, то уследить за тем, чтобы все рекурсивные вызовы были правильно сделаны не всегда получается. Ну и следовательно приходится ловить StackOverflow exception в рантайме. Не весело в общем.
• Синтаксис. Да он кажется красивым, но это ровно до того момента, пока ты не пишешь чего-либо больше сотни строк (и не вылизываешь их по пол дня). А чем больше кода, тем стремительнее он пытается превратиться в кашу. Из этого следуют две следующие проблемы.
• Выразительность кода на F# иногда может сыграть с программистом в довольно плохую шутку. Выразительность усложняет код, т.е. вносить правку в F# код значительно сложнее, чем в C/C++/C#/python код. Не потому, что сложнее написать пару символов, а потому что приходится дольше вникать в кусок кода, чтобы понять, где нужно поправить.
• Синтаксис F# сложен, при этом в компиляторе есть косяки и не все заявленные в том же MSDN фичи работают + проблемы с автовыводом типов (приходится иногда ручками прописывать, либо изменять код на аналогичный, но для которого типы выводятся). Это заставляется писать более "грязный" код.

В общем и целом я отношусь к F# положительно, но пока буду ждать, как будут развиваться компилятор и среда разработки под него. 

Ах да, на НГ игрался с Mailbox + ZMQ, получилось забавно, хотя пришлось дополнительно использовать стандартные Thread для запуска ZMQ сокетов, т.к. Mailbox довольно мутно рулит потоками и, по умолчанию, должен использовать однопоточную обработку сообщений.

В любом случае сейчас я с .Net и C#/F# не работаю. Пересел на Java + Clojure и раскуриваю Gephi и gephi-toolkit, хотя качество документации к ним не фонтан. Первые пробы Clojure оказались довольно неплохи. Важным оказалось то, что после F# я смог быстро адаптироваться к recur. Что же, попробую заставить себя перевести https://github.com/gephi/gephi-toolkit-demos на Clojure, главное чтобы запала хватило :)

Тестирование библиотек F# в Visual Studio

Когда создаётся новый проект F# Library, то в довесок в *.fs файлу идёт Srcipt.fsx. И в этот скрипт логично бы запилить функционал теста работы библиотеки, причём хорошо бы прогонять этот тест автоматически.

Оказывается это возможно и делается довольно легко и просто.

Итак, по по пунктам:

1. ПКМ на Script.fsx -> Properties -> Copy to Output Directory выставить в Copy Always. Это необходимо для того, чтобы исходный файл скрипта автоматически копировался при сборке в целевую директорию сборки.

2. Идёт в Project -> MyProjectName Properties -> Build Events. Нас интересует Post-build event command line. Прописываем там: fsi Script.fsx. Так же можно выставить по вкусу параметр Run the post-build events.

3. Добавляем в Script.fsx что-то вроде: printfn "Hello, World!", жмём F6 и переходим вкладку Output Visual Studio(View -> Output или Ctrl-W O) и видим примерно следующее:

Build started: Project: MyMathLib, Configuration: Debug Any CPU MyMathLib -> K:\common_projects\MyMathLib\MyMathLib\bin\Debug\MyMathLib.dll
fsi test.fsx
Hello, World!
Build: 1 succeeded or up-to-date, 0 failed, 0 skipped

Для того, чтобы прилинковать либу в скрипте используйте следующую инструкцию:
#r @"MyLibraryName.dll"

Генератор функций являющихся автоматами

Переоткрыл очередной велосипед.
Меня всегда раздражало то, что для задания автомата приходилось что-то примерно такого вида(mutable можно и на ref заменить, не суть важно):

type Aut(state: 'S) =
  let mutable st = state
  
  member this.Next(x: 'A): 'B =
    ...
    st <- ...
    result

т.е. делать отдельный класс под каждый автомат или класс обёртку. Мне хотелось чего-нибудь более элегантного и удобного, а именно - представления автомата функцией. Вот, сегодня накидал следующее:

let rec create (f: 'S -> 'I -> 'O) (g: 'S -> 'I -> 'S) (state: 'S) =
    let st = ref state
 
    fun (x: 'I) ->
      let r = f !st x
      st := g !st x
      r

т.е. передаём функции создателю 3 параметра: функцию выходов, функцию переходов и начальное состояние. Если передать 2 параметра, то, за счёт карирования получим не инициальный автомат, а если 3(или нач. стостояние в карированную ф-цию) - инициальный автомат.

Ну и пример работы:

let adder = 
  create 
    (fun s x -> 
      match s with
        | 0 -> x+1
        | 1 -> x
        | _ -> s+x
      ) 
    (fun s x -> (s+1) % 10) 0

printfn "%A" [
    for i in 0..20 ->
      adder 1
  ]

результат:

[2; 1; 3; 4; 5; 6; 7; 8; 9; 10; 2; 1; 3; 4; 5; 6; 7; 8; 9; 10; 2]

Композиция функций и странные баги

Начал потихоньку вникать в теорию комбинаторов и решил попробовать их реализовать на F#.

Но наткнулся на один странный баг, который не смог воспроизвести дома. А именно, есть комбинатор функций a, b:

let (|>>) a b =
    fun x -> a x |> b

Так вот, используя интерпритатор F# из плагина к VS2008 я не мог построить комбинацию скажем таких функций:

let f1 x = x + 1
let f2 x = x.ToString()

Интерпритатор ругался и просил явно прописать типы.

хотя для

let f1 x = x + 1
let f2 x = x * x

или

let f2 x = (float) x + 1.0
 

комбинатор работал.

А вот дома, в VS2010 всё заработало в точности так, как и ожидалось.


Следующий код:

let (|>>) a b =
    fun x -> a x |> b
 
let f1 x = x + 1
let f2 x = (float) x + 1.0
let f3 x = [x]
 
let f' = f1 |>> f2 |>> f3
 
f' 10

выдал:

val ( |>> ) : ('a -> 'b) -> ('b -> 'c) -> 'a -> 'c
val f1 : int -> int
val f2 : int -> float
val f3 : 'a -> 'a list
val f' : (int -> float list)

> f' 10;;
val it : float list = [12.0] 

т.е. возможно есть какие-то проблемы с комбинаторами в старых версиях F#.

Но точно посмотреть версию F# на работе смогу только после НГ...

Всех с наступающим!)) 

F# Snippets

Бродя по интернету в поисках инфы про quotations наткнулся у Томаса Петричека на следующую ссылку: http://fssnip.net/

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

Скорость вычислений на F#

Недавно задумался над скоростью вычислений в F#, а вернее о том, стоит ли заморачиваться использую lazy() и seq. Поверхностные тесты seq показывают, что seq лучше для вычислений чем list:



> Seq.sum (seq{ for i in 1.0 .. 50.0 -> 1.0/(i*i*i) });;
Real: 00:00:00.001, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it : float = 1.201860863
> List.sum [ for i in 1.0 .. 50.0 -> 1.0/(i*i*i) ];;
Real: 00:00:00.002, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it : float = 1.201860863
> ;;
> ;;
> ;;
> Seq.sum (seq{ for i in 1.0 .. 50000.0 -> 1.0/(i*i*i) });;
Real: 00:00:00.008, CPU: 00:00:00.015, GC gen0: 0, gen1: 0, gen2: 0
val it : float = 1.202056903
> List.sum [ for i in 1.0 .. 50000.0 -> 1.0/(i*i*i) ];;
Real: 00:00:00.013, CPU: 00:00:00.015, GC gen0: 1, gen1: 0, gen2: 0
val it : float = 1.202056903
> List.sum [ for i in 1.0 .. 5000000.0 -> 1.0/(i*i*i) ];;
Real: 00:00:02.589, CPU: 00:00:02.870, GC gen0: 38, gen1: 26, gen2: 3
val it : float = 1.202056903
> Seq.sum (seq{ for i in 1.0 .. 5000000.0 -> 1.0/(i*i*i) });;
Real: 00:00:00.800, CPU: 00:00:00.795, GC gen0: 0, gen1: 0, gen2: 0
val it : float = 1.202056903

Причём чем больше эл-тов требуется вычислить, тем менее производительней становиться список, т.к. ему требуется подчищать за собой память оч. активно.


п.с. если использовать честный fold, то seq несколько замедляется, но всёравно в 2 раза быстрее списка:

> Seq.fold (fun acc e -> acc + e) 0.0 (seq{ for i in 1.0 .. 5000000.0 -> 1.0/(i*i*i) });;
Real: 00:00:01.125, CPU: 00:00:01.092, GC gen0: 0, gen1: 0, gen2: 0
val it : float = 1.202056903
> List.fold (fun acc e -> acc + e) 0.0 ([ for i in 1.0 .. 5000000.0 -> 1.0/(i*i*i) ]);;
Real: 00:00:02.716, CPU: 00:00:02.776, GC gen0: 35, gen1: 28, gen2: 1
val it : float = 1.202056903

правда стоит заметить, что для seq использование fold увеличило требуемое время на 0.3 сек, в то время когда для списка всего на 0.127 сек

Ну разве этот код не красив?...

/// L1 ⊕k L2 = {w | (w = xy, x ∈ L1, y ∈ L2, |xy| 6 k) ∨ (w = γ, xy = γβ, x ∈ L1, y ∈ L2, |γ| = k)}.
let plus k (L1 : List) (L2 : List) =
    List.fold (fun (acc : list) (x : string) ->
        (List.map (fun (y : string) -> 
                if (x.Length + y.Length) < k 
                    then x + y
                    else (x + y).Substring(0, k)
                ) L2 
            ) @ acc
        ) [] L1

хотя мне не нравится то, как пришлось использовать fold и @. это снижает его скорость к сожалению

Upd. Паттерн матчинг

В догонку к предыдущему сообщению.

let find = function
    | "by" :: "name" :: _ :: []  -> 3
    | "by" :: "autor" :: _ :: [] -> 4
    | "by" :: "autors" :: _ :: [] -> 5
    | _ -> 0

и 

let find = function
    | "by" :: "name" :: t when t <> [] -> 3
    | "by" :: "autor" :: t when t <> [] -> 4
    | "by" :: "autors" :: t when t <> [] -> 5
    | _ -> 0
Так вот, 2й вариант значительно хуже! Он развернётся аж в две функции, каждая из которых будет сложнее того, во что развернётся 1й варинт(листинги приводить не буду - всё это можно увидеть в рефлекторе).

Паттерн матчинг и выделение памяти

Есть небольшой и довольно простой код:

let replace = function
    | "by" :: "id" :: t :: [] -> 8
    | _ -> 0

t :: [] - используется для того, чтобы гарантировать наличие одного свободного эл-та в списке.

И вроде бы всё хорошо, но если посмотреть в рефлекторе, то можно увидеть такую картину:

 
public static int replace(FSharpList<string> _arg1)
{
    if (_arg1.get_TailOrNull() != null)
    {
        FSharpList<string> list = _arg1;
        if (string.Equals(list.get_HeadOrDefault(), "by") 
&& (list.get_TailOrNull().get_TailOrNull() != null))
        {
            FSharpList<string> list2 = list.get_TailOrNull();
            if (string.Equals(list2.get_HeadOrDefault(), "id") 
&& (list2.get_TailOrNull().get_TailOrNull() != null))
            {
                FSharpList<string> list3 = list2.get_TailOrNull();
                if (list3.get_TailOrNull().get_TailOrNull() == null)
                {
                    string t = list3.get_HeadOrDefault();
                    return 8;
                }
            }
        }
    }
    return 0;
}

Выделенная строка намекает на то, что выделяется память под ту же ссылку(а это лишняя работа).

Но, если использовать _ вместо t, то всё становится несколько радужней:

 
public static int replace(FSharpList<string> _arg1)
{
    if (_arg1.get_TailOrNull() != null)
    {
        FSharpList<string> list = _arg1;
        if (string.Equals(list.get_HeadOrDefault(), "by") 
&& (list.get_TailOrNull().get_TailOrNull() != null))
        {
            FSharpList<string> list2 = list.get_TailOrNull();
            if ((string.Equals(list2.get_HeadOrDefault(), "id") 
&& (list2.get_TailOrNull().get_TailOrNull() != null)) 
&& (list2.get_TailOrNull().get_TailOrNull().get_TailOrNull() == null))
            {
                return 8;
            }
        }
    }
    return 0;
}


Как можно заметить код становится значительно проще(пропадает один вложенный иф + не выделяется память под t + не вычисляется list3).

Отсюда нехитрый вывод - следует, по возможности, использовать запись вида h :: _ :: t вместо h :: elem :: t.

mutable привязки, интерпретатор и массивы

Есть такой код:

let mutable x =

    [|
     1; 2; 3; 4; 5;
     2; 3; 5; 6; 3;
     |]
 
let to_null =
    for i in 0..9 do

        x.[i] <- 0
загоняем его в интерпретатор и получаем соотв.:

val mutable x : int [] = [|0; 0; 0; 0; 0; 0; 0; 0; 0; 0|]
val to_null : unit = ()


Всё правильно, всё логично.

А теперь снова засунем в интерпретатор x:
val mutable x : int [] = [|1; 2; 3; 4; 5; 2; 3; 5; 6; 3|]

и вызовет to_null:

> to_null;;
val it : unit = ()
> x;;
val it : int [] = [|1; 2; 3; 4; 5; 2; 3; 5; 6; 3|]


Поэтому следует быть осторожным при работе с mutable привязками в интерпретаторе и, по крайней мере, перезагружать их при каждой загрузке кода в fsi.

Динамические системы в F# - задание, динамика

Решил начинать потихоньку писать код по ДС на F#. Оказалось это очень удобно и невообразимо просто, если знать что такое карринг;)

Итак, ДС состоит из двух элементов:

1. Множество состояний S;
2. Функция переходов(эволюции) f : S -> S.

очевидным образом можно примерно получить описание такого объекта на F#:

Set<'a> * ('a -> 'a),

т.е. это кортеж из множества и функции.

Ну с множеством всё понятно - это встроенный тип в F#, а вот с функцией не всё так гладко, т.к. не хочется каждый раз писать новую функцию для каждой ДС вручную.

Но, т.к. я рассматриваю КДС, выясняется, что любую функцию можно задать множеством пар вида (a,b), где a, b принадлежат S, а это можно представить как list<'a * 'a>.

Реализовал я это так:

let rec evo_function table a =

        match table with

            | h :: t ->

                if (fst h) = a then snd h else evo_function t a

            | _ -> failwith("dynamic error: invalid state")

Соответственно использоваться это будет следующим образом:

let ds1 = (Set[0;1], evo_function [(0,1);(1,0)])

т.е. создавая ДС я каррирую evo_function таблицей переходов функции и получаю нужную мне ДС.

Остаётся решить вопрос с созданием удобного способа динамики ДС. Но и эта проблема решается с помощью карринга легко и просто! Смотрите сами:

let evolution ds = Seq.unfold (fun state -> Some(state, state |> snd ds))

Элементарная функция создающая последовательность на основе псевдо-рекурсивных вызовов каррированной evo_function у ds. Плюс ко всему используя последовательность, как результат прогона динамики ДС я получаю выйгрыш в производительности за счёт того, что для последовательностей используются ленивые вычисления в F# :)

Вот полный пример инициализации ДС и получения для неё двух последовательных динамик:

> let ds1 = (Set[0;1], evo_function [(0,1);(1,0)]);;

val ds1 : Set * (int -> int) = (set [0; 1], )

> let evo_ds1 = evolution ds1;;

val evo_ds1 : (int -> seq)

> evo_ds1 1;;
val it : seq = seq [1; 0; 1; 0; ...]
> evo_ds1 0;;
val it : seq = seq [0; 1; 0; 1; ...]

Удаление бесплодных и недостижимых символов из КС-грамматики

Не далее как сегодня утром я таки дошёл с флешкой и таки сдал эти задачки:)

Привожу тут код этих алгоритмов:

N, E - Set - мн-ва не\терминальных символов
P - Set> - мн-во правил грамматики

// функция построения Ni для DelSterileChar
    let rec del_char (N' : Set) : Set = 
        let Ni : Set = 
            Set.map (fun (a, b) -> 
                        if List.forall (fun e -> N'.Contains(e) || E.Contains(e)) b  
                            then a 
                            else "") P
            |> Set.filter (fun k -> k <> "")
        if Ni = N' then Ni
                   else del_char <| Set.union Ni N'
 
    // функци построения Ni для DelUnattChar
    let rec del_un_char (N' : Set) : Set =
        let Ni = Set.filter (fun (a, b) -> N'.Contains(a)) P
                 |> Set.fold (fun acc (a, b) -> b @ acc) []
                 |> Set.ofList
                 |> Set.union N'
        if Ni = N' then Ni
                   else del_un_char Ni
    
    // алгоритм удаления бесподных символов
    member x.DelSterileChar() : unit =
        N <- del_char <| Set []
        P <- Set.filter (fun (a, b) -> 
                            N.Contains(a) && 
                            List.forall (fun e -> N.Contains(e) || E.Contains(e)) b) P
                                
    // алгоритм удаление недостижимых символов
    member x.DelUnattChar() : unit =
        let Ni = del_un_char <| Set [S]
        N <- Set.intersect N Ni
        E <- Set.intersect E Ni
        P <- Set.filter (fun (a, b) -> Ni.Contains(a) &&
                                       List.forall (fun e -> Ni.Contains(e)) b) P

"Кости" в консоли на F#

небольшая "игрушка" написанная на F# с применением ООП...
написанная правда фигово с точки зрения того же ООП:)

смысл - посмотреть, как юзаются классы с F#)

module BoneGame

open System
open System.Collections.Generic

#light

type UserInterface () =
    member x.Roll : bool =
        printfn "Вы будете бросать кубик?"
        x.QuestYN

    member x.PrintState (data : list) : unit = 
        for e in data do
            printfn "%s" <| e

    member x.QuestYN : bool =
        printf "Ваше решениие(Y или N): "
        match Console.ReadLine() with
            | "Y" | "y" -> true
            | "N" | "n" -> false
            | _ -> x.QuestYN 

    member x.Win : unit =
        printfn "Поздравляем, Вы выйграли!!!"
        Console.ReadKey () |> ignore

    member x.Louse (name : string) : unit =
        printfn "Вы проиграли! Выйграл %s." name
        Console.ReadKey () |> ignore

    member x.GeneratePlayerList : list =
        printf "Введите имя игрока: "
        let name = Console.ReadLine()
        printfn "Будут ещё игроки?"
        if x.QuestYN then name :: x.GeneratePlayerList
        else [name]

type Player (name   : string,
             score  : int,
             UI     : UserInterface) =
    let name    = name
    let ui      = UI
    let mutable score = score

    member x.Name   with get () = name
    member x.UI     with get () = ui
    member x.Score  with get () = score and set v = score <- v + score

    member x.Roll : bool = ui.Roll

type Game () =
    let intrf = UserInterface ()
    let mutable Players = new Queue ()

    do 
        let p_name = intrf.GeneratePlayerList
        for e in p_name do
            Players.Enqueue ( new Player (e, 0, intrf))

    let max_score = 100

    let bone_roll = (new Random (int(DateTime.Now.Ticks))).Next(1, 6)

    member x.Start : unit =
        let mutable end_flag = true
        while end_flag do
            // выбираем игрока, чья очередь бросать кости
            let current_player = Players.Dequeue ()
            let mutable sum = 0
            let mutable flag = true

            Console.Clear () // !!!!!!!!!!!!!!
            // выводим данные о игровой ситуации
            current_player.UI.PrintState ["Бросает " + current_player.Name;
                                          "Очков у игрока: " + current_player.Score.ToString ();
                                          "--------------------";]
            for e in Players do
                current_player.UI.PrintState ["Противник " + e.Name;
                                              "Очков " + e.Score.ToString ()]
            current_player.UI.PrintState ["--------------------"]

            Console.ReadKey () |> ignore
            Console.Clear ()

            // бросок игрока
            current_player.UI.PrintState ["Будете бросать?"]
            while flag && current_player.Roll do
                let r = (new Random (int(DateTime.Now.Ticks))).Next(1, 6)
                current_player.UI.PrintState ["Вы выбросили " + r.ToString () + " очков"]
                if r <> 1 then 
                    sum <- sum + r
                    current_player.UI.PrintState ["За ход вы набрали " + sum.ToString () + " очков"]
                else 
                    flag <- false
                    sum  <- 0
                    current_player.UI.PrintState ["К сожалению ваши очки, набранные за ход обнуляются"]
                    Console.ReadKey () |> ignore
            current_player.Score <- sum

            // обрабатываем результаты броска
            if current_player.Score < max_score then
                Players.Enqueue (current_player)    // продолжаем игру
            else
                current_player.UI.Win |> ignore
                for e in Players do
                    e.UI.Louse |> ignore
                end_flag <- false

[]
let main _ = 
    printfn "Приветствуем вас в игре Кости!"

    let G = new Game ()
    G.Start
    Console.ReadKey() |> ignore
    0

Циклы на F#

Сейчас попытался реализовать довольно тривиальный цикл, который на C++ выглядел бы следующим образом:

while(true)
{
    string buf = "";
    cout << "write string(Y/N): ";
    cin >> buf;
    if(buf == "Y") return true;
    if(buf == "N") return false;
}

довольно тривиальная весчь, заставляющая ввести либо Y, либо N.
но вот на F# возникли некоторые проблемы(предположительно из-за того, что ключевое слово return можно не использовать и юзался #light)

т.е. написать в лоб:

while true do
  printf "write string(Y/N): "
  let Sol = Console.ReadLine()
  if Sol = "Y" then true
  if Sol = "N" then false

не получается, т.к. компилятор начинал ругаться на то, что возвращаемое выражение имеет неправильный тип...

в итоге это было решено следующим образом(в ФП стиле кстати, в императивном стиле я решения не нашёл удовлетворительного(два match и лишняя переменная не в счёт)):

type ... =
  ...
  member x.entr = 
        printfn "Enter your solution(Y/N): "
        match Console.ReadLine() with
            | "Y" -> true
            | "N" -> false
            | _ -> x.entr
  ...
  interface ... with
    member x.roll (flag : bool, data : IRollData) = 
            intrf.print data.DataList
            if flag = true then x.entr
            else false

хотя не думаю, что это лучший выход... скорее всего я как-то не так понял работу цикла while-do

F#, первое знакомство

F# - это функциональный язык разработанный в M$ под платформу .Net, близкий родственник Haskell.

Первые ощущения от языка - странно.
Оч. похоже на Haskell и Python на первый взгляд. Сразу бросается в глаза использование отступов для различения блоков кода, но это есть гуд кстати(есть и в питоне и в хаскеле).
Потом... функцию main можно определить следующим образом:
let main ( _ ) =
    ...
ну или более стандартно(если аргументы имеют для нас значение):
let main ( args : string[] ) =
    ...

_ - явное использование паттерн матчинга(ура, классная весч), в хаскеле оч. часто ей пользуешься)
= - опять аналогия с хаскель...

это всё хорошо, мне нравится...
но вот много строчные комментарии вида (* много\nтысч\nбукаф *) убивают... хочется стандартных, для C#, /* **/ с автопереносом и автодобавлением звёздочек...

а да, чуть не забыл... вместо привычного main, как точки входа в программу, можно использовать к примеру MaIInbl...
ибо дело в том, что точка входа опр. с помощью добавления перед функцией [%EntryPoint%]*
, которая будет точкой входа.

*вместо [% следует ставить [<, а вместо %] - >]