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