الإغلاق والقياس العالمي

Question

لقد كنت أحاول معرفة كيفية تنفيذ أنواع البيانات المشفرة للكنيسة في Scala. يبدو أنه يتطلب أنواع رتبة 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))
  }
}

ومع ذلك ، فإن القائمة الفارغة أكثر إشكالية ولم أتمكن من الحصول على مترجم سكالا لتوحيد الأنواع.

هل يمكنك تحديد NIL ، بحيث ، بالنظر إلى التعريف أعلاه ، يجمع ما يلي؟

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

Answer 1

بفضل مارك هاره لإكمال هذا الحل. الحيلة هي ذلك Function1 في المكتبات القياسية لم يتم تعريفها بطريقة عامة بما فيه الكفاية.

سمة "الإغلاق" في السؤال هي في الواقع تحول طبيعي بين المسلسلات. هذا هو تعميم مفهوم "الوظيفة".

trait ~>[F[_],G[_]] { def apply[B](f: F[B]): G[B] }

وظيفة a -> b ثم يجب أن يكون تخصصًا لهذه الصفة ، وهو تحول طبيعي بين اثنين من الجهاز الداخلي على فئة أنواع Scala.

trait Const[A] { type Apply[B] = A }
type ->:[A,B] = Const[A]#Apply ~>: Const[B]#Apply

Const[A] هو functor الذي يرسم كل نوع 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
}

تحذير واحد هو الحاجة إلى تحويل بشكل صريح (A ->: B) إلى (A => B) لمساعدة نظام نوع Scala على طول. لذلك لا يزال مطوّلًا بشكل رهيب ومملة أن طي القائمة بمجرد إنشائها. إليك ما يعادل هاسكل للمقارنة:

nil p z = z
cons x xs p z = p x (xs p z)

القائمة البناء والطي في إصدار Haskell هو terse وخالي من الضوضاء:

let xs = cons 1 (cons 2 (cons 3 nil)) in xs (+) 0