处理元组流而没有可变性？

Question

所以我想要一个接收Tuple <int,int>数组的函数,并返回相同的类型但具有不同的值.

我想要做的是一个返回这种值的函数:

f( [1,10; 2,20; 3,40; 4,70] ) = [2,10; 3,20; 4,30]

所以你可以看到,第一个数字基本没有变化(除了第一个项目没有被选中),但最后一个数字是当前数字与前一个数字的减法(20 - 10 = 10,40 - 20 = 20, ...).

我试图在F#中提出一个不涉及可变性的算法(使用前一个值的累加器意味着我需要一个可变变量),但我无法弄清楚.这可能吗？

Answer 1

使用内置函数.在这种情况下,您可以使用Seq.pairwise.该函数采用一系列输入并生成包含先前值和当前值的对序列.一旦有了对,就可以使用Seq.map将对转换为结果 - 在您的情况下,获取当前值的ID并从当前值中减去先前的值:

input 
|> Seq.pairwise 
|> Seq.map (fun ((pid, pval), (nid, nval)) -> nid, nval-pval)

请注意,结果是一个sequence(IEnumerable<T>)而不是一个列表 - 只是因为该Seq模块包含一些(有用的)函数.您可以使用将其转换回列表List.ofSeq.

使用显式递归.如果您的任务不适合某些内置函数所涵盖的常见模式之一,那么答案就是使用递归(通常,它会替换函数式中的突变).

为了完整性,递归版本看起来像这样(这不是完美的,因为它不是尾递归的,所以它可能导致堆栈溢出,但它证明了这个想法):

let rec f list = 
  match list with
  | (pid, pval)::(((nid, nval)::_) as tail) ->
      (nid, nval-pval)::(f tail)
  | _ -> []

这需要一个列表并查看列表的前两个元素(pid, pval)和(nid, nval).然后它根据两个元素计算新值(nid, nval-pval),然后递归处理list(tail)的其余部分,跳过第一个元素.如果列表包含一个或多个元素(第二种情况),则不返回任何内容.

可以使用"累加器"技巧编写尾递归版本.newValue::(recursiveCall ...)我们不是写作,而是将新生成的值累积在作为参数保留的列表中,然后将其反转:

let rec f list acc = 
  match list with
  | (pid, pval)::(((nid, nval)::_) as tail) ->
      f tail ((nid, nval-pval)::acc)
  | _ -> List.rev acc

现在你只需要调用函数f input []来初始化累加器.