3

我想从列表中提取元素范围，满足以下要求：

  • 范围的第一个元素必须是匹配特定条件的元素之前的元素
  • 范围的最后一个元素必须是匹配特定条件的元素旁边的元素
  • 示例：对于列表 (1,1,1,10,2,10,1,1,1) 和x >= 10我想要获取的条件 (1,10,2,10,1)

这对于命令式编程非常简单，但我只是想知道是否有一些智能的 Scala 函数式方法来实现它。是吗？

4

4 回答 4

3

将它保存在 scala 标准库中，我将使用递归解决这个问题：

def f(_xs: List[Int])(cond: Int => Boolean): List[Int] = {
  def inner(xs: List[Int], res: List[Int]): List[Int] = xs match {
    case Nil => Nil
    case x :: y :: tail if cond(y) && res.isEmpty => inner(tail, res ++ (x :: y :: Nil))
    case x :: y :: tail if cond(x) && res.nonEmpty => res ++ (x :: y :: Nil)
    case x :: tail if res.nonEmpty => inner(tail, res :+ x)
    case x :: tail => inner(tail, res)
  }

  inner(_xs, Nil)
}

scala> f(List(1,1,1,10,2,10,1,1,1))(_ >= 10)
res3: List[Int] = List(1, 10, 2, 10, 1)

scala> f(List(2,10,2,10))(_ >= 10)
res4: List[Int] = List()

scala> f(List(2,10,2,10,1))(_ >= 10)
res5: List[Int] = List(2, 10, 2, 10, 1)

也许在这个解决方案中有一些我没有想到的东西，或者我误解了一些东西，但我想你会明白基本的想法。

于 2013-09-13T10:32:48.957 回答
2

良好的函数式算法设计实践就是将复杂问题分解为更简单的问题。该原则称为分而治之。

从主题问题中提取两个更简单的子问题很容易：

  1. 获取匹配元素之后的所有元素的列表，在此匹配元素之前，在其之前的元素之前。

  2. 获取所有元素的列表，直到最新匹配的元素，然后是匹配元素及其后的元素。

命名的问题很简单，可以实现相应的功能，因此不需要细分。

这是第一个函数的实现：

def afterWithPredecessor
  [ A ]
  ( elements : List[ A ] )
  ( test : A => Boolean ) 
  : List[ A ] 
  = elements match {
      case Nil => Nil
      case a :: tail if test( a ) => Nil // since there is no predecessor
      case a :: b :: tail if test( b ) => a :: b :: tail
      case a :: tail => afterWithPredecessor( tail )( test )
    }

由于第二个问题可以看作是第一个问题的直接逆，因此可以通过反转输入和输出来轻松实现：

def beforeWithSuccessor
  [ A ]
  ( elements : List[ A ] )
  ( test : A => Boolean ) 
  : List[ A ] 
  = afterWithPredecessor( elements.reverse )( test ).reverse

但这里有一个优化版本：

def beforeWithSuccessor
  [ A ]
  ( elements : List[ A ] )
  ( test : A => Boolean ) 
  : List[ A ] 
  = elements match {
      case Nil => Nil
      case a :: b :: tail if test( a ) => 
        a :: b :: beforeWithSuccessor( tail )( test )
      case a :: tail => 
        beforeWithSuccessor( tail )( test ) match {
          case Nil => Nil
          case r => a :: r
        }
    }

最后，将上述函数组合在一起以产生解决您问题的函数变得非常简单：

def range[ A ]( elements : List[ A ] )( test : A => Boolean ) : List[ A ] 
  = beforeWithSuccessor( afterWithPredecessor( elements )( test ) )( test )

测试：

scala> range( List(1,1,1,10,2,10,1,1,1) )( _ >= 10 )
res0: List[Int] = List(1, 10, 2, 10, 1)

scala> range( List(1,1,1,10,2,10,1,1,1) )( _ >= 1 )
res1: List[Int] = List()

scala> range( List(1,1,1,10,2,10,1,1,1) )( _ == 2 )
res2: List[Int] = List(10, 2, 10)

第二个测试返回一个空列表，因为满足谓词的最外层元素没有前任（或后继）。

于 2013-09-15T21:04:23.337 回答
1

拉链和地图救援

val l = List(1, 1, 1, 10, 2, 1, 1, 1)

def test (i: Int) = i >= 10

((l.head :: l) zip (l.tail :+ l.last)) zip l filter {
  case ((a, b), c) => (test (a) || test (b) || test (c) )
} map { case ((a, b), c ) => c }

那应该行得通。我只有我的智能手机，而且距离我可以测试它的任何地方都很远，所以对于任何拼写错误或轻微的语法错误深表歉意

编辑：现在工作。我希望很明显，我的解决方案将列表左右移动以创建两个新列表。当这些被压缩在一起并再次与原始列表一起压缩时，结果是一个元组列表，每个元组都包含原始元素及其邻居的元组。然后，过滤并映射回一个简单的列表就很简单了。

使其成为更通用的功能（并使用collect而不是过滤器->映射）...

def filterWithNeighbours[E](l: List[E])(p: E => Boolean) = l match {
  case Nil => Nil
  case li if li.size < 3 => if (l exists p) l else Nil
  case _ => ((l.head :: l) zip (l.tail :+ l.last)) zip l collect {
    case ((a, b), c) if (p (a) || p (b) || p (c) ) => c
  }
}

这比递归解决方案效率低，但使测试更简单，更清晰。在递归解决方案中匹配正确的模式序列可能很困难，因为模式通常表示所选实现的形状而不是原始数据。使用简单的功能解决方案，每个元素都可以清楚而简单地与其相邻元素进行比较。

于 2013-09-14T15:34:36.687 回答
1 
def range[T](elements: List[T], condition: T => Boolean): List[T] = {
   val first = elements.indexWhere(condition)
   val last  = elements.lastIndexWhere(condition)

   elements.slice(first - 1, last + 2)
}

scala> range[Int](List(1,1,1,10,2,10,1,1,1), _ >= 10)
res0: List[Int] = List(1, 10, 2, 10, 1)

scala> range[Int](List(2,10,2,10), _ >= 10)
res1: List[Int] = List(2, 10, 2, 10)

scala> range[Int](List(), _ >= 10)
res2: List[Int] = List()
于 2013-09-13T12:08:04.943 回答