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) 内存要求,这对于这样简单的函数是 Not Acceptable ,
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).
最佳答案
免责声明:以下内容是在 Erlang 完全不允许突变的假设下编写的,我不确定,因为我不太了解 Erlang。
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
最后,我想补充一点,基于突变的解决方案几乎总是性能更高(所有条件都相同),至少有一点。即使在计算新状态时立即丢弃旧状态,内存仍然需要回收,这本身就是性能损失。不变性的好处不包括性能微调。
更新:
这是我在 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
关于f# - Erlang 替代 f# 序列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30265901/