Динамические системы в 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

и ещё...

ИТАК Я ДУМАЮ В ВАШЕЙ ДУШЕ....... ТУМАН

В вашей душе клубится туман, укрывая серым пологом вашу душу... http://aeterna.ru/test.php?link=tests:108172 ВЫ ОЧЕНЬ ПОХОЖИ НА ... ПОСЕЙДОНА А ДОРОГУ ТЕБЕ ОСВЕЩАЛО… ОСЕННЕЕ УТРЕННЕЕ СОЛНЦЕ Осеннее утреннее солнце каждый день наполняет мир яркими, выразительными красками. Ты не терпишь бледности, вялости невыразительности. Ты признаешь яркие краски и сильные чувства. С тобою можно поделиться горестями и печалями, ведь ты всегда видишь корень проблемы и находишь решение, кладущие всем тревогам и сомнениям конец. Ты по натуре – взыскательный, добивающийся во всем, совершенства человек, для которого важно решить проблему до конца, чтобы перевернуть новую страницу жизни http://aeterna.ru/test.php?link=tests:106205

новая порция результато тестов с Аэтерны...

СКОРО ВЫ ВЕРНЕТЕСЬ В РЕАЛЬНОСТЬ, НО ПЕРЕД ЭТИМ Я СКАЖУ ВАМ, ЧТО ВАШ ИДЕАЛЬНЫЙ ПОЦЕЛУЙ - ПОЦЕЛУЙ С ЛЮБИМЫМ ЧЕЛОВЕКОМ.

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

http://aeterna.ru/test.php?link=tests:71971

ВАША ДЕВУШКА С ТЕМНОЙ СТОРОНЫ: ВЕДЬМА

Она владеет тайными знаниями, умеет многое, и кажется нет того, чего она не может. Но нет, есть: она не может забыть Вас.

http://aeterna.ru/test.php?link=tests:59143

ПОЗДРАВЛЯЮ!!!! ВЫ - СКОРЕЕ РЕАЛИСТ!

Вы умеете смотреть на вещи реально. Если вдруг загорится автобус, в котором вы едете, вы не растеряетесь, не впадете как все в панику, а начнете действовать осознанно. Вы спасете всех из этого горящего автобуса. У вас много друзей, они любят вас за прямолинейность, искренность. Вы способны любить и ваша половинка будет счастлива с вами. Вы добрый и поможете в трудную минуту. Вы- золотая середина! http://aeterna.ru/test.php?link=tests:58479 МНЕ КАЖЕТСЯ, ВЫ НЕОБЫЧНЫЙ ЧЕЛОВЕК... Сегодня – улыбающийся оптимист, завтра – пессимист в глубокой депрессии, неординарны и творчески, избегаете стереотипов, Вам нравится все новое и необычное; вполне возможно, интересуетесь мистикой и другими явлениями, которые у других людей пока что не получается объяснить. http://aeterna.ru/test.php?link=tests:110316

к сожалению...

мде... кажется "Печальный рыцарь", как меня как то назвали, возвращается...

ну что ж, пережил один раз, переживу и второй.

да поможет мне зелёный чай.

Love-Hate-Sex-Pain

Ненавижу память

Помнить - это проклятье.