2

私は、Coursera での Scala の関数型プログラミングの講義に従っています。ビデオ 5.7 の最後で、Martin Odersky は次の方程式の正しさを帰納法によって証明するよう求めています。

(xs ++ ys) map f = (xs map f) ++ (ys map f)

複数のリストが含まれている場合、帰納法による証明をどのように処理するのですか?

xs が Nil で ys が Nil である基本ケースを確認しました。xs を x::xs に置き換えたときに方程式が成立することを帰納法によって証明しましたが、ys を y::ys に置き換えた方程式もチェックする必要がありますか?

そしてその場合（エクササイズをあまり台無しにすることなく...とにかく採点されません）、どのように処理します(xs ++ (y::ys)) map fか？

これは、私が同様の例で使用したアプローチであり、

(xs ++ ys).reverse = ys.reverse ++ xs.reverse

証明 (基本ケースと簡単な x::xs ケースを省略):

(xs ++ (y::ys)).reverse
= (xs ++ (List(y) ++ ys)).reverse         //y::ys = List(y) ++ ys
= ((xs ++ List(y)) ++ ys).reverse         //concat associativity
= ys.reverse ++ (xs ++ List(y)).reverse   //by induction hypothesis (proven with x::xs)
= ys.reverse ++ List(y).reverse ++ xs.reverse //by induction hypothesis
= ys.reverse ++ (y::Nil).reverse ++ xs.reverse //List(y) = y :: Nil
= ys.reverse ++ Nil.reverse ++ List(y) ++ xs.reverse //reverse definition
= (ys.reverse ++ List(y)) ++ xs.reverse //reverse on Nil (base case)
= (y :: ys).reverse ++ xs.reverse         //reverse definition

これは正しいですか ？

4

2 に答える 2

4

プロパティには複数のリストが含まれますが++、左の引数でのみ再帰します。これは、その左辺の帰納法によって証明できるヒントです。一般に、ある再帰関数に関する命題を証明するとき、最初に試みることは、関数が再帰するのと同じ引数で帰納することです。

例として、これを行います。

クレーム: (xs ++ ys) map f=(xs map f) ++ (ys map f)

証明: の帰納法によるxs.

  • 基本ケース: xs=Nil

    • lhs =(Nil ++ ys) map f=ys map f

      (++の定義による)

    • 相対値 =(Nil map f) ++ (ys map f)=Nil ++ ys map f=ys map f

      (の定義map、次に++の定義による)

    • したがって、lhs = rhs

  • 誘導の場合: xs=z :: zs

    • 仮説:(zs ++ ys) map f=(zs map f) ++ (ys map f)
    • 目標:((z :: zs) ++ ys) map f=((z :: zs) map f) ++ (ys map f)

    • lhs =(z :: (zs ++ ys)) map f=f(z) :: ((zs ++ ys) map f) (1)

      (mapの定義による)

    • 相対値 =((z :: zs) map f) ++ (ys map f)=(f(z) :: (zs map f)) ++ (ys map f)

      (mapの定義による)

    • 次に、rhs = f(z) :: ((zs map f) ++ (ys map f)) (2)

      (++の定義による)

    • 仮説、(1)および(2)から、ゴールが証明されました。

xsしたがって、 、ys、および に関係なく、主張が真であることを証明しましたf。

于 2015-05-24T02:31:29.813 に答える
0

@Philのコメントが言うように、最初はメソッドがリストで何をしているのかをよく理解することであり、より良い方法は++ドキュメントです::

リストプログラムの性質を証明するにはどうすればよいでしょうか? 答えは構造帰納法です！構造帰納法によるリスト プロパティ P(xs) の証明規則:

すべての x,xs に対する P(Nil) (基本ケース) : P(xs) => P(x::xs) (誘導ステップ)

すべての xs に対して : P(xs) (帰結)

誘導段階の P(xs) は誘導仮説と呼ばれる

重要なのは xs だけなので、ys は長さ l の適切なリストを修正することです。

それでは、帰納法と関数の定義を適用しましょう

P(xs): (xs ++ ys) マップ f = (xs マップ f) ++ (ys マップ f)

基本ケースでは、xs を nil に置き換えます

(nil ++ ys) map f [definition of ++ ] 
ys map f  on the other hand 
(xs map f) ++ (ys map p) [apply map over NIL] 
(NIL) ++ (ys map p) [definition pf ++] 
ys map p

誘導ステップ

((x::xs) ++ ys) map f [definition ++]
(x:: (xs ++ ys)) map f [definition map]
f(x) :: ((xs ++ ys) map f) [induction hypothesis]
f(x) :: ((xs map f) ++ (ys map f)) [definition ++]
(f(x) :: (xs map f)) ++ (ys map f) [definition map]
(x::xs) map f ++ ys map f

した

たとえば、scala ワークシートの別のケース

import scala.util.Random

// P : length ( append(as,bs) )) = length ( as ) + length (bs)

def length[T](as: List[T]): Int = as match {
    case Nil => 0
    case _::xs => 1 + length(xs)
}

def append[T](as: List[T], bs: List[T]): List[T] = as match {
  case Nil => bs
  case x :: xs => x :: append(xs, bs)
}

// base case  we substitute Nil for as in P

val a:List[Int] = Nil
val n = 10
val b:List[Int] = Seq.fill(n)(Random.nextInt).toList

length((append(a,b)))

length(a)

length(b)

import scala.util.Random

length: length[T](val as: List[T]) => Int




append: append[T](val as: List[T],val bs: List[T]) => List[T]






a: List[Int] = List()
n: Int = 10
b: List[Int] = List(1168053950, 922397949, -1884264936, 869558369, -165728826, -1052466354, -1696038881, 246666877, 1673332480, -975585734)

res0: Int = 10

res1: Int = 0

res2: Int = 10

ここで他の例を見つけることができます

于 2015-05-23T10:30:33.020 に答える