Scala 中通用过滤器函数中的错误 [英] Bug in a generic filter function in Scala

问题描述

我正在 Scala 中编写一个过滤器函数，虽然我对我正在尝试做的事情感觉很好，但我不明白为什么它不能识别我的 List 或者这个错误告诉我什么.我尝试编辑语法，但似乎没有任何解决方法

I am writing a filter function in Scala and although I feel good about what I am trying to do I can not figure out why it will not recognize my List or what this bug is telling me. I have tried editing the syntax but nothing seems to fix it

sealed trait List[+A]
case object Empty extends List[Nothing]
case class Cons[A]( x : A, xs : List[A]) extends List[A]

def filter[A](f: A => Boolean, list: List[A]): List[A] =
for { 
    a <- list
    if (f(a)) 
} yield a

<console>:93: error: value filter is not a member of List[A]
   a <- list

在此处查看代码

推荐答案

所以，如果我们首先理解 for comprehensions 是 map、flatMap 和 sugar 语法>过滤器.那么我们可以看到你定义过滤器的尝试相当于:

So, if we first understand that for comprehensions are sugar syntax for map, flatMap and filter. Then we can see that your attempt of defining filter is equivalent to:

list.filter(a => f(a))

这显然没有意义.您不能根据 filter...

Which obviously doesn't make sense. You can not define filter in terms of filter...

嗯，你实际上可以，这就是递归的全部意义，实际上这是解决问题的正确方法.
在模式匹配的额外帮助下.

Well, you actually can, that is what recursion is all about, and actually that is the correct way of solving the problem.
With the extra help of pattern matching.

所以递归函数是处理List这样的递归数据结构的最佳方式.
这个过程实际上很简单，我们需要弄清楚在基本情况下做什么，在递归情况下做什么(这可能需要递归调用).
(注意:我改变了函数签名，这个新签名允许更好的语法和更好的类型推断)

So a recursive function is the best way to process a recursive data structure like List.
The process is actually quite straight forward, we need to figure out what to do in the base case and what to do in the recursive case (which probably will require a recursive call).
(note: I changed the function signature, this new signature allows better syntax and better type inference)

/** Returns a new list with only the elements that satisfied the predicate. **/
def filter[A](list: List[A])(p: A => Boolean): List[A] = list match {
  case Empty => ??? // Base case. Tip: tink in what is the filter of an empty list.
  case Cons(a, tail) => ??? // Recursive case. Tip: you probably will need to call the function recursively.
}

一旦你填满了这些洞，你就会有一个合适的过滤功能.但是，我们遇到了一个问题，因为这是一个递归解决方案，尝试过滤一个非常大的列表会导致 StackOverflowError 这并不理想，那么我们该怎么办?
尾递归来救援！

Once you fill the holes, you will have a proper filter function. But, we got a problem, since this is a recursive solution, trying to filter a very big list will result in a StackOverflowError which is not ideal, so what can we do?
Tail-Recursion to the rescue!

想法很简单，我们需要保留一个累加器来保存中间值.
(注意:保持尾部函数作为内部函数通常是个好主意)

The idea is simple, we need to keep an accumulator for holding intermediate values.
(note: it is usually a good idea to keep the tail function as an inner function)

/** Returns a new list with only the elements that satisfied the predicate. **/
def filter[A](list: List[A])(p: A => Boolean): List[A] = {
  @annotation.tailrec
  def loop(remaining: List[A], acc: ???): List[A] =
    remaining match {
      case Cons(a, as) => ??? // Recursive case.
      case Empty => ??? // Base case, we are done! Tip: Is the output correct?
    }

  loop(remaining = list, acc = ???)
}

一旦你填补了这些漏洞，你就会有一个很好的filter功能.

Once you fill the holes, you will have a good filter function.

(最后一点:遵循一种名为 输入俄罗斯方块可能有助于获得正确的解决方案)

这篇关于Scala 中通用过滤器函数中的错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！