Отказ от ответственности: нижеследующее написано в предположении, что Эрланг полностью запрещает мутацию, о которой я не уверен, потому что я не знаю Эрланга достаточно хорошо.
Seq внутренне мутационный. Он поддерживает «текущее состояние» и мутирует его на каждой итерации. Так что, когда вы делаете одну итерацию, вы получаете «следующее значение», но вы также получаете побочный эффект, который изменил внутреннее состояние счетчика, и когда вы выполните следующую итерацию, вы получите другое «следующее значение», , и так далее. Обычно это красиво покрывается функционально выглядящими соображениями, но если вы когда-либо работали с IEnumerator
, вы увидите нечистоту невооруженным глазом.
Другой способ подумать об этом, учитывая «последовательность», вы получаете два результата: «следующее значение» и «остальная последовательность», а затем «остальная последовательность» становится вашей новой «последовательностью» и вы можете повторить этот процесс. (И оригинальная «последовательность» навсегда ушла)
Эта линия мысли может быть непосредственно выражена в F #:
type MySeq<'a> = MySeq of (unit -> ('a * MySeq<'a>))
Значения: «ленивая последовательность представляет собой функцию, которая при их применении, возвраты его голову и хвост, где хвост - еще одна ленивая последовательность ». MySeq of
включен, чтобы сохранить тип бесконечным.
(извините, я буду использовать F #, я не знаю, Erlang достаточно хорошо, я уверен, что вы можете перевести)
Но затем, видя, как последовательности, как правило, конечно, то все это должно быть факультативным:
type MySeq<'a> = MySeq of (unit -> ('a * MySeq<'a>) option)
Учитывая это определение, вы можете тривиальным сделать некоторые конструкторы:
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)
Карта и сгиб также тривиальна:
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
И от fold
вы можете построить все, что не является ленивой последовательностью. Но строить ленивые последовательности, вам нужен «качению складку» (иногда называемый «сканирование»):
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<_>
Вот как его использовать:
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
И в заключение я хотел бы добавьте, что решение на основе мутации почти всегда будет более эффективным (при прочих равных условиях), по крайней мере, немного. Даже если вы сразу выбросите старое состояние при вычислении нового, память все еще нуждается в исправлении, что само по себе является хитом производительности. Преимущества неизменности не включают настройку производительности.
Update:
Вот моя трещина в Erlang версии. Имейте в виду, что это самый первый код, который я когда-либо писал в Erlang. Таким образом, я уверен, что есть лучшие способы кодирования этого и что для этого уже есть библиотека.
-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).
Использование:
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
Благодарим за помощь, но ваш код не компилируется под VS 2012. В разделе «Некоторые (a, repeat (n-1) a)» или « Некоторые (a, бесконечные a) "он жалуется:' Тип несоответствия. Ожидание 'a ' a , но с учетом блока -> ('b *' a) Результирующий тип будет бесконечным при объединении опции '' a 'и' unit -> ('b *' a) ' К сожалению, я знаю Erlang около 3 часов, поэтому я не знаю, как перевести большую часть этого, особенно когда я не могу смотреть, как он работает. –
@JacekGajek, вы должны простить меня за некомпилирующий код, я печатал его на своем телефоне в то время. Я думал, что идея должна быть достаточно ясной сама по себе и включала только код для иллюстрации. Я заменил все примеры на правильный, проверенный код. –
@JacekGajek Я также выпустил версию Erlang только сейчас, не стесняйтесь использовать ее для справки. –