22

foldLeftフォールドに提供される初期値が完全にカリー化された関数であり、演算子がapplyであり、リストが関数に渡される引数のリストである場合、引数のリストに対して a を実行することは可能ですfか?

たとえば、f が次のように定義されているとします。

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

もちろん、直接使用できます。

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

または、一度に 1 つずつ引数をカリー化して適用します。

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

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

一見、これは の仕事のように見えfoldLeftます。

この一連のapply使用方法を説明する最初の試みはfoldLeft次のようになります。

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

ただし、次のエラーが発生します。

<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) })

エラーメッセージを読んだところ、型推論にはg.

私が探しているソリューションでは、次のタイプを除いて、元の式のすべてが変更されていませんg。

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

私が最初に考えたのは、ユニオン型がここで役立つだろうということでした。Miles Sabin が Curry-Howard を使用して共用体型を導出するのを見たことがあります。そのため、最初の予感が正しければ、問題を解決するために必要な基本的な機構を持っているように見えます。

ただし、ユニオン型が答えであっても、「関数の完全にカリー化された型からカリー化された関数の型までのすべての型の結合で、最後の引数がすべて提供されている」を参照できれば便利です。つまり、型を変える方法は次のとおりです。

T1 => ... => Tn

ユニオンタイプに：

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

上記のタイプとして役立ちgます。

a foldLefton a を実行すると、すべてが同じListである場合にのみ議論が制限T1されます。Tn-1みたいな表記

(T1 =>)+ Tn

に提供したいタイプを説明しますg。

私が尋ねている特定のケースでは、任意の長いチェーンは必要ないため、次を使用してイテレータに境界を提供できます

(T1 =>){1,4} Tn

ただし、等しくない型のチェーンに対してこれを実行したい場合は、チェーンをすべての接尾辞のセットに切り刻む型の魔法の関数の方が便利かもしれません。

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

これを実装することは、現時点で私の Scala の能力をはるかに超えています。そうする方法についてのヒントをいただければ幸いです。これが、Scala の既存の型システムを高度に使用するか、コンパイラ プラグインを介して実行できるか、またはそのどちらでもないかはわかりません。

以下のコメントで指摘されているように、結果を「共用体型」と呼ぶことは、このユース ケースには完全に適合しません。他に何と呼べばいいのかわかりませんが、それが現時点で最も近いアイデアです。他の言語はこの考えを特別にサポートしていますか? これは Coq と Agda でどのように機能しますか?

この問題に名前を付けて、全体像 (型理論、決定可能性など) に関してどこに位置するかを理解することは、 の実用的な実装を持つことよりも重要ですがANSWER、どちらも良いことです。Scalaz、Monoids、または圏論全般への接続を描くことができる人にはボーナス ポイントがあります。

4

3 に答える 3

30

これは、最初に予想したよりもかなり単純であることがわかりました。

まず、単純な を定義する必要があります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]

次に、型クラスの助けを借りて、折り畳みのような関数を帰納的に定義できます。

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)

最初に元の例では、次のように使用できます。

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

foldCurryまた、アリティが異なり、引数の型が一様でない関数に対しても、変更されていない同じものを使用できます。

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)
于 2011-11-06T21:48:42.257 に答える
6

関数は正確に 4 つのInt引数を必要とします。foldLeft任意の数の要素に適用される関数です。あなたは言及しますが、またはList(1,2,3,4)がある場合はどうなりますList(1,2,3,4,5)かList()？

List.foldLeft[B]また、関数が同じタイプを返すことを期待してBいますが、あなたのケースIntでは、いくつかFunction1[Int, _]は同じタイプではありません。

どのような解決策を思いついたとしても、一般的ではありません。たとえば、関数のタイプが の場合はどうなります(Int, Float, Int, String) => Intか? 次に、List[Any]

ですから、それは間違いなくの仕事ではありませんList.foldLeft。

それを念頭に置いて（警告は非常に非スカラコードです）：

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
于 2011-09-30T13:46:56.740 に答える
3

わかりました scalaz も解決策もありませんが、説明があります。REPL で f.currried.apply を 1 引数で使用し、次に 2 引数で使用する場合、return-result 型が実際には毎回異なることを観察してください! FoldLeft は非常に単純です。f.curried である開始引数を持つ型に固定されており、 f.curried.apply(1) と同じ署名がないため、機能しません。したがって、開始引数と結果は同じ型でなければなりません。foldLeft の開始合計要素の型は一貫している必要があります。そして、あなたの結果は Int でさえあるので、それは絶対にうまくいきません。お役に立てれば。

于 2011-09-30T07:10:38.657 に答える