Question

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 all the list of tuples are sorted from smaller to higher frequenties.

I am asking if someone can help me to slove it or a pointer to a tutorial where i can find more tips to do it.

Thanks for your reply.

Answer 1

The standard library has for example the bag datatype that nicely has all the tools ready. You basically just convert your list to a bag and then convert the bag back to a list with the frequencies. Then use the sort for lists to have it sorted like you want. Or you can do the same by hand and fold over the list with a map as the accumulator where you store the encountered elements with their occurrence count.

An example with the bag:

:- module freq.
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.

:- implementation.
:- import_module string.
:- import_module list.
:- import_module assoc_list.
:- import_module bag.

main(!IO) :- 
  List = string.to_char_list("this is a test"),
  bag.from_list(List, Bag),
  bag.to_assoc_list(Bag, ElemSortedAssocList),
  list.sort(assoc_list.reverse_members(ElemSortedAssocList), CountSortedAssocList),
  assoc_list.reverse_members(CountSortedAssocList, Result),
  io.write(Result, !IO),
  io.nl(!IO).

友情链接