Applying an argument list to curried function using foldLeft in Scala

Question

Is it possible to do a foldLeft on a list of arguments, where the initial value supplied to the fold is a fully curried function, the operator is apply, and the list is a list of arguments to be passed to function f?

For example, let's say f is defined as:

scala> val f = (i: Int, j: Int, k: Int, l: Int) => i+j+k+l
f: (Int, Int, Int, Int) => Int = <function4>

Which we can of course use directly:

scala> f(1, 2, 3, 4)
res1: Int = 10

Or curry and apply the arguments one at a time:

scala> f.curried
res2: Int => Int => Int => Int => Int = <function1>

scala> f.curried.apply(1).apply(2).apply(3).apply(4)
res3: Int = 10

At first glance this looks like a job for foldLeft.

My first attempt at describing this sequence of apply using foldLeft looks like:

scala> List(1, 2, 3, 4).foldLeft(f.curried)({ (g, x) => g.apply(x) })

However, that yields the following error:

<console>:9: error: type mismatch;
 found   : Int => Int => Int => Int
 required: Int => Int => Int => Int => Int
              List(1, 2, 3, 4).foldLeft(f.curried)({ (g, x) => g.apply(x) })

My reading of the error message is that type inference would need some hint for g.

The solution I'm looking for leaves everything unmodified in my original expression except the type of g:

List(1, 2, 3, 4).foldLeft(f.curried)({ (g: ANSWER, x) => g.apply(x) })

My first thought was that a union type would be useful here. I've seen Miles Sabin's derivation of union types using Curry-Howard, so if that first hunch is true, then I appear to have the basic machinery required to solve the problem.

However: Even if union types are the answer it would be useful if I could refer to "The union of all types from the fully curried type of a function to the type of the curried function with all but the last argument supplied". In other words, a way to turn the type:

T1 => ... => Tn

into the union type:

(T1 => ... => Tn) |∨| ... |∨| (Tn-1 => Tn)

would be useful as the type for g above.

Doing a foldLeft on a List limits the discussion to case where T1 through Tn-1 are all the same. A notation like

(T1 =>)+ Tn

would describe the type I want to provide for g.

The specific case I'm asking about doesn't require arbitrarily long chains, so we could provide bounds on the iterator using

(T1 =>){1,4} Tn

Looking ahead at wanting to do this for chains of types that are not equal, though, perhaps some magical function on types that chops up the chain into the set of all suffixes is more useful:

Suffixes(T1 => ... => Tn)

Implementing this is well beyond my Scala abilities at the moment. Any hints as to how to go about doing so would be appreciated. Whether this can be done with advanced usage of Scala's existing type system or through a compiler plugin or neither, I do not know.

As has been noted in the comments below, calling the result a "union type" is not a perfect fit for this use case. I don't know what else to call it, but that's the closest idea I have at the moment. Do other languages have special support for this idea? How would this work in Coq and Agda?

Naming this problem and understanding where it sits with respect to the bigger picture (of type theory, decidability, and so forth) is more important to me than having a working implementation of ANSWER, though both would be nice. Bonus points to anyone who can draw connections to Scalaz, Monoids, or Category Theory in general.

Cyrille

I'm not sure that union types are the way to go here. It seems like you're after a fold-like thing of the curried function over the arguments represented as an HList. I think that something like that is probably doable. Anyhow, it's an interesting problem ... I'll investigate and answer properly if I come up with anything workable. – Stovepipe

Wow -- thanks, Miles. I'd love to hear what you make of this problem. I agree that union types, per se, seem to be not exactly what is called for in this situation. – Cyrille

@MilesSabin I've clarified my question and posited some forms that an answer might take. I'm still unclear whether this is or should be possible, but either way this has been a good exercise for me to talk this through. – Cyrille

Answer 1

This turns out to be quite a bit simpler than I initially expected.

First we need to define a simple HList,

sealed trait HList

final case class HCons[H, T <: HList](head : H, tail : T) extends HList {
  def ::[H1](h : H1) = HCons(h, this)
  override def toString = head+" :: "+tail.toString
}

trait HNil extends HList {
  def ::[H1](h : H1) = HCons(h, this)
  override def toString = "HNil"
}

case object HNil extends HNil
type ::[H, T <: HList] = HCons[H, T]

Then we can define our fold-like function inductively with the aid of a type class,

trait FoldCurry[L <: HList, F, Out] {
  def apply(l : L, f : F) : Out
}

// Base case for HLists of length one
implicit def foldCurry1[H, Out] = new FoldCurry[H :: HNil, H => Out, Out] {
  def apply(l : H :: HNil, f : H => Out) = f(l.head)
}

// Case for HLists of length n+1
implicit def foldCurry2[H, T <: HList, FT, Out]
  (implicit fct : FoldCurry[T, FT, Out]) = new FoldCurry[H :: T, H => FT, Out] {
    def apply(l : H :: T, f : H => FT) = fct(l.tail, f(l.head))
}

// Public interface ... implemented in terms of type class and instances above
def foldCurry[L <: HList, F, Out](l : L, f : F)
  (implicit fc : FoldCurry[L, F, Out]) : Out = fc(l, f)

We can use it like this, first for your original example,

val f1 = (i : Int, j : Int, k : Int, l : Int) => i+j+k+l
val f1c = f1.curried

val l1 = 1 :: 2 :: 3 :: 4 :: HNil

// In the REPL ... note the inferred result type
scala> foldCurry(l1, f1c)
res0: Int = 10

And we can also use the same unmodified foldCurry for functions with different arity's and non-uniform argument types,

val f2 = (i : Int, s : String, d : Double) => (i+1, s.length, d*2)
val f2c = f2.curried

val l2 = 23 :: "foo" :: 2.0 :: HNil

// In the REPL ... again, note the inferred result type
scala> foldCurry(l2, f2c)
res1: (Int, Int, Double) = (24,3,4.0)

Stovepipe

Answer 2

Your function expects exactly 4 Int arguments. foldLeft is a function that applies to an arbitrary number of elements. You mention List(1,2,3,4) but what if you have List(1,2,3,4,5) or List()?

List.foldLeft[B] also expects a function to return the same type B, but in your case Int and some Function1[Int, _] is not the same type.

Whatever solution you come up with would not be general either. For instance what if your function is of type (Int, Float, Int, String) => Int? You would then need a List[Any]

So it's definitely not a job for List.foldLeft.

With that in mind (warning very un-scala code):

class Acc[T](f: Function1[T, _]) {
  private[this] var ff: Any = f
  def apply(t: T): this.type = {
    ff = ff.asInstanceOf[Function1[T,_]](t)
    this
  }
  def get = ff match { 
    case _: Function1[_,_] => sys.error("not enough arguments")
    case res => res.asInstanceOf[T]
  }
}

List(1,2,3,4).foldLeft(new Acc(f.curried))((acc, i) => acc(i)).get
// res10: Int = 10

Severalty

Thank you, @huynjl. I've clarified my question to state that I'm looking for an answer that doesn't modify my original expression except for adding a type for g, but this certainly gets the job done. Regarding the lack of generality and the limitations of List.foldLeft -- can we define some "fold-like thing" (to use Sabin's phrase) that works just as well on tuples? – Cyrille

I've been thinking about the 4-ness of my particular example. While it's true that infinitely long type signatures are not possible (that I know of) in Scala, and that the usual use of foldLeft is rarely if ever limited by the zero, it's exactly that quality of this example that makes it interesting. I can imagine many contrived but valid situations where the zero or the operator halt execution before the input is consumed, but this is a case that's actually interesting and useful (imho). – Cyrille

@AdamPingel, without bring infinite lists in the picture, it was an interesting problem already without an obvious solution. I think the HList avenue that Miles suggest is an interesting one. – Severalty

@AdamPingel, I'm going to be honest here... You lost me at "limited by the zero". – Severalty

@huynjl Trying to adopt some of the language I've seen in Scalaz. In this case I hope I'm using "zero" along these lines: github.com/scalaz/scalaz/blob/master/core/src/main/scala/scalaz/… – Cyrille

Answer 3

Ok no scalaz and no solution but an explanation. If you use your f.curried.apply with 1 and then with 2 arguments in the REPL observe the return-result types DO actually differ each time! FoldLeft is quite simple. It's fixed in it's type with your starting argument which is f.curried and since that has not the same signature as f.curried.apply(1) it doesn't work. So the starting argument and the result HAVE to be of the same type. The type hast to be consistent for the starting-sum element of foldLeft. And your result would be even Int so that would absolutely not work. Hope this helps.

Surtax

I guess my question may reduce to "Does Scala support union types?" And if so, is there any syntactic sugar for referring to "The union of all types from the fully curried type of a function to the type of f with all but the last argument supplied"? – Cyrille

Directly using Sabin's notation in this case would be cumbersome. If there were a way to turn the "T1 => ... => Tn" type into the union "(T1 => ... => Tn ) v ... v (Tn-1 => Tn)" with some special operator, that would be very useful here. – Cyrille

My mobile prevented me from postage tat link :/ but you can always google that too. There isn't much(yet) material on that topic using scala. – Surtax

Thank you Andreas and @ArjanBlokzijl for your comments. I'm curious if it's possible to extend Sabin's union types as mentioned in my previous comment. (And now included in the original post's update.) – Cyrille