2015-05-15 22 views
8

Esiste un'alternativa per il costrutto F # "seq" in Erlang? Ad esempio, in F # posso scrivere un O (1) Memoria integrare funzioneAlternativa di Erlang alla sequenza f #

let integrate x1 x2 dx f = 
    let N = int (abs (x2-x1)/dx) 
    let sum = seq { for i in 0..N do yield dx*f(x1 + dx * (double i)) } 
       |> Seq.sum 
    if x2>x1 then sum else -sum 

In Erlang, ho un'implementazione che utilizza elenchi, e quindi ha O (n) requisito di memoria che è inaccettabile per tale funzione semplice ,

create(Dx, N)->[0| create(Dx, N,[])]. 

create(Dx, 0, Init)->Init; 
create(Dx, N, Init)->create(Dx,N-1, [Dx*N |Init]). 

integral(X1,X2,Dx, F) -> 
    N=trunc((X2-X1)/Dx), 
    Points = create(Dx,N),  
    Vals = lists:map(fun(X)->F(X)*Dx end, Points), 
    lists:sum(Vals). 

risposta

6

Disclaimer: quanto segue è stato scritto sotto ipotesi che Erlang non ammette la mutazione completamente, di cui non sono sicuro, perché non conosco abbastanza bene l'Erlang.

Seq è basato su mutazione interna. Mantiene lo "stato attuale" e lo muta su ogni iterazione. In questo modo, quando esegui una iterazione, ottieni il "valore successivo", ma ottieni anche un effetto collaterale, ovvero lo stato interno dell'enumeratore è cambiato e quando esegui l'iterazione successiva, otterrai un "valore successivo" diverso , e così via. Questo di solito è ben coperto da comprensioni funzionali, ma se dovessi lavorare direttamente con IEnumerator, vedrai la non purezza a occhio nudo.

Un altro modo di pensarci è dato da una "sequenza", si ottengono due risultati: "valore successivo" e "resto della sequenza", quindi "resto della sequenza" diventa la nuova "sequenza", e puoi ripetere il processo. (E la "sequenza" originale è andato per sempre)

Questa linea di pensiero può essere espresso direttamente in F #:

type MySeq<'a> = MySeq of (unit -> ('a * MySeq<'a>)) 

Significato: "una sequenza pigro è una funzione che, quando applicata, i rendimenti la sua testa e la sua coda, dove la coda è un'altra sequenza pigra ". MySeq of è incluso per mantenere il tipo da diventare infinito.
(scusate, userò F #, non so Erlang abbastanza bene, io sono sicuro che si può tradurre)

Ma poi, vedendo come le sequenze di solito sono finiti, il tutto dovrebbe essere facoltativo:

type MySeq<'a> = MySeq of (unit -> ('a * MySeq<'a>) option) 

Data questa definizione, si può banalmente fare alcuni costruttori:

module MySeq = 
    let empty = MySeq <| fun() -> None 
    let cons a rest = MySeq <| fun() -> Some (a, rest) 
    let singleton a = cons a empty 
    let rec repeat n a = 
     if n <= 0 then empty 
     else MySeq <| fun() -> Some (a, (repeat (n-1) a)) 
    let rec infinite a = MySeq <| fun() -> Some (a, infinite a) 
    let rec ofList list = 
     match list with 
     | [] -> empty 
     | x :: xs -> MySeq <| fun() -> Some (x, ofList xs) 

Mappa e piega sono anche banale:

let rec map f (MySeq s) = MySeq <| fun() -> 
    match s() with 
    | None -> None 
    | Some (a, rest) -> Some (f a, map f rest) 

let rec fold f acc0 (MySeq s) = 
    match s() with 
    | None -> acc0 
    | Some (a, rest) -> fold f (f acc0 a) rest 

E da fold è possibile creare tutto, che non è una sequenza pigra stessa. Ma per costruire sequenze pigri, è necessario un "piega rolling" (a volte chiamato "scan"):

let rec scan f state0 (MySeq s) = MySeq <| fun() -> 
    match s() with 
    | None -> None 
    | Some (a, rest) -> 
     let newState = f state0 a 
     Some (newState, scan f newState rest) 

// reformulate map in terms of scan: 
let map f = scan (fun _ a -> f a) Unchecked.defaultof<_> 

Ecco come usarlo:

let emptySeq = MySeq.empty 
let numbers = MySeq.ofList [1; 2; 3; 4] 
let doubles = MySeq.map ((*) 2) numbers // [2; 4; 6; 8] 
let infiniteNumbers = 
    MySeq.infinite() 
    |> MySeq.scan (fun prev _ -> prev+1) 0 
let infiniteDoubles = MySeq.map ((*) 2) infiniteNumbers 

E in conclusione, mi piacerebbe aggiunga che la soluzione basata sulla mutazione sarà quasi sempre più performante (a parità di tutte le cose), almeno un po '. Anche se si getta via il vecchio stato come si calcola nuovo, la memoria deve ancora essere recuperata, che a sua volta è un successo in termini di prestazioni. I vantaggi dell'immutabilità non includono la messa a punto delle prestazioni.

Aggiornamento:
Ecco la mia crepa alla versione Erlang. Tieni presente che questo è il primo codice che abbia mai scritto in Erlang. In quanto tale, sono sicuro che ci sono modi migliori per codificarlo e che ci deve essere una libreria per questo già disponibile.

-module (seq). 
-export ([empty/0, singleton/1, infinite/1, repeat/2, fold/3, scan/3, map/2, count/1]). 

empty() -> empty. 
singleton(A) -> fun() -> {A, empty} end. 
infinite(A) -> fun() -> {A, infinite(A)} end. 

repeat(0,_) -> empty; 
repeat(N,A) -> fun() -> {A, repeat(N-1,A)} end. 

fold(_, S0, empty) -> S0; 
fold(F, S0, Seq) -> 
    {Current, Rest} = Seq(), 
    S1 = F(S0, Current), 
    fold(F, S1, Rest). 

scan(_, _, empty) -> empty; 
scan(F, S0, Seq) -> fun() -> 
    {Current, Rest} = Seq(), 
    S1 = F(S0, Current), 
    {S1, scan(F, S1, Rest)} 
end. 

map(F, Seq) -> scan(fun(_,A) -> F(A) end, 0, Seq). 
count(Seq) -> fold(fun(C,_) -> C+1 end, 0, Seq). 

utilizzati:

1> c(seq). 
{ok,seq} 
2> FiveTwos = seq:repeat(5,2). 
#Fun<seq.2.133838528> 
3> Doubles = seq:map(fun(A) -> A*2 end, FiveTwos). 
#Fun<seq.3.133838528> 
5> seq:fold(fun(S,A) -> S+A end, 0, Doubles). 
20 
6> seq:fold(fun(S,A) -> S+A end, 0, FiveTwos). 
10 
11> seq:count(FiveTwos). 
5 
+0

Grazie per l'aiuto, ma il codice non viene compilato in VS 2012. In "Alcuni (a, ripeti (n-1) a)" o " Alcuni (a, infinito a) "si lamenta:" Tipo mancata corrispondenza. Aspettando un 'a unità -> (' b * 'a) opzione Il tipo risultante sarebbe infinito quando unificando' 'a' e 'unità -> (' b * 'a) opzione'' Sfortunatamente conosco Erlang da circa 3 ore, quindi non ho idea di come tradurre la maggior parte di questo, specialmente quando non riesco a vederlo funzionare. –

+0

@JacekGajek, devi perdonarmi per codice non compilato, stavo scrivendo sul mio telefono in quel momento. Ho pensato che l'idea dovrebbe essere abbastanza chiara da sola e includere solo il codice per l'illustrazione. Ho sostituito tutti gli esempi con codice corretto e verificato. –

+0

@JacekGajek Ho anche prodotto una versione di Erlang proprio ora, sentitevi liberi di usarlo come riferimento. –

5

Questo non è testato, ma è un modo per farlo.

L'idea è quella di trasformare l'elenco in un processo che restituisce il valore successivo quando richiesto. Puoi facilmente generalizzare l'idea se hai bisogno di farlo.

In alternativa, è possibile scrivere uno spiegamento che può quindi aprire l'elenco un po 'alla volta e utilizzarlo come input per il processore generico.

Un altro modo è quello di implementare flussi pigri, basato sull'idea che qualsiasi Expr possono essere ritardate fun() -> Expr end forse meglio scritto come -define(DELAY(X), fun() -> X end). come macro e poi utilizzati insieme con -define(FORCE(X), X()).

-module(z). 

-export([integral/4]). 

create(Dx, N) -> 
    spawn_link(fun() -> create_loop(Dx, N) end). 

create_loop(Dx, 0, Acc)-> 
    receive 
     {grab, Target} -> Target ! done, 
     ok 
    after 5000 -> 
     exit(timeout_error) 
    end; 
create_loop(Dx, N, Acc) -> 
    receive 
     {grab, Target} -> 
      Target ! {next, Dx*N}, 
      create_loop(Dx, N-1) 
    after 5000 -> 
     exit(timeout_error) 
    end. 

next(Pid) -> 
    Pid ! {grab, self()}, 
    receive 
     {next, V} -> {next, V}; 
     done -> done 
    after 5000 -> 
     exit(timeout_error) 
    end. 

sum(F, Points, Acc) -> 
    case next(Points) of 
     {next, V} -> sum(F, Points, Acc + F(V)); 
     done -> Acc 
    end. 

integral(X1, X2, Dx, F) -> 
    N = trunc((X2 - X1)/Dx), 
    Points = create(Dx, N), 
    sum(fun(X) -> F(X) * Dx end, Points, 0). 

La soluzione basata su DELAY/FORCE è qualcosa del tipo:

-module(z). 
-define(DELAY(X), fun() -> X end). 
-define(FORCE(X), X()). 

create(Dx, N) -> 
    [0 | ?DELAY(create_loop(Dx, N))]. 

create_loop(Dx, N) -> 
    [Dx*N | ?DELAY(create_loop(Dx, N-1)]; % This is an abuse of improper lists 
create_loop(_, 0) -> []. 

map(F, []) -> []; 
map(F, [V | Thunk]) -> 
    [F(V) | ?DELAY(map(F, ?FORCE(Thunk)))]. 

sum([], Acc) -> Acc; 
sum([V | Thunk], Acc) -> 
    sum(?FORCE(Thunk), V + Acc). 

integral(X1,X2,Dx, F) -> 
    N = trunc((X2-X1)/Dx), 
    Points = create(Dx, N), 
    Vals = map(fun(X) -> F(X)*Dx end, Points), 
    sum(Vals). 

Ma non testato.

+0

Troppo complicato ... Il multithreading è un passo avanti. Per sapere preferirei avere la soluzione più semplice possibile. –

+0

Se lo pulisci un po ', non è complicato.La maggior parte della struttura può essere sollevata in una biblioteca. Inoltre, ha il valore aggiunto che può produrre valori in parallelo con il tuo calcolo, il che è positivo per alcuni problemi. Tuttavia, ho aggiunto l'idea di DELAY/FORCE per rendere stream.s esplicito. –

2

Il modo più popolare per creare trasformazione stabile memoria è definire coda funzione ricorsiva. Per esempio:

integrate_rec(X1, X2, DX, F) when X2 >= X1 -> 
    integrate_rec(X1, X2, DX, F, X1, 0, 1); 
integrate_rec(X1, X2, DX, F) when X2 < X1 -> 
    integrate_rec(X2, X1, DX, F, X2, 0, -1). 

integrate_rec(X1, X2, _DX, _F, X, Sum, Sign) when X >= X2 -> 
    Sign*Sum; 
integrate_rec(X1, X2, DX, F, X, Sum, Sign) -> 
    integrate_rec(X1, X2, DX, F, X + DX, Sum + DX*F(X), Sign). 

Ma non sembra chiaro ... Ho avuto lo stesso problema una volta ho fatto short helper for function che permette di iterare senza liste:

integrate_for(X1, X2, DX, F) -> 
    Sign = if X2 < X1 -> -1; true -> 1 end, 
    Sum = (for(0, {X1, X2, Sign*DX}))(
      fun (X, Sum) -> 
       Sum + DX*F(X) 
      end), 
    Sign*Sum. 

Purtroppo, è un po ' bit più lento di ricorsione diretta:

benchmark() -> 
    X1 = 0, 
    X2 = math:pi(), 
    DX = 0.0000001, 
    F = fun math:sin/1, 
    IntegrateFuns = [fun integrate_rec/4, fun integrate_for/4], 
    Args = [X1, X2, DX, F], 
    [timer:tc(IntegrateFun, Args) || IntegrateFun <- IntegrateFuns]. 

> [{3032398,2.000000000571214},{4069549,2.000000000571214}] 

Quindi è ~ 3.03s a ~ 4.07s - non è così male.

0

mi piace espressione concisa, è per questo che propongo questa via soluzione (definito nel guscio, ma dovrebbe essere facile da adattare a un modulo):

1> Int = fun Int(X,N,N,D,F,V,LF) -> (V + (F(N*D+X)+LF)*D)/2; Int(X,C,N,D,F,V,LF) -> NF = F(X+C*D), Int(X,C+1,N,D,F,V+(NF+LF)*D,NF) end. 
#Fun<erl_eval.27.90072148> 
2> Integral = fun(X1,X2,Dx,F) -> S = abs(X2-X1)/(X2-X1), N = round(S*(X2-X1)/Dx), Int(X1,1,N,S*Dx,F,0,F(X1)) end. 
#Fun<erl_eval.4.90072148> 
3> F = fun(X) -> 2*X end. 
#Fun<erl_eval.6.90072148> 
4> Integral(0,2,0.00001,F). 
4.000000000000002 
5> Integral(2,0,0.00001,F). 
-3.9999999999999996 
6> 

Int fa la valutazione loop ricorsivo, Integral prepara i parametri prima di chiamare Int.