Erlang 替代 f# 序列
Erlang alternative to f# sequence
在 Erlang 中是否有 F# "seq" 构造的替代方案？例如，在 F# 中我可以编写一个 O(1) 内存集成函数
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
在 Erlang 中，我有一个使用列表的实现，因此具有 O(n) 内存要求，这对于如此简单的函数来说是不可接受的，
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).
这没有经过测试，但这是一种实现方式。
这个想法是将列表变成一个过程，在被询问时产生下一个值。如果需要，您可以很容易地概括这个想法。
或者，您可以编写一个展开，然后可以一次展开列表并将其用作通用处理器的输入。
另一种方法是实现惰性流，基于这样的想法，即任何 Expr 都可以延迟 fun () -> Expr end 也许最好写成 -define(DELAY(X), fun() -> X end). 作为宏，然后与-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).
基于DELAY/FORCE的解决方案是这样的：
-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).
但未测试。
免责声明：以下是在假设 Erlang 完全不允许突变的情况下编写的，对此我不确定，因为我对 Erlang 还不够了解。
Seq 是基于内部突变的。它维护 "current state" 并在每次迭代时对其进行变异。这样当你进行一次迭代时，你会得到 "next value"，但你也会得到一个副作用，即枚举器的内部状态发生了变化，当你进行下一次迭代时，你将得到一个不同的 [=54] =]，等等。这通常很好地覆盖了功能性的理解，但如果你曾经直接使用 IEnumerator，你会用肉眼看到非纯度。
另一种思考方式是，给定一个 "sequence"，您将得到两个结果："next value" 和 "rest of sequence"，然后 "rest of sequence" 成为您的新 "sequence"，你可以重复这个过程。 （原来的"sequence"已经一去不复返了）
这个思路可以直接用F#表达：
type MySeq<'a> = MySeq of (unit -> ('a * MySeq<'a>))
含义："a lazy sequence is a function that, when applied, returns its head and tail, where tail is another lazy sequence"。 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 开始，您可以构建所有内容，这本身并不是惰性序列。但是要构建惰性序列，您需要一个 "rolling fold"（有时称为 "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<_>
使用方法如下：
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
最后，我想补充一点，基于突变的解决方案几乎总是会更高效（所有条件都相同），至少是一点点。即使您在计算新状态时立即丢弃旧状态，内存仍然需要回收，这本身就是一种性能损失。不变性的好处不包括性能微调。
更新：
这是我对 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
创建内存稳定处理最流行的方法是定义尾递归函数。例如：
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).
但它看起来不太清楚...我曾经遇到过同样的问题并制作了 short helper for function 允许您在没有列表的情况下进行迭代：
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.
不幸的是，它比直接递归要慢一点：
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}]
所以它是 ~3.03s 到 ~4.07s - 还不错。
我喜欢简洁的表达方式，所以我提出了第四个方案（在shell中定义，但应该很容易适应一个模块）：
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 以递归方式进行求值循环，Integral 在调用 Int 之前准备好参数。
在 Erlang 中是否有 F# "seq" 构造的替代方案？例如，在 F# 中我可以编写一个 O(1) 内存集成函数
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
在 Erlang 中，我有一个使用列表的实现，因此具有 O(n) 内存要求，这对于如此简单的函数来说是不可接受的，
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).
这没有经过测试，但这是一种实现方式。
这个想法是将列表变成一个过程，在被询问时产生下一个值。如果需要，您可以很容易地概括这个想法。
或者，您可以编写一个展开，然后可以一次展开列表并将其用作通用处理器的输入。
另一种方法是实现惰性流，基于这样的想法，即任何 Expr 都可以延迟 fun () -> Expr end 也许最好写成 -define(DELAY(X), fun() -> X end). 作为宏，然后与-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).
基于DELAY/FORCE的解决方案是这样的：
-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).
但未测试。
免责声明：以下是在假设 Erlang 完全不允许突变的情况下编写的，对此我不确定，因为我对 Erlang 还不够了解。
Seq 是基于内部突变的。它维护 "current state" 并在每次迭代时对其进行变异。这样当你进行一次迭代时，你会得到 "next value"，但你也会得到一个副作用，即枚举器的内部状态发生了变化，当你进行下一次迭代时，你将得到一个不同的 [=54] =]，等等。这通常很好地覆盖了功能性的理解，但如果你曾经直接使用 IEnumerator，你会用肉眼看到非纯度。
另一种思考方式是，给定一个 "sequence"，您将得到两个结果："next value" 和 "rest of sequence"，然后 "rest of sequence" 成为您的新 "sequence"，你可以重复这个过程。 （原来的"sequence"已经一去不复返了）
这个思路可以直接用F#表达：
type MySeq<'a> = MySeq of (unit -> ('a * MySeq<'a>))
含义："a lazy sequence is a function that, when applied, returns its head and tail, where tail is another lazy sequence"。 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 开始，您可以构建所有内容，这本身并不是惰性序列。但是要构建惰性序列，您需要一个 "rolling fold"（有时称为 "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<_>
使用方法如下：
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
最后，我想补充一点，基于突变的解决方案几乎总是会更高效（所有条件都相同），至少是一点点。即使您在计算新状态时立即丢弃旧状态，内存仍然需要回收，这本身就是一种性能损失。不变性的好处不包括性能微调。
更新：
这是我对 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
创建内存稳定处理最流行的方法是定义尾递归函数。例如：
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).
但它看起来不太清楚...我曾经遇到过同样的问题并制作了 short helper for function 允许您在没有列表的情况下进行迭代：
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.
不幸的是，它比直接递归要慢一点：
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}]
所以它是 ~3.03s 到 ~4.07s - 还不错。
我喜欢简洁的表达方式，所以我提出了第四个方案（在shell中定义，但应该很容易适应一个模块）：
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 以递归方式进行求值循环，Integral 在调用 Int 之前准备好参数。