I am new to scala and I now the basic of it. Due to my internet research I found this blog post about inverse Btree's. I do understand most of it but this section:

def fold[A, B](t:Tree[A] , z:B)(f:(B,A,B) => B): B = t match {
  case EmptyTree => z
  case Node(x,l,r) => f ( fold( l , z )(f) , x , fold( r , z )(f) )
}

What does this (f:(B,A,B) => B) mean? And also why do I need to enclose it here f ( fold( l , z )(f) , x , fold( r , z )(f) ) and after the recursion call?

CodePudding user response：

In Scala, fold is generally provided as a shorthand for a "reduce to a single value" expression that would otherwise be accomplished via pattern matching.

For example, Option#fold is essentially

// in Option[A]
def fold[B](ifEmpty: => B)(f: A => B): B = this match {
  case None => ifEmpty
  case Some(a) => f(a)
}

and Either#fold is essentially

// in Either[A, B]
def fold[C](fa: A => C, fb: B => C): C = this match {
  case Left(a) => fa(a)
  case Right(b) => fb(b)
}

and List.foldLeft is essentially

def foldLeft[B](z: B)(op: (B, A) => B) = this match {
  case Nil => z
  case head :: tail => tail.foldLeft(op(z, head))(op) // recursion!
}

(disclaimer: I didn't take these from the Scala source, this is just from my own understanding of the methods)

The general goal of a fold is to reduce the collection (i.e. Option / Seq/ Either / Tree) to a single value based on the f function(s) that you pass to it. The f is an anonymous function which typically serves the role of a "transformation for when the value is available" or a "combine next input with previous/recursive result" operation.

In the case of the Tree class from the blog post, Tree is a recursive data structure, so naturally reducing it to a single value will involve some recursion. That's why you see fold( l , z )(f) and fold( r , z )(f) inside the fold implementation. These are computing the fold results (of type B) for the node's left and right sub-trees. Then the f is used to combine those results with the node's own value (of type A).

It may help to rearrange and rename things:

def fold[A, B](tree: Tree[A], ifEmpty: B)(combine: (B, A, B) => B): B = t match {
  case EmptyTree => ifEmpty
  case Node(value, left, right) =>
    // recurse into `left` and `right`
    val leftResult = fold(left, ifEmpty)(combine)
    val rightResult = fold(right, ifEmpty)(combine)
    combine(leftResult, value, rightResult)
}

In the blog post, the author defined def size as an example usage of fold:

def size[T] (tree: Tree[T]) =
  fold(tree, 0: Int){(l,x,r) => l   r   1}

This might make more sense as

def size[T](tree: Tree[T]): Int =
  fold(tree, 0){ (leftSize, x, rightSize) => leftSize   rightSize   1 }

The conclusion of the blog post uses B = Tree[A] in its fold call to accomplish the tree inversion. The combine (i.e. f) function takes the already-inverted left and right sub-trees, and constructs a new Node that puts them in the opposite positions. The fold implementation takes care of the recursion and just calls your f / combine function to piece things together.

CodePudding user response：

The term you're looking for is called currying, in honor of Haskell Curry.

In Scala, functions can have multiple argument lists. You can think of the declaration

def fold[A, B](t:Tree[A] , z:B)(f:(B,A,B) => B): B

as being very similar to

def fold[A, B](t:Tree[A] , z:B, f:(B,A,B) => B): B

It's really just a function of three arguments. But treating it as two separate argument lists confers us several benefits.

Partial Application

First, some functions are frequently partially applied in a certain way. For instance, consider the const function, which takes two arguments and returns its first.

def const[A, B](a: A, b: B) = a

As a function of two arguments, it's basically useless. But it can be useful for creating closures. For instance,

{ (b: Any) => const(0, b) }

is a function which always returns zero for any input. And since this is the most common way to use this function, we split it into two argument lists.

def const[A, B](a: A)(b: B) = a

and now we can write const(0) to mean "a constant function of one argument that returns 0 unconditionally". It's the same as what we wrote before but much less wordy.

Implicits

Implicit parameters (or using clauses, as they're called in Scala 3) must have their own argument list. So if a function, say, takes three values and adds them together using a Monoid operation, we would write

def add3[A](a: A, b: A, c: A)(implicit m: Monoid[A]) =
  m.append(a, m.append(b, c))

And then, when we call the function, we can just pass the three explicit arguments and leave the entire second argument list to implicit resolution.

(Of course, in this particular case, context bounds are a shorter way to express the same idea, but that's not always possible)

Function Arguments

This is the use case most directly applicable to your fold function. If we define fold as a function of three arguments in one list, we have to call it something like this.

fold(myTree, myValue, { (b1, a, b2) => ... })

Which is not necessarily the most intuitive notation. But if there's an argument list which consists of only one argument, and that one argument is a function, we can omit the parentheses. So with our two-argument form, we can write

fold(myTree, myValue) {
  (b1, a, b2) => ...
}

Notice how it's starting to look more like if(...) { ... } or while(...) { ... }. We can emulate control constructs with this notation, so it feels more natural in the presence of other Scala code.

We can still choose to call the function with two sets of parentheses, as you noted in your recursive call, but when the person who's using our API calls it, they don't have to if they just want to provide a lambda that looks like a control block.