将常用项目列表转为有序对列表 [英] Turn a list with common items in to a list of ordered pairs

问题描述

我对函数式编程完全陌生，这是SML的一项家庭作业。

我有一个整数列表，我试图获得有序对的列表，其中第二个条目是数字第一个入口出现在初始列表中。

例如：

  [2,3,3,5] => [（2,1），（3,2），（5,1）] 
  

'I'我不希望有人实现这一点，而是让我知道我正在寻找什么样的高阶函数和/或正确方向的指针。再次，对函数式编程来说是全新的，对于SML语言来说更是新的。

我最初的想法是我想要使用 map ，但我无法弄清楚如何跟踪或合并类似的项目。我只能成功地将每个项目转换为有序对，第二个条目等于1 ......完全没有用处。

解决方案

因此，为此，您可能会想要使用折叠，如 foldl 。

，当决定是否使用 map 或fold时（这里我把fold表示为 foldl 或<$ c $你可以使用下面的经验法则：

如果你想要的列表具有与你得到的清单，你可能需要一个 map 。否则，您需要折叠。

推理如下：对于列表中的每个元素， map 在输出中生成一个变换元素。另一方面，它更普遍，可以做任何你想做的事情。 （你确实可以使用fold来实现 map ，这并不意味着你当然不需要使事情变得复杂）

为了完整起见，让我简单说明褶皱如何工作。一个折叠遍历一个列表（从左边的 foldl ，右边的 foldr ，因此是名称），构建一次一个元素的累加器结果。

让我们看一个例子：

  foldl（fn（e，a）=> e + a）0 [5,3,7,10] 
  

这里 e 是我们目前使用的元素， a 累加器变量（即当前结果）。我们以 a = 0 开头，因为我们将 0 指定为起始值。

  | e | a |新的
 ------------------------- 
 | 5 | 0 | 5 + 0 = 5 
 | 3 | 5 | 3 + 5 = 8 
 | 7 | 8 | 7 + 8 = 15 
 | 10 | 15 | 10 + 15 = 25 
 | | 25 | 
  

这给了我们一个最终的 a code> 25 ，我们看到函数将列表中的元素相加。请注意，在任何迭代中， a 的值是到目前为止列表中元素的总和，以及我们如何扩展此列表以包含多个元素。

这是我建议用来解决这个问题的方法。

• 考虑 a 的基值应该是多少。 （与获取 [] 作为输入的结果相同。）


• 请考虑如何从较小的列表中获取结果，并将其扩展为包含其他元素。

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.

这篇关于将常用项目列表转为有序对列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！