时间戳

首页 > 解决方案 > 在“Any”类型列表的末尾添加一个元素（Int,Double...）

scala - 在“Any”类型列表的末尾添加一个元素（Int,Double...）

问题描述

我正在尝试在“Any”类型列表（ List[Any] ）的末尾添加一个元素。我想使用递归函数来构建它，想法是“如果我需要这个元素，我会附加它，当迭代结束时，我的列表将完成”。在下面的代码中，想法是“如果元素 'elem' 位于 'l' 的头部，我有一个列表 'l'，我将添加它的位置，保存在 'index' 中，作为列表 'ret 的下一个元素'。否则我将检查下一个元素并且什么都不做（我使用'l :: support...'只是为了匹配返回类型为List [Any]）。当'l'为空时（或Nil）给我列表'ret'。最后'ret'是包含列表'l'中找到的所有元素'elem'的位置的列表。这个非常重要 ：

我尝试使用 "::","+:",":+" 但它们没有用。每次“错误：值 :: 不是类型参数 Any 的成员”时，错误都是相同的。

object find{
    def support[Any](l:List[Any],elem:Any,index:Int,ret:List[Any]):List[Any]={
        if (l==Nil) ret;
        else if(l.head==elem) (l :: support(l.tail,elem,index+1,ret :: (index.asInstanceOf[Any])));
        else (l :: support(l.tail,elem,index+1,ret));       
    }
    def findIndices[Any](l:List[Any],x:Any):List[Any]={//I want to find all the elements "elem" in the list "l"
        val a:List[Any]=support(l,x,0,List[Any]());//I'll build my list using an auxiliary function "support"
        a;
    }
}
object main extends App{
    val l:List[Int]=List(1,2,2,2,2,3,4,5)
    val x:Int=2;
    val f:List[Int]=find.findIndices(l,x)
    println(f)
}

我对所有可行的解决方案持开放态度，但请先尝试回答我的问题并解释你是如何做到的以及为什么这样做。我正在学习这门语言，我来自 C 和 Java。

标签： scalalistrecursion

解决方案

TL;DR 一条线解决方案：

val list = List(1,2,2,2,2,3,4,5)
list.zipWithIndex.filter(_._1 == 2).map(_._2) //  List(1, 2, 3, 4)

或者用大小写符号命名你的变量：

list.zipWithIndex.filter { case(value,index) => value == 2 } map { case(value,index) => index }

或者使用 collect 方法将 filter 和 map 结合起来：

list.zipWithIndex.collect { case (value,index) if value == 2 => index }

递归

如果你真的需要使用递归，有一个简单的方法和一个困难的方法来做到这一点，看起来你正在尝试以困难的方式来做。在这种情况下，困难的方法是有意义的，但我会先用简单的方法来帮助你展示我在做什么以及为什么。

所以给出一个列表

val list = List(1,2,2,2,2,3,4,5) // named list instead of l because l looks like 1.

我们想要一个findIndices返回findIndices(list,2)的函数List(1,2,3,4)

我将从findIndices这样定义开始：

def findIndices(list: List[Any], element: Any): List[Any] = ???

现在有几件事我想马上改变。首先，您的示例使用单一类型的事物列表，因此这看起来是使用参数化类型的绝佳机会。

def findIndices[T](list: List[T], element: T): List[Any] = ???

第二件事是无论列表中的内容是什么，生成的索引列表都将是整数，因为索引是整数。

def findIndices[T](list: List[T], element: T): List[Int] = ???

所以现在我准备好处理方法的主体了。我知道这需要递归，递归函数的一般形式是：

  1. 检查终止案例。
  2. 处理非终止案件。

所以我的函数看起来像这样：

def findIndices[T](list: List[T], element: T): List[Int] = {
  // if (terminating case) return termination
  // else if (check for next index of element) return index plus recursive call
  // else return recursive call
}

填空会给我们这样的东西：

def findIndices[T](list: List[T], element: T): List[Int] = {
  if (list.isEmpty) List.empty[Int]
  else if (list.head == element) 0 :: findIndices(list.tail, element)
  else findIndices(list.tail, element)
}

不幸的是，这段代码有一个错误。我们正在根据不断缩短的列表而不是原始列表来计算索引。当我们使用越来越短的列表版本时，我们可以通过跟踪索引的偏移量来解决这个问题：

def findIndices[T](list: List[T], element: T, offset: Int = 0): List[Int] = {
  if (list.isEmpty) List.empty[Int]
  else if (list.head == element) offset :: findIndices(list.tail, element, offset + 1)
  else findIndices(list.tail, element, offset + 1)
}

此方法按预期工作......仅适用于小列表。对于非常大的列表，我们将得到堆栈溢出。解决这个问题的方法是使方法尾递归，因此程序在每次调用时不需要跟踪堆栈。这就是您在问题中似乎试图做的事情。我把它称为困难的方式，但是一旦你有了非尾递归函数，将它转换为尾递归函数实际上是相当简单和机械的。

顶层函数参数保持不变：

def findIndices[T](list: List[T], element: T, offset: Int = 0): List[Int] = ???

在第一个函数中，我们定义了一个新函数。这个新函数将具有与旧函数相同的参数，外加一个累加器。这个累加器将允许我们将算法的中间结果向下传递给下一个递归函数调用，因此程序不必维护调用堆栈来跟踪每个中间结果。

我们的外部函数唯一要做的就是使用初始参数调用内部函数。

def findIndices[T](list: List[T], element: T, offset: Int = 0): List[Int] = {

  def findIndicesAcc(list: List[T], element: T, acc: List[Int], offset: Int = 0): List[Int] = {
    // do logic here
  }

  findIndicesAcc(list, element, List.empty[Int])
}

累加器函数内部的逻辑将与原始函数非常相似。它将简单地利用累加器参数，而不是将中间结果留在堆栈上。

def findIndices[T](list: List[T], element: T, offset: Int = 0): List[Int] = {

  def findIndicesAcc(list: List[T], element: T, acc: List[Int], offset: Int = 0): List[Int] = {
    if (list.isEmpty) acc
    else if (list.head == element) findIndicesAcc(list.tail, element, offset + 1, offset :: acc)
    else findIndicesAcc(list.tail, element, offset + 1, acc)
  }

  findIndicesAcc(list, element, List.empty[Int])
}

此功能按预期工作，但我们可以做一些最终的簿记和清理项目。首先，我们可以去掉最外层的offset参数，去掉内层offset参数的默认值。其次，我们可以@tailrec给内部函数添加一个注解，以确保我们已经解决了堆栈溢出问题。第三，如果返回列表中索引的顺序很重要，我们可以在累加器的输出上调用 reverse。

import scala.annotation.tailrec

def findIndices[T](list: List[T], element: T): List[Int] = {

  @tailrec
  def findIndicesAcc(list: List[T], element: T, offset: Int, acc: List[Int]): List[Int] = {
    if (list.isEmpty) acc
    else if (list.head == element) findIndicesAcc(list.tail, element, offset + 1, offset :: acc)
    else findIndicesAcc(list.tail, element, offset + 1, acc)
  }

  findIndicesAcc(list, element, 0, List.empty[Int]).reverse
}

更多关于尾递归

尾递归是指递归函数，其中递归调用是函数中发生的最后一件事。有时您必须仔细查看某些东西是否是尾递归的。例如，代码片段

else if (list.head == element) offset :: findIndices(list.tail, element, offset + 1)

不是尾递归的，因为offset必须在findIndices返回后的结果之前添加。如果我们将代码片段的每个操作分成单独的行，则可以更清楚地说明这一点：

else if (list.head == element) {
  val tail = list.tail      
  val newOffset = offset + 1
  val recursiveResult = findIndices(tail, element, newOffset)
  return offset :: recursiveResult
}

当代码这样分解时，我们可以看到递归findIndices调用返回后还需要做更多的工作。

另一方面，代码片段

else if (list.head == element) findIndicesAcc(list.tail, element, offset + 1, offset :: acc)

是尾递归的。当我们将操作分成单独的行时，我们得到

else if (list.head == element) {
  val tail = list.tail
  val newOffset = offset + 1
  val combinedList = offset :: acc
  return findIndicesAcc(tail, element, newOffset, combinedList)
}

我们可以清楚地看到findIndicesAcc调用是最后发生的事情。

在第一种情况下，程序被迫维护整个调用堆栈，因为它需要记住offset函数的每个先前迭代中的值是什么。在 linux 机器中，我们通常有 8 MB 的堆栈可供使用。对于非常长的列表，我们最终会用完所有 8 MB 的堆栈，这会导致堆栈溢出异常。

在第二种情况下，所有相关数据都被传递给递归函数的下一次迭代。程序需要跟踪的先前函数调用中没有任何内容。编译器能够检测到这一点，并将代码优化成一个循环。在这种情况下，不需要维护调用堆栈，因此没有堆栈溢出异常的风险。

最后一个警告，我尽可能仔细地检查了这段代码，但是当我写这篇文章时我没有使用 scala 编译器，所以我为任何拼写错误道歉。

推荐阅读