ErlangのReduceの観点からのマップの実装

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（N）であり、追記とは異なり、O（1）であるので、我々は逆にリストを作成しています。 lists:reverseもこのマップ関数をO（n）にするO（1）で実行されます。 fun(Acc, X) -> AcC++ [F(X)] endを実行してその逆がなければ、O（n^2）になります。