对用户定义的数据类型中的元素求和 [英] summing elements from a user defined datatype

问题描述

在介绍f#(即列表)中的预定义数据类型以及如何对列表或序列中的元素求和时，我试图学习如何使用用户定义的数据类型.假设我创建了一种数据类型，将其称为list1:

Upon covering the predefined datatypes in f# (i.e lists) and how to sum elements of a list or a sequence, I'm trying to learn how I can work with user defined datatypes. Say I create a data type, call it list1:

type list1 = 
    A
  | B of int * list1

位置:

• A代表一个空列表
• B通过在另一个列表前面添加一个int来构建新列表

所以1,2,3,4将用list1值表示:

so 1,2,3,4, will be represented with the list1 value:

B(1, B(2, B(3, B(4, A))))

从Wikibook中，我了解到，通过列表，我可以通过以下操作对元素求和:

From the wikibook I learned that with a list I can sum the elements by doing:

let List.sum [1; 2; 3; 4]

但是我该如何对用户定义的数据类型的元素求和呢?任何提示将不胜感激.

But how do I go about summing the elements of a user defined datatype? Any hints would be greatly appreciated.

我可以利用匹配运算符:

I'm able to take advantage of the match operator:

let rec sumit (l: ilist) : int = 
  match l with
  | (B(x1, A)) -> x1
  | (B(x1, B(x2, A))) -> (x1+x2)

sumit (B(3, B(4, A)))

我得到:

val it : int = 7

如何做到这一点，以便如果我有2个以上的整数，它仍会累加元素(即(B(3，B(4，B(5，A))))变为12?

How can I make it so that if I have more than 2 ints it still sums the elemets (i.e. (B(3, B(4, B(5, A)))) gets 12?

推荐答案

一种解决此类问题的好方法是将您的算法以单词形式或伪代码形式写出，然后一旦确定了算法，就将其转换到F#.在这种情况下，您想对列表求和，如下所示:

One good general approach to questions like this is to write out your algorithm in word form or pseudocode form, then once you've figured out your algorithm, convert it to F#. In this case where you want to sum the lists, that would look like this:

弄清楚算法的第一步是仔细定义问题的规格.我想要一种算法来总结我的自定义列表类型.究竟是什么意思?或者，更具体地说，这对于我的自定义列表类型可以具有的两种不同类型的值(A和B)到底意味着什么?好吧，让我们一次看看它们.如果列表的类型为A，则表示一个空列表，因此我需要确定一个空列表的总和.空列表的总和的最明智的值为0，因此规则为如果列表为A，则总和为0".现在，如果列表的类型为B，那么该列表的总和是什么意思?好吧，类型B列表的总和就是它的int值加上子列表的总和.

The first step in figuring out an algorithm is to carefully define the specifications of the problem. I want an algorithm to sum my custom list type. What exactly does that mean? Or, to be more specific, what exactly does that mean for the two different kinds of values (A and B) that my custom list type can have? Well, let's look at them one at a time. If a list is of type A, then that represents an empty list, so I need to decide what the sum of an empty list should be. The most sensible value for the sum of an empty list is 0, so the rule is "I the list is of type A, then the sum is 0". Now, if the list is of type B, then what does the sum of that list mean? Well, the sum of a list of type B would be its int value, plus the sum of the sublist.

因此，现在我们为list1可以具有的两种类型分别设置一个求和"规则.如果为A，则总和为0.如果为B，则总和为(值+子列表的总和).那条规则几乎逐字地翻译成F#代码！

So now we have a "sum" rule for each of the two types that list1 can have. If A, the sum is 0. If B, the sum is (value + sum of sublist). And that rule translates almost verbatim into F# code!

let rec sum (lst : list1) =
    match lst with
    | A -> 0
    | B (value, sublist) -> value + sum sublist

关于此代码，我需要注意几件事.首先，您可能曾经或可能从未见过的一件事(因为您似乎是F#初学者)是rec关键字.在编写递归函数时，这是必需的:由于有关F#解析器实现方式的内部细节，如果函数要调用自身，则必须在声明函数名称和参数时提前声明.其次，这不是编写sum函数的最佳方法，因为它实际上不是尾部递归的，这意味着如果您尝试对一个真正的真的很长的清单.在学习F#的这一点上，您也许现在不必担心这一点，但是最终您将学到一种有用的技术，可以将非尾递归函数转换为尾递归函数.它涉及添加一个通常称为累加器"的额外参数(有时缩写为acc)，并且上述sum函数的正确尾部递归版本应如下所示:

A couple things I want to note about this code. First, one thing you may or may not have seen before (since you seem to be an F# beginner) is the rec keyword. This is required when you're writing a recursive function: due to internal details in how the F# parser is implemented, if a function is going to call itself, you have to declare that ahead of time when you declare the function's name and parameters. Second, this is not the best way to write a sum function, because it is not actually tail-recursive, which means that it might throw a StackOverflowException if you try to sum a really, really long list. At this point in your learning F# you maybe shouldn't worry about that just yet, but eventually you will learn a useful technique for turning a non-tail-recursive function into a tail-recursive one. It involves adding an extra parameter usually called an "accumulator" (and sometimes spelled acc for short), and a properly tail-recursive version of the above sum function would have looked like this:

let sum (lst : list1) =
    let rec tailRecursiveSum (acc : int) (lst : list1) =
        match lst with
        | A -> acc
        | B (value, sublist) -> tailRecursiveSum (acc + value) sublist
    tailRecursiveSum 0 lst

如果您已经可以理解这一点，那就太好了！如果您还没到那时，请在研究完尾递归后将此答案添加书签，然后再返回，因为这种技术(通过使用内部函数将非尾递归函数转换为尾递归函数函数和一个累加器参数)是非常有价值的，它在F#编程中具有各种应用程序.

If you're already at the point where you can understand this, great! If you're not at that point yet, bookmark this answer and come back to it once you've studied tail recursion, because this technique (turning a non-tail-recursive function into a tail-recursive one with the use of an inner function and an accumulator parameter) is a very valuable one that has all sorts of applications in F# programming.

这篇关于对用户定义的数据类型中的元素求和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！