12

私は、教会でエンコードされたデータ型を Scala で実装する方法を考え出そうとしています。consttype のファーストクラス関数が必要になるため、ランク n 型が必要なようです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 コンパイラーに型を統一させることができませんでした。

上記の定義が与えられた場合、次のものがコンパイルされるように、nil を定義できますか?

cons(1)(cons(2)(cons(3)(nil)))
4

1 に答える 1

11

このソリューションを完成させてくれた 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は、型をそれ自体にマップする関数の型 ( endofunction ) の単なるエイリアスです。

type Endo[A] = A ->: A

AndFoldは、リストを折りたたむことができる関数のタイプです。

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) に明示的に変換する必要があることです。そのため、一度作成したリストを実際に折りたたむのは、依然として非常に冗長で退屈です。比較のために、同等の 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
于 2010-04-08T23:05:54.430 に答える