Erlang/OTP Forums
Author Message

<  Erlang  ~  List program
Babbler
Posted: Thu Sep 10, 2009 5:37 am Reply with quote
Joined: 10 Sep 2009 Posts: 1
Program finds X element of list and puts it on the first place. Parametars are element X and list L.
I'm new in erlang, and finding problems with this program.
Thanks, for help.
Back to top View user's profile Send private message
baryluk
Posted: Thu Sep 10, 2009 11:25 am Reply with quote
User Joined: 05 Aug 2009 Posts: 48
if you need something like this:
Code:

f(4, [1,2,3,4,5,6,7,8,9]) -> [4,1,2,3,5,6,7,8,9].


then you basically need to think more how lists works. You will need something like: H=4, Left=[1,2,3], Right=[5,6,7,8,9], then just concatnate this three lists (you can make trivial list [4]), by using ++ (also known as lists:append/2).

Actually better if you will build [3,2,1], becuase it is faster to use F = lists:reverse([3,2,1], [5,6,7,8,9]) than just using F = [1,2,3] ++ [5,6,7,8,9]. After having F = [1,2,3,5,6,7,8,9] you just need to put new head in front of it. [4 | F].

You can use lists:nth/2 and lists:split/2, as a helper function, but this will not be optimal (split will produce something like, [1,2,3] and [4,5,6,7,8,9], but we really want [3,2,1] for optimality, ie. for using in lists:reverse/2 not just ++). Using split:

Code:

f(X, L) ->
  {Left, [H|Tail]} = lists:split(X, L-1),
  [H | Left ++ Tail].


But as i said, split isn't very fast, and also ++ isn't.

So the best is to use single manual iteration (because unfortunetly there is no lists:reversesplit/2 :/ ). Because you want to make function work in constant space of stack (tail recrusive), you will need to keep track of how many elements is left to process on the left side and current ReversedLeft. Start using X and empty list.

Code:

f(X, L) ->
   f(X, L, []).

f(1, [H|L], ReversedLeft) ->
   [H | lists:reverse(ReversedLeft, L)];
f(X, [H|L], ReversedLeft) when X > 0 ->
   f(X-1, L, [H|ReversedLeft]).


The two above codes are equivalent (they even throw exception in the same situations)

If you want to excercise in lists, reimplement some of already existing functions like reverse, split, nth. Smile

Reference manual for lists will be helpfull, there are many interesting functions.

_________________
Witold Baryluk

Erlang Training and Consulting Ltd
http://www.erlang-consulting.com
Back to top View user's profile Send private message
Allan
Posted: Mon Sep 21, 2009 5:16 am Reply with quote
User Joined: 29 Jun 2009 Posts: 30
Babbler wrote:
Program finds X element of list and puts it on the first place. Parametars are element X and list L.

"move_to_front(X, List) -> [X | lists:delete(X, L)]." should do it.
Back to top View user's profile Send private message Send e-mail ICQ Number
Mazen
Posted: Sun Sep 27, 2009 8:26 am Reply with quote
User Joined: 20 Jul 2006 Posts: 164 Location: London
Allan wrote:
Babbler wrote:
Program finds X element of list and puts it on the first place. Parametars are element X and list L.

"move_to_front(X, List) -> [X | lists:delete(X, L)]." should do it.


Note though: If it is required that the element is present in the list before it is "moved" then this won't work... consider the following:

Code:
f(4, [1,2,3]) -> [4, 1, 2, 3]


otherwise it is good.
Back to top View user's profile Send private message
Allan
Posted: Sun Sep 27, 2009 2:32 pm Reply with quote
User Joined: 29 Jun 2009 Posts: 30
Mazen wrote:
Note though: If it is required that the element is present in the list before it is "moved" then this won't work...

Just use "lists:member(X, L)" to check for element presence when needed.

Depending on the paradigm used in your project, you may use one of the following:
Code:

move_to_front_aggressive(Element, List) ->
  [Element | lists:delete(Element, List)]
.

move_to_front_failfast(Element, List) ->
  true = lists:member(Element, List),
  [Element | lists:delete(Element, List)]
.

move_to_front_defensive(Element, List) ->
  case lists:member(Element, List) of
    true -> [Element | lists:delete(Element, List)];
    _    -> List
  end
.
Back to top View user's profile Send private message Send e-mail ICQ Number
Mazen
Posted: Mon Sep 28, 2009 6:25 am Reply with quote
User Joined: 20 Jul 2006 Posts: 164 Location: London
Allan wrote:
Depending on the paradigm used in your project...


Yes, as usual it comes down to specification.
Back to top View user's profile Send private message

Display posts from previous:  

All times are GMT
View next topic
View previous topic
Page 1 of 1
Erlang Forum - Trap Exit Forum Index  ~  Erlang
This forum is locked: you cannot post, reply to, or edit topics.

Jump to:  

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You cannot download files in this forum
Hosted by Erlang Solutions    |    Powered by phpBB and NoseBleed 1.14