Erlang替代f#序列

Question

在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).

Answer 1

免责声明:以下是在假设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