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