I am entirely new to functional programming; this is a homework assignment for SML.
I have a list of integers and I am trying to get a list of ordered pairs where the second entry of the pair is the number of times the first entry appeared in the initial list.
For example:
[2,3,3,5] => [(2,1),(3,2),(5,1)]
I'm not hoping for somebody to implement this but rather give me an idea of what sort of higher-order function I am looking for, and/or a pointer in the right direction. Again, totally new to functional programming and even more new to the SML language.
My initial thought was that I want to use map, but I can't figure out how to keep track of or merge similar items. I've only successfully been able to turn each item to an ordered pair with the second entry equal to 1... quite useless.
So, for this you'll probably want to use a fold, like foldl.
In general, when deciding on whether to use map or fold (here I take fold to mean either foldl or foldr), you can use the following rule of thumb:
If the list you want out has exactly the same number of elements as the list you get in, you probably want a map. Else, you'll want a fold.
The reasoning being as follows: For each element in the list, map produces a transformed element in the output. fold, on the other hand, is more general, and can do whatever you want it to. (And you could indeed implement map using a fold. This doesn't mean that you should, of course, no need to make things needlessly complex)
For completeness' sake, let me give a short explanation of how folds work. A fold runs through a list (foldl from the left, foldr from the right, hence the names), building up a result in an accumulator one element at a time.
Let's see it in an example:
foldl (fn (e, a) => e + a) 0 [5, 3, 7, 10]
Here e is the element we're currently working with, and a the accumulator-variable (i.e. the current result). We start with a = 0, because we specified 0 to be the starting value.
| e | a | new a
-------------------------
| 5 | 0 | 5 + 0 = 5
| 3 | 5 | 3 + 5 = 8
| 7 | 8 | 7 + 8 = 15
| 10 | 15 | 10 + 15 = 25
| | 25 |
This gives us a final a of 25, and we see that the function summed up the elements in the list. Notice how, at any iteration, the value of a is the sum of the elements in the list so far, and how we each step expand this list to include one more element.
This is the sort of approach I'd recommend for solving this problem.
- Consider what the base value for
a should be. (The same as the result of getting [] as input.)
- Consider then how to take the result from a smaller list, and expanding it to include another element.
Besides using folding, here is another hint: Since [(2,1),(3,2),(5,1)] is a final result, the return value of the accumulating function that fold uses could have this type; (int * int) list. You have then reduced the problem to
foldl (fn (elem, acc) => ...) [] xs
where f should insert elem, e.g. 5, into accum, e.g. [(2,1),(3,2)]. f could be considered an insert function, or equivalently, call such an insert function, so long as it produces something like [(2,1),(3,2),(5,1)] (i.e., look through already found elements, increase it if found, or insert it with count 1 if not found.
