Want more features on Pastebin? Sign Up, it's FREE!
Guest

MononcQc

By: a guest on Mar 19th, 2009  |  syntax: Erlang  |  size: 2.69 KB  |  views: 50  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. -module(generators).
  2. -author([{name,"Fred T-H"},{email, hidden}]).
  3. -description("An example of generators implemented in erlang,
  4. allowing to generate the equivalent of lists with constant memory.").
  5. -vsn(0.0).
  6. -export([t_fib/1, y_fib/1, sum/1, fold/3, test/2, batch_test/3]).
  7.  
  8. % macros to make the creation of generators a tad more user-friendly.
  9. -define(yield(X), receive {Pid, next} -> Pid ! {self(), X} end).
  10. -define(last_yield(X), receive {Pid, next} -> Pid ! {self(), X, done} end).
  11.  
  12. %% Tail-recursive fibonacci function.
  13. t_fib(1) -> [1];
  14. t_fib(2) -> [1,1];
  15. t_fib(L) -> t_fib(3,L,[1,1]).
  16.  
  17. t_fib(L,L,[N1,N2|_]=F) ->
  18.     lists:reverse([N1+N2|F]);
  19. t_fib(C, L, [N1,N2|_]=F) ->
  20.     t_fib(C+1,L,[N1+N2|F]).
  21.  
  22. %% Generator-like tail-recursive fibonacci function.
  23. y_fib(L) ->
  24.     y_fib(1,L,1,0).
  25.  
  26. y_fib(L,L,N1,N2) ->
  27.     ?last_yield(N1+N2);
  28. y_fib(C, L, N1,N2) ->
  29.     N = N1+N2,
  30.     ?yield(N),
  31.     y_fib(C+1,L,N2,N).
  32.  
  33. %% what the lists:sum version for generators could look like
  34. sum({M,Gen,Args}) ->
  35.     Pid = spawn(M, Gen, Args),
  36.     sum(Pid,0).
  37. sum(Pid,S) ->
  38.     Pid ! {self(), next},
  39.     receive
  40.         {Pid, N} -> sum(Pid, S+N);
  41.         {Pid, N, done} -> S+N
  42.     end.
  43.  
  44. %% ... and lists:foldl/3 (no foldr possible with generators).
  45. fold(F, Acc,{M,Gen,Args}) when is_function(F,2) ->
  46.     Pid = spawn(M,Gen,Args),
  47.     fold(F, Acc, Pid);
  48. fold(F, Acc, Pid) ->
  49.     Pid ! {self(), next},
  50.     receive
  51.         {Pid, N} -> fold(F, F(N,Acc), Pid);
  52.         {Pid, N, done} -> F(N,Acc)
  53.     end.
  54.  
  55. %% Comparing execution times of lists vs generators
  56. test(fold,N) ->
  57.     erlang:statistics(wall_clock),
  58.     F = fun(X, Acc) ->
  59.           if X rem 2 == 0 -> Acc+1;
  60.              true -> Acc
  61.           end
  62.         end,
  63.     ?MODULE:fold(F, 0, {?MODULE, y_fib, [N]}),
  64.     io:format("generator ok~n"),
  65.     {_, T1} = erlang:statistics(wall_clock),
  66.     lists:foldl(F, 0, t_fib(N)),
  67.     io:format("list ok~n"),
  68.     {_, T2} = erlang:statistics(wall_clock),
  69.     if T1>0 -> {T1,T2, T2/T1};
  70.        T2 == T1, T1 == 0 -> {T1,T2,1};
  71.        true -> {T1,T2, '?'}
  72.     end;
  73. test(sum, N) ->
  74.     erlang:statistics(wall_clock),
  75.     ?MODULE:sum({?MODULE, y_fib, [N]}),
  76.     io:format("generator ok~n"),
  77.     {_, T1} = erlang:statistics(wall_clock),
  78.     lists:sum(t_fib(N)),
  79.     io:format("list ok~n"),
  80.     {_, T2} = erlang:statistics(wall_clock),
  81.     if T1>0 -> {T1,T2, T2/T1};
  82.        T2 == T1, T1 == 0 -> {T1,T2,1};
  83.        true -> {T1,T2, '?'}
  84.     end.
  85.  
  86. %% Testing lists vs generators many times.
  87. batch_test(Type, N, Lim) ->
  88.     batch_test(Type, N, 0, Lim, 0).
  89. batch_test(_Type,_N,Lim,Lim,Acc) ->
  90.     Acc/Lim;
  91. batch_test(Type,N,Ct,Lim,Acc) ->
  92.     {_,_,X} = test(Type,N),
  93.     batch_test(Type,N,Ct+1,Lim,Acc+X).
clone this paste RAW Paste Data