0

也许这可能很容易解决，但你能帮助我或指导我找到解决方案吗？我有一个删除函数，它通过一个元组列表“List [（String，Any）]”，当列表被循环时，我试图用 Nil 替换值的 1 索引。

但是当我尝试用 Nil 替换当前的 v 时，它说 v 被分配给“val”。现在我明白 scala 列表是不可变的。所以也许这就是问题所在？

我尝试了 Tail 递归实现，但是当我退出 def 时，类型不匹配。即：是单位但必需：Option[Any]

// remove(k) removes one value v associated with key k
// from the dictionary, if any, and returns it as Some(v).  
// It returns None if k is associated to no value.  
def remove(key:String):Option[Any] = {
    for((k,v) <- d){
        if(k == key){
            var temp:Option[Any] = Some(v)
            v = Nil
            return temp
        } 
    }; None
}

这是试图弄清楚的另一种方法

  def remove(key:String):Option[Any] = {
    def removeHelper(l:List[(String,Any)]):List[(String,Any)] =
      l match {
        case Nil => Nil
        case (k,v)::t => if (key == k) t else (k,v)::removeHelper(t)
      }
    d = removeHelper(d)
  }

有什么建议么？这是学校的家庭作业/项目，我想我可以为那些不喜欢帮助家庭作业的人补充一下。

4

2 回答 2

2

嗯，有很多方法可以回答这个问题。我将在这里用我自己的实现来概述我能想到的那些，但这个列表绝不是详尽的（也可能是最佳的实现）。

首先，您可以尝试使用现有的组合器 - 通常的嫌疑人是map,flatMap和：foldLeftfoldRight

def remove_flatMap(key: String, list: List[(String, Any)]): List[(String, Any)] =
  // The Java developer in me rebels against creating that many "useless" instances.
  list.flatMap {a => if(a._1 == key) Nil else List(a)}

def remove_foldLeft(key: String, list: List[(String, Any)]): List[(String, Any)] =
  list.foldLeft(List[(String, Any)]()) {(acc, a) =>
    if(a._1 == key) acc
    else            a :: acc
  // Note the call to reverse here.
  }.reverse

// This is more obviously correct than the foldLeft version, but is not tail-recursive.
def remove_foldRight(key: String, list: List[(String, Any)]): List[(String, Any)] =
  list.foldRight(List[(String, Any)]()) {(a, acc) =>
    if(a._1 == key) acc
    else            a :: acc
  }

这些问题在于，据我所知，一旦达到某个条件，您就无法阻止它们：我认为它们不会直接解决您的问题，因为它们会删除所有实例key而不是第一个实例。

您还需要注意：

  • foldLeft完成后必须反转列表，因为它以“错误”的顺序附加元素。
  • foldRight没有那个缺陷，但不是尾递归：它会导致大型列表出现内存问题。
  • map不能用于您的问题，因为它只允许我们修改列表的值，但不能修改其结构。

您也可以使用自己的实现。我已经包含了两个版本，一个是尾递归的，一个不是。尾递归的显然更好，但也更冗长（我责怪使用 aList[(String, Any)]而不是的丑陋Map[String, Any]：

def remove_nonTailRec(key: String, list: List[(String, Any)]): List[(String, Any)] = list match {
  case h :: t if h._1 == key => t
  // This line is the reason our function is not tail-recursive.
  case h :: t                => h :: remove_nonTailRec(key, t)
  case Nil                   => Nil
}

def remove_tailRec(key: String, list: List[(String, Any)]): List[(String, Any)] = {
  @scala.annotation.tailrec
  def run(list: List[(String, Any)], acc: List[(String, Any)]): List[(String, Any)] = list match {
    // We've been aggregating in the "wrong" order again...
    case h :: t if h._1 == key => acc.reverse ::: t
    case h :: t                => run(t, h :: acc)
    case Nil                   => acc.reverse
  }

  run(list, Nil)

}

更好的解决方案当然是使用正确的工具来完成这项工作：a Map[String, Any].

请注意，我认为我没有完全回答您的问题：我的示例删除 key，而您想将其设置为Nil。由于这是您的作业，我将让您弄清楚如何更改我的代码以满足您的要求。

于 2013-09-26T09:49:40.827 回答
0

List如果任何键只存在一次，则使用错误的集合。你应该使用Map[String,Any]. 带着清单，

  1. 您必须做额外的工作以防止重复条目。
  2. 检索密钥会更慢，它出现的列表越靠下。尝试检索不存在的键将与列表的大小成比例地变慢。

我猜第 2 点可能是您尝试将其替换为Nil而不是仅从列表中删除密钥的原因。 Nil真的不适合在这里使用。如果您尝试检索与已删除的密钥相比不存在的密钥，您将得到不同的东西。这真的是你想要的吗？回来有多大意义Some(Nil)？

这里有几种适用于可变或不可变列表的方法，但它们并不假设您成功阻止了重复项的蔓延......

val l1: List[(String, Any)] = List(("apple", 1), ("pear", "violin"), ("banana", Unit))
val l2: List[(Int, Any)] = List((3, 1), (4, "violin"), (7, Unit))

def remove[A,B](key: A, xs: List[(A,B)]) = (
  xs collect { case x if x._1 == key => x._2 }, 
    xs map { case x if x._1 != key => x; case _ => (key, Nil) }
)

scala>  remove("apple", l1)
res0: (List[(String, Any)], List[(String, Any)]) = (List((1)),List((apple, List()),(pear,violin), (banana,object scala.Unit)))

scala> remove(4, l2)
res1: (List[(Int, Any)], List[(Int, Any)]) = (List((violin)),List((3,1), (4, List()), (7,object scala.Unit)))

scala> remove("snark", l1)
res2: (List[Any], List[(String, Any)]) = (List(),List((apple,1), (pear,violin), (banana,object scala.Unit)))

这将返回一个匹配值列表（因此是一个空列表，而不是None如果不匹配）和剩余列表，在一个元组中。如果您想要一个完全删除不需要的密钥的版本，请执行此操作...

def remove[A,B](key: A, xs: List[(A,B)]) = (
  xs collect { case x if x._1 == key => x._2 }, 
  xs filter { _._1 != key }
)

但也要看看这个：

scala> l1 groupBy {
         case (k, _) if k == "apple" => "removed",
         case _ => "kept"
       }
res3: scala.collection.immutable.Map[String,List[(String, Any)]] = Map(removed -> List((apple,1)), kept -> List((pear,violin), (banana,object scala.Unit)))

那是你可以发展的东西。您需要做的就是添加("apple", Nil)到“保留”列表并从“删除”列表中提取值。

请注意，我使用的是 List 组合函数，而不是编写自己的递归代码；这通常会使代码更清晰，并且通常与手动递归函数一样快或更快。

另请注意，我不会更改原始列表。这意味着我的函数适用于可变和不可变列表。如果您有一个可变列表，请随时将我返回的列表分配为您的 mutable 的新值var。赢，赢。

但请为此使用地图。看看事情变得多么简单：

val m1: Map[String, Any] = Map(("apple", 1), ("pear", "violin"), ("banana", Unit))
val m2: Map[Int, Any] = Map((3, 1), (4, "violin"), (7, Unit))

def remove[A,B](key: A, m: Map[A,B]) = (m.get(key), m - key)

scala> remove("apple", m1)
res0: (Option[Any], scala.collection.immutable.Map[String,Any]) = (Some(1),Map(pear -> violin, banana -> object scala.Unit))

scala> remove(4, m2)
res1: (Option[Any], scala.collection.immutable.Map[Int,Any]) = (Some(violin),Map(3 -> 1, 7 -> object scala.Unit))

scala> remove("snark", m1)
res2: res26: (Option[Any], scala.collection.immutable.Map[String,Any]) = (None,Map(apple -> 1, pear -> violin, banana -> object scala.Unit))

组合函数使事情变得更容易，但是当你使用正确的集合时，它变得如此简单，以至于几乎不值得编写一个特殊的函数。当然，除非你试图隐藏数据结构——在这种情况下，你真的应该把它隐藏在一个对象中。

于 2013-09-26T14:49:18.653 回答