在 Erlang 中根据 Reduce 实现 Map

Question

我是 Erlang 的初学者，我正在尝试根据 Reduce 函数实现 Map 函数。但是，我无法想象你是怎么做到的……我有到目前为止试过了：

reduce(_, Acc, [])     -> Acc;
reduce(Fn,Acc,[Hd|Tl]) -> reduce(Fn,Fn(Acc,Hd),Tl). 

map(F,[])      -> [];
map(F,[Hd|Tl]) -> [reduce(F,F(Hd),[]) | map(F,Tl)].

但是我觉得这个解决方案有点幼稚。有什么帮助吗？

Answer 1

如果你已经有一个reduce函数，你不需要使用递归来映射一个列表。您可以将 (Acc, X) -> [F(X) | Acc] 作为函数传递给 reduce，然后在最后调用 lists:reverse，因为列表将以相反的顺序创建。

map(F, List) -> lists:reverse(reduce(fun(Acc, X) -> [F(X) | Acc] end, [], List)).

我们正在反向创建列表，因为将元素添加到列表的时间复杂度为 O(1)，而追加的时间复杂度为 O(n)。 lists:reverse 也在 O(1) 中运行，这使得此映射函数为 O(n)。如果我们做了 fun(Acc, X) -> Acc ++ [F(X)] end 并且没有反转，那就是 O(n^2).

在 Erlang 中根据 Reduce 实现 Map

Implementing Map in terms of Reduce in Erlang

erlang

reduce