Решил начинать потихоньку писать код по ДС на F#. Оказалось это очень удобно и невообразимо просто, если знать что такое карринг;)
Итак, ДС состоит из двух элементов:
- Множество состояний S;
- Функция переходов(эволюции) 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; ...]
Не правда ли элементарно? ;)
