閉鎖と普遍的な定量化
-
25-09-2019 - |
質問
私は、Scalaで教会がエンコードされたデータ型を実装する方法を考えようとしています。一流が必要なので、rank-nタイプが必要だと思われます const
タイプの関数 forAll a. a -> (forAll b. b -> b)
.
しかし、私はペアをエンコードすることができました:
import scalaz._
trait Compose[F[_],G[_]] { type Apply = F[G[A]] }
trait Closure[F[_],G[_]] { def apply[B](f: F[B]): G[B] }
def pair[A,B](a: A, b: B) =
new Closure[Compose[({type f[x] = A => x})#f,
({type f[x] = B => x})#f]#Apply, Id] {
def apply[C](f: A => B => C) = f(a)(b)
}
リストについては、エンコードすることができました cons
:
def cons[A](x: A) = {
type T[B] = B => (A => B => B) => B
new Closure[T,T] {
def apply[B](xs: T[B]) = (b: B) => (f: A => B => B) => f(x)(xs(b)(f))
}
}
ただし、空のリストはより問題があり、Scalaコンパイラにタイプを統合することができませんでした。
上記の定義を考慮して、次のコンパイルを定義することができますか?
cons(1)(cons(2)(cons(3)(nil)))
解決
このソリューションを完了してくれたMark Harrahに感謝します。トリックはそれです Function1
標準ライブラリでは、一般的な方法で定義されていません。
質問の私の「閉鎖」特性は、実際にはファンクター間の自然な変換です。これは、「関数」の概念の一般化です。
trait ~>[F[_],G[_]] { def apply[B](f: F[B]): G[B] }
機能 a -> b
その後、この特性の専門化、SCALAタイプのカテゴリ上の2人のエンドカクター間の自然な変換である必要があります。
trait Const[A] { type Apply[B] = A }
type ->:[A,B] = Const[A]#Apply ~>: Const[B]#Apply
Const[A]
あらゆるタイプをマッピングするファンチャーです A
.
そして、これが私たちのリストタイプです:
type CList[A] = ({type f[x] = Fold[A,x]})#f ~> Endo
ここ、 Endo
タイプを自分にマッピングする機能のタイプのエイリアスです( エンド機能).
type Endo[A] = A ->: A
と Fold
リストを折り畳むことができる関数のタイプです。
type Fold[A,B] = A ->: Endo[B]
そして最後に、ここに私たちのリストコンストラクターがあります:
def cons[A](x: A) = {
new (CList[A] ->: CList[A]) {
def apply[C](xs: CList[A]) = new CList[A] {
def apply[B](f: Fold[A,B]) = (b: B) => f(x)(xs(f)(b))
}
}
}
def nil[A] = new CList[A] {
def apply[B](f: Fold[A,B]) = (b: B) => b
}
1つの警告は、Scalaのタイプシステムを支援するために(a->:b)に明示的に(a->:b)に(a => b)に変換する必要があることです。したがって、作成された後に実際にリストを折り畳むことは、まだひどく冗長で退屈です。比較のための同等のHaskellは次のとおりです。
nil p z = z
cons x xs p z = p x (xs p z)
Haskellバージョンの構造と折りたたみをリストするのは簡潔でノイズフリーです。
let xs = cons 1 (cons 2 (cons 3 nil)) in xs (+) 0