Can `A => List[B]` be transformed into a `List[A => B]`?

user_8475974 0
Viewed 107

I am trying to find an implementation for this Scala function signature:

def explode[A, B](f: A => List[B]): List[A => B]

The opposite direction is possible:

def nest[A, B](fs: List[A => B]): A => List[B] = (a: A) => fs.map(_(a))

By now I am tending to believe the first one (explode) is unimplementable, but I am happy to be proven wrong. If it is indeed not possible to implement, is there a deep reasoning behind it?

In my view, I am essentially asking the compiler to "duplicate" that input A some n times (the Lists size), and "fix" it as input.

function-composition scala function functional-programming types
2 Answers

In my view, I am essentially asking the compiler to "duplicate" that input A some n times (the Lists size), and "fix" it as input.

The problem is you don't know what n is. Consider for example a function that returns a list of all the prime divisors of a number:

def divisors(n: Int): List[Int] = ???

What do you expect explode(divisors) to be? divisors can return a List of any size, depending on its argument, whenever it's invoked in the future. But when you call explode it has to return a List of a fixed size immediately.

Given a fixed type A, the signatures in your code can be written like this:

type F[T] = List[T]
type G[T] = A => T

def nest[B]: F[G[B]] => G[F[B]]
def explode[B]: G[F[B]] => F[G[B]]

nest and explode are reminiscent to sequence operation. It works for nest, because it's possible to write a Traverse instance for a List, but it's not possible to write a Traverse instance for a function A => T. Here is an equivallent question for Haskell, that gives some more insight.

user_10982300

If you want to make some implementation that just satisfies the signature you can do something like this:

def explode[A, B](f: A => List[B]): List[A => B] = {
  Nil
}

def explode[A, B](f: A => List[B]): List[A => B] = {
  List(f.andThen(_.head))
}

But I guess you want something semantically different:

"duplicate" that input A some n times (the Lists size), and "fix" it as input

In that case, there is a problem. The result of f, in the general case, depends on the input A. It could be Nil, finite-size list, or infinite list.

What you can do is only something like:

def explode[A, B](f: A => List[B]): A => List[A => B] = {
  f.andThen(_.map(b => (_: A) => b)
}
user_140443710
Related