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
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. –
@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. –
@JacekGajek Ho anche prodotto una versione di Erlang proprio ora, sentitevi liberi di usarlo come riferimento. –