<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"><head><meta http-equiv=Content-Type content="text/html; charset=us-ascii"><meta name=Generator content="Microsoft Word 15 (filtered medium)"><style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Consolas;
panose-1:2 11 6 9 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri","sans-serif";}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:#0563C1;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:#954F72;
text-decoration:underline;}
span.EmailStyle17
{mso-style-type:personal-compose;
font-family:"Calibri","sans-serif";
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri","sans-serif";}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]--></head><body lang=EN-US link="#0563C1" vlink="#954F72"><div class=WordSection1><p class=MsoNormal>I fellows, I was down for a while, connection payment problems, lol. So I am back, and I have a few ideas I would like to share. Also my cowboy extension framework is marching very nice, I had dedicate some time to it in this offline days.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>My thoughts, when I was doing some algorithms for the framework, I found some questions I would like to share because for example, when working with lists module, and doing some recursive functions, it is usually a problem that we need to do lists:reverse at the end of the algorism to get the data in the right order.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>So I can imagine Erlang implement lists using double linked lists for obvious purposes, I haven’t see the source code so I am just guessing here, so for example when doing length you must spend one O(N) to transverse the list, one O(1) for each element to count them and one final O(1) to return the list. So when using lists:reverse/1 it takes four times what lengths does, so I can play guess, and just that, that you are using indeed a double linked list so you spend one O(n) to transverse the list, three O(1), which is an O(1) in total of course I am just counting the operations as well, to swap the preview and next pointers for each node so the list will be in the reverse order and other O(1) to return the new list which is a pointer of course to the old list just reversed.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>So guessing that it is what you do, how bad could be instead of doing that just make list have one bit more of size in memory by saying the order it have. So when you use lists:reverse/1 is just changing that bit to true and when iterating the list instead of using the next function use preview function and viseversa. The problem will be that you must spend one more O(1) for each element when iterating to choose what function is executed depending on the reverse bit. I just did a little simple erlang example to prove my point, of course it is just for demonstration purposes not for real implementation. <o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'>-module(mylists).<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'>-compile(export_all).<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'>-type mylists_ref() :: erlang:ref().<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'>-spec new(list()) -> mylists_ref().<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'>new(List)-><o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> Ref = erlang:make_ref(),<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> erlang:put({Ref, first}, erlang:hd(List)),<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> store_list(List, Ref),<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> Ref.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'>store_list([A], Ref) -><o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> erlang:put({Ref, final}, A);<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'>store_list([A,B | _] = [_ | Rest], Ref) -><o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> erlang:put({Ref, A, next}, B),<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> erlang:put({Ref, B, preview}, A),<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> store_list(Rest, Ref).<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> <o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'>-spec next(mylists_ref()) -> Element :: any().<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'>next(MyListRef) -><o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> case erlang:get({MyListRef, cursor}) of<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> undefined -><o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> Element =<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> case erlang:get({MyListRef, reversed}) of<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> true -><o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> erlang:get({MyListRef, final});<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> undefined -><o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> erlang:get({MyListRef, first})<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> end,<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> erlang:put({MyListRef, cursor}, Element),<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> Element;<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> Element -><o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> NewElement =<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> case erlang:get({MyListRef, reversed}) of<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> true -><o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> erlang:get({MyListRef, Element, preview});<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> undefined -><o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> erlang:get({MyListRef, Element, next})<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> end,<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> case NewElement of<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> undefined -><o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> undefined;<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> Next -><o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> erlang:put({MyListRef, cursor}, Next),<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> Next<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> end<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> end.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'>reset(MyListRef) -><o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> erlang:erase({MyListRef, cursor}).<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'>-spec reverse(mylists_ref()) -> MyReverseListRef :: mylists_ref().<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'>reverse(MyListRef) -> <o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> reset(MyListRef),<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> case erlang:get({MyListRef, reversed}) of<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> undefined -><o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> erlang:put({MyListRef, reversed}, true);<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> true -><o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> erlang:erase({MyListRef, reversed})<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> end,<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> ok.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'>test() -><o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> MyListRef = mylists:new([1,2,3,4]),<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> FirstElem = mylists:next(MyListRef),<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> mylists:reverse(MyListRef),<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> LastElem = mylists:next(MyListRef),<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'> {FirstElem, LastElem}.<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:10.0pt;font-family:Consolas'><o:p> </o:p></span></p><p class=MsoNormal>Cheers,<o:p></o:p></p><p class=MsoNormal>Ivan (son of Gilberio).<o:p></o:p></p></div></body></html>