再帰関数-独自の数学の作成（Scala）

こんにちは、Habr！



このような大げさなタイトルで、多くの計算モデル（計算モデル）の1つ- 再帰関数に関する記事を始めたいと思います 。 この投稿の最初の部分では（要するに、すべてがウィキペディアで詳述されているため）このモデルの理論的要素（原始再帰）を分析し、後半ではScala言語を使用してこのモデルを（部分的に）実装しようとします。

1.再帰関数-それは何ですか？

誰もが「チューリングマシン」というフレーズを知っています。これは、英国の数学者、論理学者、暗号学者、そしてただの良き人アランチューリングによって作成された計算モデルです。 このモデルは多くの中で最も有名で人気のある微積分モデルの1つです。 しかし、最近、ラムダ計算やミュー再帰などの他のモデルが一般的になり始めています。



それでも、再帰関数とは何ですか？

目の前に、2つの数値の加算、減算、微分、積分などの操作を（まだ）知らない抽象的なコンピューターがあると想像してください。 そのようなマシンでの作業方法は？ 彼女に数えることを教える方法は？

まず、このマシンに必要な基本機能を定義します。

• 基本的な数学関数のセット：
  
  
  
  -ゼロ（x）= 0：指定された引数xごとに、関数は0を返します
  
  
  
  -Succ（x）= x + 1：指定されたxごとに、関数はx + 1を返します
  
  
  
  -投影関数のファミリー どこで ：任意のn引数に対して、m位置にある引数を返します。
  
  
• これらの機能に適用できる一連の操作：
  
  
  
  -関数の合成（重ね合わせ）：（f•g）（x）= f（g（x））;
  
  
  
  -プリミティブ再帰：n個の変数の関数f（x1、x2、...、xn）とn + 2個の変数の関数g（X1、X2、...、Xn、Xn + 1、Xn + 2）があるとします。 次に、n + 1変数の関数h（X1、X2、.... Xn、Xn + 1）を定義できます。
  
  
  
  h（X1、X2、...、Xn、0）= f（X1、X2、...、Xn）;
  
  h（X1、X2、...、Xn、i + 1）= g（X1、X2、...、Xn、i、h（X1、X2、...、Xn、i））;
  
  

私たちの抽象的なコンピューターでできることはそれだけです。 このリストの主なものは、あなたが推測したように、原始的な再帰です。 より明確にするために、たとえば、2つの数値aとbを追加する機能を実装するようにタスクを設定します。



合計（a、b）：

合計（a、0）= I（a）;

Sum（a、i + 1）= Succ（F（a、i、Sum（a、i）））ここで、Fは3番目の引数の射影です。つまり、この場合、FはSum（a、i）を返します。



それだけです！ これで、2つの数字を追加できます。これについて非常に満足しています。

ところで、誰かに質問があるかもしれません。なぜSum（a、i + 1）を描くのがそんなに難しいのか、そして単にSum（a、i + 1）= Succ（Sum（a、i））と書かないのか。 私は答えます：定義により、再帰関数は、引数として目的の関数（この場合はa）のすべての引数（反復を除く）、また、1つ減った反復引数（この場合はi）、および実際に再帰呼び出しSum（a 、i）。 これは、非プリミティブな再帰で動作できるようにするために行われます（反復は2つ以上の引数に従います）。



あなたが理解するように、同じ方法で、抑制、程度などの関数を作成できます。 これらの例はすべてウィキペディアに非常によく描かれており、記事の後半で実装します。 いずれにせよ、プリミティブな再帰関数の無限のセットをすでに定義できます。



F = {f0、f1、f2、f3、...}は、次のように定義された無限のカウント可能な関数のセットです。



f0（0、y）= Succ（y）;

f [n + 1]（x、y）：f [n + 1]（0、y）= y; f [n + 1]（i + 1、y）= fn（y、f [n + 1]（i、y））;



これはプリミティブな再帰です。

深く掘り下げてμ再帰関数とは何であるかを説明しません。特に、原始再帰は独自の...数学を実装するのに十分であるため、すべてがウィキペディアに非常にうまく描かれています。

2. Scalaでのプリミティブな再帰

まず、数字とは何かを判断する必要がありますか？ 抽象クラスMyNumberを作成します。

abstract class MyNumber { val isNatural: Boolean val isNeg: Boolean val isZero: Boolean val isInf: Boolean def +(b: MyNumber): MyNumber def -(b: MyNumber): MyNumber def *(b: MyNumber): MyNumber def /(b: MyNumber): MyNumber def ^(b: MyNumber): MyNumber def <(b: MyNumber): Boolean def >(b: MyNumber): Boolean def ==(b: MyNumber): Boolean def neg: MyNumber def abs: MyNumber def pre: MyInteger def suc: MyInteger val num: MyInteger val denum: MyInteger def gcd(b: MyNumber): MyNumber def mod(b: MyInteger): MyNumber override def toString(): String def toInteger: MyInteger = if(isNatural) this.asInstanceOf[MyInteger] else (num / denum).asInstanceOf[MyInteger] def toFraction: Fraction = if(isNatural) new Fraction(this.toInteger) else this.asInstanceOf[Fraction] }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

すでに見たように、FractionとMyIntegerの2つの子クラスがあります。

 abstract class MyInteger extends MyNumber { val isNatural = true val isNeg: Boolean val isZero: Boolean val isInf: Boolean def +(b: MyNumber): MyNumber = if (b.isNatural) this plusInt b.toInteger else this plusFrac b.toFraction protected def plusInt(b: MyInteger): MyNumber private def plusFrac(b: Fraction): MyNumber = this.toFraction + b def -(b: MyNumber): MyNumber = if (b.isNatural) this minusInt b.toInteger else this minusFrac b.toFraction protected def minusInt(b: MyInteger): MyNumber private def minusFrac(b: Fraction): MyNumber = this.toFraction - b def *(b: MyNumber): MyNumber = if (b.isNatural) this multInt b.toInteger else this multFrac b.toFraction protected def multInt(b: MyInteger): MyNumber private def multFrac(b: Fraction): MyNumber = this.toFraction * b def /(b: MyNumber): MyNumber = if (b.isNatural) this divInt b.toInteger else this divFrac b.toFraction protected def divInt(b: MyInteger): MyNumber private def divFrac(b: Fraction): MyNumber = this.toFraction / b def ^(b: MyNumber): MyNumber = if (b.isNatural) this powInt b.toInteger else this powFrac b.toFraction protected def powInt(b: MyInteger): MyNumber protected def powFrac(b: Fraction): MyNumber //TODO def <(b: MyNumber): Boolean = if (b.isNatural) this lessThanInt b.toInteger else this lessThanFrac b.toFraction protected def lessThanInt(b: MyInteger): Boolean private def lessThanFrac(b: Fraction): Boolean = this.toFraction < b def >(b: MyNumber): Boolean = if (b.isNatural) this biggerThanInt b.toInteger else this biggerThanFrac b.toFraction protected def biggerThanInt(b: MyInteger): Boolean private def biggerThanFrac(b: Fraction): Boolean = this.toFraction > b def ==(b: MyNumber): Boolean = if (b.isNatural) this equalsInt b.toInteger else this equalsFrac b.toFraction protected def equalsInt(b: MyInteger): Boolean private def equalsFrac(b: Fraction): Boolean = this.toFraction == b def pre: MyInteger def suc: MyInteger val num: MyInteger = null val denum: MyInteger = null def neg: MyNumber def abs: MyNumber = if (!isNeg || isZero) this else this neg def gcd(b: MyNumber): MyNumber = if (b.isNatural) this gcdPrivate b.abs.toInteger else (new Zero).pre private def gcdPrivate(b: MyNumber): MyNumber = { def iter(a: MyNumber, b: MyNumber): MyNumber = { if (b == (new Zero)) a else iter(b, a.toInteger mod b.toInteger) } iter(this, b) } def mod(b: MyInteger): MyNumber = { def iter(a: MyNumber, b: MyNumber): MyNumber = { if (b.isNeg) this mod b.abs.toInteger else if (!b.isNatural) (new Zero).pre else if (a < b) if (a.isNeg) a + b else a else iter(if (a.isNeg) a + b else a - b, b) } iter(this, b) } override def toString: String = { def iter(nb: MyInteger, accu: Int): Int = { if (nb isZero) accu else if (nb isNeg) iter(nb.suc.toInteger, accu - 1) else iter(nb.pre.toInteger, accu + 1) } if(this.isInf) "Inf" else iter(this, 0).toString() } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

整数を定義するには、次の数（Suc）、前（Pre）、ゼロ（Zero）、および無限（PosInf）の概念が必要です。

 class Zero extends MyInteger { val isZero = true val isNeg = false val isInf = false protected def plusInt(b: MyInteger): MyNumber = b protected def minusInt(b: MyInteger): MyNumber = b neg protected def multInt(b: MyInteger): MyNumber = this protected def divInt(b: MyInteger): MyNumber = if (b.isZero) new PosInf else if(b.isInf) new Zero else this protected def powInt(b: MyInteger): MyNumber = this.suc protected def powFrac(b: Fraction): MyNumber = this.suc protected def lessThanInt(b: MyInteger): Boolean = !b.isNeg && !b.isZero protected def biggerThanInt(b: MyInteger): Boolean = b.isNeg && !b.isZero protected def equalsInt(b: MyInteger): Boolean = b.isZero def pre: MyInteger = new Pre(this) def suc: MyInteger = new Suc(this) def neg = this } class PosInf extends MyInteger { val isZero = false val isNeg = false val isInf = true protected def plusInt(b: MyInteger): MyNumber = this protected def minusInt(b: MyInteger): MyNumber = this protected def multInt(b: MyInteger): MyNumber = this protected def divInt(b: MyInteger): MyNumber = this protected def powInt(b: MyInteger): MyNumber = this protected def powFrac(b: Fraction): MyNumber = this protected def lessThanInt(b: MyInteger): Boolean = false protected def biggerThanInt(b: MyInteger): Boolean = true protected def equalsInt(b: MyInteger): Boolean = b.isInf def pre: MyInteger = this def suc: MyInteger = this def neg = this } class Pre(nb: MyInteger) extends MyInteger { val isZero = false val isNeg = true val isInf = false protected def plusInt(b: MyInteger): MyNumber = { def iter(b: MyInteger, accu: MyNumber): MyNumber = { if (b isNeg) this - (b neg) else if (b isZero) accu else iter(b.pre, accu.suc) } iter(b, this) } protected def minusInt(b: MyInteger): MyNumber = { def iter(b: MyInteger, accu: MyNumber): MyNumber = { if (b isNeg) (this + (b neg)) else if (b isZero) accu else iter(b.pre, accu.pre) } iter(b, this) } protected def multInt(b: MyInteger): MyNumber = { (this.neg * b).neg } protected def divInt(b: MyInteger): MyNumber = if (b.isZero) new PosInf else if(b.isInf) new Zero else if (b.isNeg) this.abs / b.abs else (this.abs / b).neg protected def powInt(b: MyInteger): MyNumber = if(b!=new Zero)(this.neg ^ b).neg else (new Zero).suc protected def powFrac(b: Fraction): MyNumber = (new Zero).pre //TODO protected def lessThanInt(b: MyInteger): Boolean = { def iter(a: MyInteger, b: MyInteger): Boolean = a.isZero || b.isZero match { case true => !(a isZero) && (b isZero) case false => iter(a.suc, b.suc) } if (!b.isNeg || b.isZero) true else iter(this, b) } protected def biggerThanInt(b: MyInteger): Boolean = { def iter(a: MyInteger, b: MyInteger): Boolean = a.isZero || b.isZero match { case true => (a isZero) && !(b isZero) case false => iter(a.suc, b.suc) } if (!b.isNeg || b.isZero) false else iter(this, b) } protected def equalsInt(b: MyInteger): Boolean = !(this < b) && !(this > b) def pre: MyInteger = new Pre(this) def suc: MyInteger = nb def neg = { def iter(nb: MyInteger, accu: MyInteger): MyInteger = { if (nb isZero) accu else iter(nb.suc, accu.suc) } iter(this, new Zero) } } class Suc(nb: MyInteger) extends MyInteger { val isZero = false val isNeg = false val isInf = false protected def plusInt(b: MyInteger): MyNumber = { def iter(b: MyInteger, accu: MyNumber): MyNumber = { if (b isNeg) this - (b neg) else if (b isZero) accu else iter(b.pre, accu.suc) } iter(this, b) } protected def minusInt(b: MyInteger): MyNumber = { def iter(b: MyInteger, accu: MyNumber): MyNumber = { if (b isNeg) this + (b neg) else if (b isZero) accu else iter(b.pre, accu.pre) } iter(b, this) } protected def multInt(b: MyInteger): MyNumber = { def iter(a: MyInteger, b: MyInteger, accu: MyNumber): MyNumber = { if (b.isZero) accu else iter(a, b.pre, accu + a) } if (b.isZero) new Zero else { if (this < b) { if (b.isNeg) iter(b.neg.toInteger, this, new Zero).neg else iter(b, this, new Zero) } else { if (b.isNeg) iter(this, b.neg.toInteger, new Zero).neg else iter(this, b, new Zero) } } } protected def divInt(b: MyInteger): MyNumber = { def iter(a: MyNumber, b: MyNumber, count: MyNumber): MyNumber = { if (a.isZero) count else if (a.isNeg) count.pre else iter(a - b, b, count.suc) } if (b.isZero) new PosInf else if(b.isInf) new Zero else if (b.isNeg) iter(this, b.abs, new Zero).neg else iter(this, b, new Zero) } protected def powInt(b: MyInteger): MyNumber = { def iter(a: MyInteger, b: MyInteger, accu: MyNumber): MyNumber = { if (b.isZero) accu else iter(a, b.pre, accu * a) } if (b.isZero) (new Zero).suc else { if (b.isNeg) new Fraction((new Zero).suc, iter(this, b.neg.toInteger, (new Zero).suc).toInteger) else new Fraction(iter(b, this, (new Zero).suc).toInteger) } } protected def powFrac(b: Fraction): MyNumber = (new Zero).pre //TODO protected def lessThanInt(b: MyInteger): Boolean = { def iter(a: MyInteger, b: MyInteger): Boolean = a.isZero || b.isZero match { case true => (a isZero) && !(b isZero) case false => iter(a.pre, b.pre) } if (b.isNeg || b.isZero) false else iter(this, b) } protected def biggerThanInt(b: MyInteger): Boolean = { def iter(a: MyInteger, b: MyInteger): Boolean = a.isZero || b.isZero match { case true => !(a isZero) && (b isZero) case false => iter(a.pre, b.pre) } if (b.isNeg || b.isZero) true else iter(this, b) } protected def equalsInt(b: MyInteger): Boolean = !(this < b) && !(this > b) def pre: MyInteger = nb def suc: MyInteger = new Suc(this) def neg = { def iter(nb: MyInteger, accu: MyInteger): MyInteger = { if (nb isZero) accu else iter(nb.pre, accu.pre) } iter(this, new Zero) } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

FractionクラスはMyIntegerに完全に基づいているため、やや簡単です。

 class Fraction(x: MyInteger, y: MyInteger) extends MyNumber { def this(x: MyInteger) = this(x, (new Zero).suc) val isNatural: Boolean = false val isNeg: Boolean = (x.isNeg && !y.isNeg) || (!x.isNeg && y.isNeg) val isZero: Boolean = x.isZero val isInf: Boolean = x.isInf || y.isInf def +(b: MyNumber): MyNumber = this plus b.toFraction private def plus(b: Fraction): MyNumber = new Fraction((this.num * b.denum + this.denum * b.num).toInteger, (this.denum * b.denum).toInteger) def -(b: MyNumber): MyNumber = this minus b.toFraction private def minus(b: Fraction): MyNumber = new Fraction((this.num * b.denum - this.denum * b.num).toInteger, (this.denum * b.denum).toInteger) def *(b: MyNumber): MyNumber = this mult b.toFraction private def mult(b: Fraction): MyNumber = new Fraction((this.num * b.num).toInteger, (this.denum * b.denum).toInteger) def /(b: MyNumber): MyNumber = this div b.toFraction private def div(b: Fraction): MyNumber = new Fraction((this.num * b.denum).toInteger, (this.denum * b.num).toInteger) def ^(b: MyNumber): MyNumber = if (!b.isNatural) (new Zero).pre else new Fraction((this.num ^ b.toInteger).toInteger, (this.denum ^ b.toInteger).toInteger) def <(b: MyNumber): Boolean = if (this.num.isNeg) { if (b.num.isNeg) this.neg > b.neg else true } else if (this.isZero) { if (b.isZero || b.num.isNeg) false else true } else { if (b.num.isNeg || b.isZero) false else this.num * b.denum < this.denum * b.num } def >(b: MyNumber): Boolean = if(this.num.isNeg){ if(b.num.isNeg) this.neg < b.neg else false }else if(this.isZero){ if(b.isZero || !b.num.isNeg) false else true }else{ if(b.num.isNeg || b.isZero) true else this.num * b.denum > this.denum * b.num } def ==(b: MyNumber): Boolean = if(!b.isNatural)(this.num == b.num) && (this.denum == b.denum) else this == b.toFraction def neg: MyNumber = new Fraction(num.neg.toInteger, denum) def abs: MyNumber = new Fraction(num.abs.toInteger, denum) def pre: MyInteger = sys.error("Predicat of fraction") def suc: MyInteger = sys.error("Successor of fraction") val num = ((if(this.isNeg)x.abs.neg else x.abs) / (x.abs gcd y.abs)).toInteger val denum = (y.abs / (x.abs gcd y.abs)).toInteger def gcd(b: MyNumber): MyNumber = this.denum gcd (new Zero).suc def mod(b: MyInteger): MyNumber = new Zero override def toString(): String = if(num.isZero) 0.toString() else if(this.isInf) "" else if(denum == (new Zero).suc) num.toString() else num + "/" + denum }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

以上です！ 現在、自然数と小数、および一連の単純な操作があります（ネイティブクラスを1回使用するのではなく、ご注意ください）。



同じ原則を使用して、新しく出現した数値のデータ構造を作成できます。

 abstract class MySet { def add(elem: MyNumber): MySet def delete(elem: MyNumber): MySet def union(set: MySet): MySet def intersec(set: MySet): MySet def contains(elem: MyNumber): Boolean def linearSearch(elem: MyNumber): MySet def mergeSort: MySet def merge: MySet def quickSort: MySet def timSort: MySet def binaryTreeSort: MySet def length: MyNumber def get(pos: MyNumber): MyNumber def take(n: MyNumber): MySet def drop(n: MyNumber): MySet def map(p: MyNumber => MyNumber): MySet def filter(p: MyNumber => Boolean): MySet def flat(p: (MyNumber, MyNumber) => MyNumber): MyNumber
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

また、再帰関数を使用して多くのことを実行でき、独自のユニバースを作成することもできます。 「ブラックジャックと売春婦。」 ご清聴ありがとうございました。