scala - 折叠 Stream 算法的惰性解决方案(从结果中取出 K 个元素应该只消耗输入中的 Q 个元素)

Question

我和一些同事提出了一个有趣的问题，并正在争论，但似乎无法找到一个懒惰的解决方案。有吗？

这是在尝试学习函数式编程时出现的，我们想到了用惰性解决方案来扩展简单问题

我将首先介绍非惰性问题(对此我们找到了一个简单的折叠 + flatMap 解决方案)

Let's say we have a word. W

We want to generate all subsets of the word, such that:

For "abcd" the result would be :
"", "a", "b", "ab", "c", "ac", "bc", "abc", "d", "ad", "bd", "abd", "cd", "acd", "bcd", "abcd"

基本上是逐个字符地查找字符并用当前字符组合到目前为止的结果，总是使结果加倍。

问题:

Can we find a lazy solution to this problem ?

Given:

• the input as a Stream of Char

• expected result a Stream of Strings

Can we consume the input stream lazily with just enough data to produce onlythe amount of results we need

这是我迄今为止在 Scala 中的解决方案:

import org.scalatest.{FreeSpec, Matchers}

class Problem extends FreeSpec with Matchers {

  private def solution(word: Stream[Char]) = foldr(compose, Stream(""))(word)

  def compose(letter: Char, results: => Stream[String]): Stream[String] = {
    results append results.map(word => word + letter)
  }

  def foldr[A, B](combine: (A, =>B) => B, base: B)(xs: Stream[A]): B =
    if (xs.isEmpty) base
    else
      combine(xs.head, foldr(combine, base)(xs.tail))

  "Problem" - {

    "Taking 5 elements from the result should evaluate only 3 elements from the initial stream" in {
      solution(
        Stream('a', 'b', 'c', 'd', 'e', 'f').map(
          x => {
            println(s"Applying map on element: '$x'")
            x
          }
        )
      ).take(5).toList shouldBe List("", "f", "e", "fe", "d")
    }
  }

}

我使用了来自此 blogpost 的foldr 实现据我了解，Scala 流不是惰性的 FoldRight？

这个解决方案的问题在于，放在那里进行调试的 map 显示该解决方案并不懒惰

Applying map on element: 'a'
Applying map on element: 'b'
Applying map on element: 'c'
Applying map on element: 'd'
Applying map on element: 'e'
Applying map on element: 'f'

因为它使用流中的所有元素

<小时/>

我尝试过的另一种解决方案是这个:

import org.scalatest.{FreeSpec, Matchers}

class Problem extends FreeSpec with Matchers {

  private def solution(word: Stream[Char]) = word.foldRight(Stream("")) (add)

  def add(letter: Char, results: Stream[String]): Stream[String] = results.flatMap(result =>  {
    println(s"Composing result '$result' with letter: '$letter'")
    Stream(result, letter + result)
  })

  "Problem" - {

    "Taking 5 elements from the result should evaluate only 3 elements from the initial stream" in {
      solution(
        Stream('a', 'b', 'c', 'd', 'e', 'f').map(
          x => {
            println(s"Applying map on element: '$x'")
            x
          }
        )
      ).take(5).toList shouldBe List("", "a", "b", "ab", "c")
    }
  }
}

产生:

Applying map on element: 'a'
Applying map on element: 'b'
Applying map on element: 'c'
Applying map on element: 'd'
Applying map on element: 'e'
Applying map on element: 'f'
Composing result '' with letter: 'f'
Composing result '' with letter: 'e'
Composing result '' with letter: 'd'
Composing result '' with letter: 'c'
Composing result '' with letter: 'b'
Composing result '' with letter: 'a'
Composing result 'b' with letter: 'a'
Composing result 'c' with letter: 'b'
Composing result 'c' with letter: 'a'

<小时/>

我不知道我的方向是否正确。任何形式的帮助将不胜感激。谢谢!

<小时/>

最终解决方案基于 The Archetypal Paul回答

  private def solution(word: Stream[Char]) =
    word.scanLeft((Stream(""), Stream(""))) ((acc, l)=> {
      val r = acc._2.map(_ + l)
      (r, acc._2 append r)
    }).flatMap(_._1)

Answer 1

给你:

val zs= Stream('a','b','c','d')
zs.map( x => {println(s"Applying map on element: '$x'"); x})
  .scanLeft("")((a, b) => a :+ b)
  .flatMap(_.permutations)
  .take(4).toList
  //> Applying map on element: 'a'
  //| Applying map on element: 'b'
  //| Applying map on element: 'c'
  //| res1: List[String] = List("", a, ab, ba)

它比需要的更贪婪(take(5) 计算 d)，但它很懒。