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

Переоткрыл очередной велосипед.
Меня всегда раздражало то, что для задания автомата приходилось что-то примерно такого вида(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 и @. это снижает его скорость к сожалению

Понравился этот дем...

иногда я действительно так делаю=)

...

Уставший, никому не нужный и держащий себя на коротком шипастом поводке...


Why I can not forgets its?