Haskell do 表示法在 Scala 中没有等效的 for 理解？

Question

考虑以下构建平衡二叉树的 Haskell 代码：

data Tree a = Node a (Tree a) (Tree a) | Empty

build :: Int -> [(Tree Char, Int)] 
build n = do
  let k = (n - 1) `div` 2
  (l, i) <- build k
  (r, j) <- build (n - k - 1)
  let h = i + j + 1
  (Node 'x' l r, h) : [(Node 'x' r l, h) | abs (i - j) == 1]

尝试将其转换为 Scala 3 会产生以下结果：

enum Tree[+A]:
  case Empty
  case Node(value: A, left: Tree[A], right: Tree[A])

object Tree:

  def build(n: Int): List[(Tree[Char], Int)] =
    val k = (n - 1) / 2
    for
      (l, i) <- build(i)
      (r, j) <- build(n - k - 1)
      h = i + j + 1
      xs = if math.abs(i - j) == 1
           then List((Node('x', r, l), h))
           else Nil
    yield (Node('x', l, r), h)

Scala 代码无法编译。这是因为

yield

想要返回一个元组，而不是元组列表。

在 Haskell 中，do 表示法可以使用

return

（或

pure

）将值“提升”到封闭的 monad，或者如果没有使用

return

，则最后一个表达式的值必须已经是该类型封闭的单子。在 Scala 中，

yield

类似于

return

，但不使用

yield

的选项会转换为不返回任何内容的

foreach

。

Scala 代码可以编写如下，以返回一个列表，但它不如使用 for-composition 时那么漂亮。

val k = (n - 1) / 2
build(k).flatMap((l, i) =>
  build(n - k - 1).flatMap { (r, j) =>
    val h = i + j + 1
    val xs =
      if math.abs(i - j) == 1
      then List((Node('x', r, l), h))
      else Nil
    (Node('x', l, r), h) :: xs
  }
)

我还尝试嵌套 for 推导式，但这似乎不是有效的语法。

我的问题是：是否可以使用 for-compression 来获得与 Haskell 代码等效的内容？

Answer 1

我的 Scala 有点生疏，但我想你必须写

object Tree:
  def build(n: Int): List[(Tree[Char], Int)] =
    val k = (n - 1) / 2
    for
      (l, i) <- build(i)
      (r, j) <- build(n - k - 1)
      h = i + j + 1
      x <- (Node('x', l, r), h) :: (if math.abs(i - j) == 1
           then List((Node('x', r, l), h))
           else Nil)
    yield x