[mercury-users] Converting List To List Of Tuples

Raphael Collet rco at missioncriticalit.com
Sat Dec 18 00:50:41 AEDT 2010


Dear Eddie,

Okay, I will give you some guidance.  Maybe we should leave the map 
aside, and use a simpler data structure to count frequencies.  My 
proposal is to count frequencies directly with a list({T, int}).

Assume you have the string "a ball".  You start off with an empty list 
of frequencies.  Here is how the frequencies are updated while you 
process the items:

initially:	-> []
process 'a'	-> [{'a',1}]
process ' '	-> [{'a',1},{' ',1}]
process 'b'	-> [{'a',1},{' ',1},{'b',1}]
process 'a'	-> [{'a',2},{' ',1},{'b',1}]
process 'l'	-> [{'a',2},{' ',1},{'b',1},{'l',1}]
process 'l'	-> [{'a',2},{' ',1},{'b',1},{'l',2}]

For each item I, you call a function inc_freq(I, FreqList) which returns 
the FreqList with the item's counter incremented.  If the item is not 
present, the element {I,1} is added to FreqList.

% return the frequency list with the given item's frequency incremented
:- func inc_freq(T, list({T,int})) = list({T,int}).

inc_freq(I, []) = [{I,1}].
inc_freq(I, [{J,N}|Freqs]) =
     ( I = J ->
         [{J,N+1}|Freqs]   % I's counter incremented, rest untouched
     ;
         ?                 % keep J in the list, but increment the
                           % frequency of I in Freqs
     ).

Fill in the question mark above.  Check your solution on paper with the 
example above.

Now that you have this function, you have to apply it on each element of 
the list.  Write an auxiliary function tabel_aux with an extra argument, 
the frequency list that is updated through the process.

% tabel_aux(Items, Freqs) adds the frequencies of Items to Freqs
:- func tabel_aux(list(T), list({T,int})) = list({T,int}).

tabel_aux will apply inc_freq to each element of the list, and return 
the final result, i.e.,

tabel_aux([X, Y, Z], FreqList) =
     inc_freq(Z, inc_freq(Y, inc_freq(X, FreqList)))

Write tabel_aux as a recursive function.  By applying it on an empty 
frequency list, you will get the items' frequencies.  What remains to be 
done is to sort the list to get the less frequent items first.  Let us 
use the function list.sort/2:

tabel(Items) = sort(compare_freq, tabel_aux(Items, [])).

The function sort takes the function compare_freq as a parameter.  The 
latter compares two frequency tuples, and returns (<), (>), or (=) 
depending on how they compare.  You can compute that result by applying 
the predicate compare on the frequencies:

% return the comparison of two frequency tuples
:- func compare_freq({T,int}, {T,int}) = comparison_result.

compare_freq({_, N1}, {_, N2}) = Result :-
     compare(Result, N1, N2).

Now, glue up all together, and you're done.


Cheers,
Raphael


On 12/17/2010 01:02 PM, win1for at yahoo.com wrote:
> Hi Raphael,
>
> Thank you so much for your reply. I really appreciate it. I have been
> taught Mercury for only 4 hours and am suppose to do that task. My only
> problem now is how to begin. Infact i really want to do it myself so
> that i can learn from it. So i will ask you specific questions to help
> me get the procedure so that i can do it myself. This is how it is.
>
> The function siganature is this:
>
> tabel(list(T)) = list({T,int})
>
> (it must work with both lists of characters and ints). The results -
> (lists of tuples) - The first element in each tuple is an element from
> the list and the second element is the frequentie of the element in the
> list.
>
> so my first line of my implementation is this:
>
> tabel([X|Xs]) =
>
>
> Now these are my concerns::
>
> Do i have to go through the list and set the keys of the map with the
> elements in the list. Meaning that the values will be empty and then
> later i will go over the list again and set the values(frequenties) ?
>
> I would like you to give me the steps i should follow and solve it. For
> instance you mentioned functions like:
>
> map.set/4
> map.set/3
> string.foldl/4
> assoc_list
> map
> pair
>
> in your replies. Can you please explain to me how all these functions
> fit in so that i can understand the procedure and do it. I need the
> steps so that i can do it. I have good understanding from your replies
> so what i need now is the steps to follow and get it done
>
> Thank you so much for your time and concern.
>
> Regards,
> Eddie
>
>
>
>
> --- On *Fri, 12/17/10, Raphael Collet /<rco at missioncriticalit.com>/* wrote:
>
>
>     From: Raphael Collet <rco at missioncriticalit.com>
>     Subject: Re: [mercury-users] Converting List To List Of Tuples
>     To: mercury-users at csse.unimelb.edu.au
>     Cc: "win1for at yahoo.com" <win1for at yahoo.com>
>     Date: Friday, December 17, 2010, 6:33 AM
>
>     Dear anonymous user,
>
>     What you ask for looks a lot like a homework... I ain't going to do the
>     homework for you. Here are a few hints, though.
>
>     The function map.init returns an empty map. That's where you should
>     start from.
>
>     The predicate map.set/4 (and the function map.set/3) allows you to set
>     the value associated to a key in the map. In your case, this could be
>     the current frequency of a character.
>
>     The predicate map.search/3 looks up for a given key, and return the
>     corresponding value. You can use this to retrieve the frequency of a
>     character. The typical use-case is:
>
>     ( map.search(Map, Key, Value) ->
>     % do something with the value
>     ;
>     % no value for key, do something else
>     )
>
>     Cheers,
>     Raphael
>
>     On 12/17/2010 11:56 AM, win1for at yahoo.com
>     </mc/compose?to=win1for at yahoo.com> wrote:
>      >
>      > Please am a total beginner can you give me an example of how to
>     use the map.
>      >
>      > thanks for your reply
>      > --- On *Fri, 12/17/10, Raphael Collet /<rco at missioncriticalit.com
>     </mc/compose?to=rco at missioncriticalit.com>>/* wrote:
>      >
>      >
>      > From: Raphael Collet <rco at missioncriticalit.com
>     </mc/compose?to=rco at missioncriticalit.com>>
>      > Subject: Re: [mercury-users] Converting List To List Of Tuples
>      > To: mercury-users at csse.unimelb.edu.au
>     </mc/compose?to=mercury-users at csse.unimelb.edu.au>
>      > Cc: "win1for at yahoo.com </mc/compose?to=win1for at yahoo.com>"
>     <win1for at yahoo.com </mc/compose?to=win1for at yahoo.com>>
>      > Date: Friday, December 17, 2010, 3:44 AM
>      >
>      > Dear user,
>      >
>      > I suggest you to have a look at the modules map, pair and assoc_list.
>      > With a map, you will be able to build the frequency map. Start
>     from an
>      > empty map, then increment the frequency of each character you find in
>      > the string. The predicate string.foldl/4 is useful to iterate
>     over all
>      > the characters of the string.
>      >
>      > To convert the map into a list of pairs, you may simply use
>      >
>      > ListOfPairs = map.to_assoc_list(FrequencyMap)
>      >
>      > In your case, the result will be of type list(pair(char, int)). Note
>      > that the pair is not strictly a tuple, but a more specific type for a
>      > tuple of exactly two elements.
>      >
>      > The last point you need is to sort the list with list.sort/3. Simply
>      > define a comparison predicate to compare two values of type
>     pair(char,
>      > int): order them by their second components. Something like:
>      >
>      > :- pred compare_freq(pair(K, int), pair(K, int), comparison_result).
>      > :- mode compare_freq(in, in, out) is det.
>      >
>      > compare_freq(X1 - F1, X2 - F2, Result) :- compare(Result, F1, F2).
>      >
>      > The predicate compare/3 and its associated types is defined in the
>      > module builtin.
>      >
>      >
>      > I hope this will help you.
>      >
>      > Cheers,
>      > Raphael
>      >
>      >
>      > On 12/17/2010 05:22 AM, win1for at yahoo.com
>     </mc/compose?to=win1for at yahoo.com>
>      > </mc/compose?to=win1for at yahoo.com
>     </mc/compose?to=win1for at yahoo.com>> wrote:
>      > > Hello,
>      > >
>      > >
>      > > I am just a total beginner in mercury and finding it hard to
>      > solve this
>      > > problem. I want to convert a list to a list of tupples sorted from
>      > > smaller to higher frequenties. Eg:
>      > >
>      > > |string.to_char_list("this is a test") becomes
>      > >
>      > > [{'a', 1}, {'e', 1}, {'h', 1}, {'i', 2}, {' ', 3}, {'s', 3},
>      > {'t', 3}]
>      > >
>      > > OR
>      > >
>      > > [3,2,1,2,1,1,2] becomes
>      > >
>      > > [{3, 1}, {1, 3}, {2, 3}]
>      > > |
>      > >
>      > > You can see that the list of tuples are sorted from smaller to
>     higher
>      > > frequenties.
>      > >
>      > > I am asking if someone can help me to solve this or point me to a
>      > > tutorial where i can find more tips to do it.
>      > >
>      > >
>      > > Thanks for your reply.
>      > >
>      > >
>      >
>      >
>     --------------------------------------------------------------------------
>      > mercury-users mailing list
>      > Post messages to: mercury-users at csse.unimelb.edu.au
>     </mc/compose?to=mercury-users at csse.unimelb.edu.au>
>      > </mc/compose?to=mercury-users at csse.unimelb.edu.au
>     </mc/compose?to=mercury-users at csse.unimelb.edu.au>>
>      > Administrative Queries: owner-mercury-users at csse.unimelb.edu.au
>     </mc/compose?to=owner-mercury-users at csse.unimelb.edu.au>
>      > </mc/compose?to=owner-mercury-users at csse.unimelb.edu.au
>     </mc/compose?to=owner-mercury-users at csse.unimelb.edu.au>>
>      > Subscriptions: mercury-users-request at csse.unimelb.edu.au
>     </mc/compose?to=mercury-users-request at csse.unimelb.edu.au>
>      > </mc/compose?to=mercury-users-request at csse.unimelb.edu.au
>     </mc/compose?to=mercury-users-request at csse.unimelb.edu.au>>
>      >
>     --------------------------------------------------------------------------
>      >
>      >
>
>

--------------------------------------------------------------------------
mercury-users mailing list
Post messages to:       mercury-users at csse.unimelb.edu.au
Administrative Queries: owner-mercury-users at csse.unimelb.edu.au
Subscriptions:          mercury-users-request at csse.unimelb.edu.au
--------------------------------------------------------------------------



More information about the users mailing list