4

私はいくつかの関数型言語を学ぶことに決めました、そして結局私はlisp-schemeに接続しました。

リストがソートされているかどうかをチェックする関数を作成しようとしています。リストがソートされているかどうかをチェックします。最初に低いものが高くなるか、その逆になります。ソートできる場合はtrueを返し、そうでない場合はfalseを返します。

これは私の最初のコードであり、リストが増加している（または等しい）場合にのみ機能します。

    (define sorted?
     (lambda (lst)
      (cond ((empty? lst) #t)
            (else (and (<= (car lst) (cadr lst))
                  (sorted? (cdr lst)))))))

明確化：（sorted？'（1 2 3 4 5））や（sorted？'（5 4 3 2 1））のようなものはtrueを返す必要があります。そうでない場合は、もちろんfalseを返します。

機能的なスタイルでプログラミングするとき、私はどのように考えるべきですか？構文は単純に見えますが、私はロジックに慣れていません。

4

5 に答える 5

5

特定の実装

ÓscarLópezの答えを参考にして、さらに一歩進んでください。

(define sorted? (lambda (lst)
  (letrec ((sorted-cmp 
            (lambda (lst cmp)
              (cond ((or (empty? lst) (empty? (cdr lst)))
                     #t)
                    (else (and (cmp (car lst) (cadr lst))
                               (sorted-cmp (cdr lst) cmp)))))))
    (or (sorted-cmp lst <=) (sorted-cmp lst >=)))))

このバージョンと彼のバージョンの最大の違いは、sorted?オスカーのバージョンを、を使用する内部ヘルパー関数として定義し、letrec両方の方法で呼び出すことです。

機能的思考

あなたは実際にSchemeが世界をどのように見ているかのいくつかの側面を説明するための良い例を選びました、そしてあなたの実装は非常に良いスタートを切りました。

この問題の解決に関係する重要な機能原理の1つは、配置できるものは何でも(**here** more stuff '(1 2 3 4))、別の関数への引数として渡すことができるということです。つまり、関数は関数型プログラミング言語のファーストクラスです。したがって、比較で使用していたという事実は、それに応じて比較を行う別の関数にパラメーターとして<=渡すことができることを意味します。<=オスカーの答えは、その点をよく表しています。

別の一般的な機能パターンを具体化するこの問題の別の側面は、主に(cond)ブロックで構成される機能です。多くの関数型プログラミング言語（Haskell、ML、OCaml、F＃、Mathematica）では、Schemeのデフォルトで、より強力なパターンマッチング機能を利用できます。したがって(cond)、Schemeでは、探しているパターンをテストする方法を説明する必要がありますが、それは通常、かなり簡単です（たとえば、(or (empty? lst) (empty? (cdr lst)))この実装では）。

この問題でよく具体化されていると私が見ている最後の関数型プログラミングパターンの1つは、多くの関数型プログラミングソリューションが再帰的であるということです。再帰は、私がletrec単純なol'の代わりに使用しなければならなかった理由letです。

cdr最初の要素（またはこの場合は2つの要素）を操作してから、その方法でリストの末尾（）で操作を繰り返すことで実行できるほとんどすべてのこと。命令型forまたはwhileスタイルのループはSchemeでは不可能ではありませんが（Haskellなどの純粋関数型言語ではほとんど不可能ですが）、多くの状況でSchemeでは少しずれています。しかし、開発者がその決定を下せるようにするSchemeの柔軟性により、特定の状況で重要なパフォーマンスまたは保守性の最適化が可能になります。

継続的な調査

ここでの私の答えに対する私の最初の実装は、リストに表示されたものに基づいて、sorted?渡す比較演算子を決定することでした。sorted-cmpリストが2つの等しい数で始まる可能性があることに気付いたとき、私はそれを後退させました'(1 1 2 3 4 5)。しかし、私がそれについてもっと考えると、あなたがまだ方向を決定したかどうかを追跡する方法が確かにあり、したがって、必要な呼び出しは1つだけですsorted-cmp。次にそれを探求することを検討するかもしれません。

于 2012-04-26T19:56:28.420 に答える
5

あなたはほとんどそれを正しく理解しました:

(define sorted?
  (lambda (lst)
    (cond ((or (empty? lst) (empty? (cdr lst)))
           #t)
          (else (and (<= (car lst) (cadr lst))
                     (sorted? (cdr lst)))))))

基本ケースに少し変更を加えれば、準備は完了です。リストに要素が 1 つしか残っていない場合は、停止する必要があります。そうしないと、cadr式でエラーがスローされます。

質問の 2 番目の部分: 別の基準を使用して並べ替えられているかどうかを確認する場合は、次のように比較関数を引数として渡すだけです。

(define sorted?
  (lambda (lst cmp)
    (cond ((or (empty? lst) (empty? (cdr lst)))
           #t)
          (else (and (cmp (car lst) (cadr lst))
                     (sorted? (cdr lst) cmp))))))

(sorted? '(1 2 3 4 5) <=)
> #t
(sorted? '(5 4 3 2 1) >=)
> #t

リストが昇順または降順でソートされているかどうかを知りたい場合は、次のようにします。

(define lst '(1 2 3 4 5))
(or (sorted? lst >=) (sorted? lst <=))
> #t

ご覧のとおり、関数型プログラミングとは、手続きを可能な限り汎用的に定義し、それらを組み合わせて問題を解決することです。関数をパラメーターとして渡すことができるという事実は、汎用関数の実装に大いに役立ちます。

于 2012-04-26T19:05:45.973 に答える
3

より具体的には、「C や Java などの命令型言語で既にプログラミングしている場合、関数型プログラミングの考え方をどのように調整すればよいですか?」という意味であなたの質問を解釈します。あなたの問題を例として、土曜日の朝にこの質問に長い形式で答えるつもりです。関数型プログラマーの進化を 3 つの段階でたどっていきます。それぞれの段階は、禅の段階的に高くなります。1)反復的に考えます。2)再帰的に考える。3)怠惰に考える。

パート I - 反復的に考える

私が C でプログラミングしていて、再帰を使用できない、または使用しないとします。おそらく、コンパイラは末尾再帰を最適化せず、再帰的なソリューションはスタックをオーバーフローさせます。それで、私はどのような状態を維持する必要があるかを考え始めます。入力の上を這う小さな機械を想像してみてください。増加するシーケンスまたは減少するシーケンスを検索しているかどうかを記憶します。まだ決定していない場合は、可能であれば現在の入力に基づいて決定します。間違った方向に向かう入力が見つかった場合、zigzag=true で終了します。入力の最後に到達すると、zigzag=false で終了します。

int
zigzag(int *data, int n)
{
  enum {unknown, increasing, decreasing} direction = unknown;

  int i;
  for (i = 1; i < n; ++i)
    {
      if (data[i] > data[i - 1]) {
    if (direction == decreasing) return 1;
    direction = increasing;
      }
      if (data[i] < data[i - 1]) {
    if (direction == increasing) return 1;
    direction = decreasing;
      }
    }

  /* We've made it through the gauntlet, no zigzagging */
  return 0;
}

このプログラムは典型的な C プログラムです。効率的ですが、正しいことを証明するのは困難です。この単純な例であっても、これが無限ループに陥ったり、ロジックのどこかで間違った方向に進んだりする可能性があるかどうかはすぐにはわかりません。もちろん、より複雑なプログラムではさらに悪化します。

パート II - 再帰的に考える

関数型言語の精神で読みやすいプログラムを作成するための鍵は (単に命令型ソリューションをその言語に変形させようとするのではなく) 、プログラムがどのように計算するかではなく、何を計算するかに焦点を当てることであることがわかりました。十分な精度でそれを行うことができれば (問題を明確に書き出すことができれば)、ほとんどの場合、関数型プログラミングでは、ほぼ解決に近づいています!

それでは、計算することをより詳細に書き出すことから始めましょう。リストがジグザグ (つまり、ある時点で減少し、別の時点で増加する) かどうかを知りたいのです。この基準を満たすリストはどれですか? さて、次の場合、リストはジグザグになります。

  • 2 要素以上の長さであり、かつ
  • 最初は増加しますが、ある時点で減少します OR
  • 最初は減少するが、ある時点で増加する OR
  • その尾はジグザグです。

上記のステートメントを多かれ少なかれ直接的にScheme関数に変換することが可能です:

(define (zigzag xs)
  (and (> (length xs) 2)
       (or (and (initially-increasing xs) (decreases xs))
           (and (initially-decreasing xs) (increases xs))
           (zigzag (cdr xs)))))

ここで、 、 、 、および の定義initially-increasingがinitially-decreasing必要decreasesですincreases。initially-関数は十分に単純です。

(define (initially-increasing xs)
  (> (cadr xs) (car xs)))

(define (initially-decreasing xs)
  (< (cadr xs) (car xs)))

decreasesとはどうincreasesですか？シーケンスの長さが 1 より大きく、最初の要素が 2 番目の要素より大きい場合、または末尾が減少する場合、シーケンスは減少します。

(define (decreases xs)
  (letrec ((passes
        (lambda (prev rest)
          (cond ((null? rest) #f)
            ((< (car rest) prev)
             #t)
            (else (passes (car rest) (cdr rest)))))))
    (passes (car xs) (cdr xs))))

同様の関数を書くこともできますが、必要increasesな変更は 1 つだけであることは明らかです。非常に多くのコードを複製すると、不安になるはずです。言語に のような関数を作成するように依頼できませんでしたが、代わりにその場所で使用していますか? 関数型言語では、関数は他の関数を返すことができるため、まさにそれを行うことができます! したがって、実装する関数を書くことができます。<>decreases>

(define (ever op)
 (lambda (xs)
   (letrec ((passes
         (lambda (prev rest)
           (cond ((null? rest) #f)
             ((op (car rest) prev)
              #t)
             (else (passes (car rest) (cdr rest)))))))
     (passes (car xs) (cdr xs)))))

increases両方ともdecreases非常に簡単に定義できるようになりました。

(define decreases (ever <))
(define increases (ever >))

実装する関数はもうありません - 完了です。このバージョンが C バージョンよりも優れていることは明らかです。このプログラムが正しいことを行うと判断するのははるかに簡単です。このプログラムのほとんどは非常に簡単で、すべての複雑さが関数に押し込まれていeverます。これは、他の多くのコンテキストで役立つ非常に一般的な操作です。検索することで、このカスタム実装ではなく、標準の (したがってより信頼できる) 実装を見つけることができると確信しています。

改善はされていますが、このプログラムはまだ完全ではありません。多くのカスタム再帰があり、最初はそのすべてが末尾再帰であることは明らかではありません(実際にはそうですが)。また、プログラムは複数の条件付き分岐と出口点の形で C のかすかなエコーを保持します。遅延評価の助けを借りて、さらに明確な実装を得ることができます。そのために、言語を切り替えます。

パート III - 怠惰に考える

問題の定義に戻りましょう。実際には、パートIIよりもはるかに簡単に述べることができます-「両方向に進む隣接する要素間の比較が含まれている場合、シーケンスはジグザグになります（つまり、ソートされません）」。この文を多かれ少なかれ直接的に Haskell の行に翻訳できます。

zigzag xs = LT `elem` comparisons && GT `elem` comparisons

ここで、 のすべてのメンバーとその後継comparisonsメンバーとの比較のリストであるを導出する方法が必要です。xsこれは難しいことではなく、例によって説明するのがおそらく最も適切です。

> xs
[1,1,1,2,3,4,5,3,9,9]

> zip xs (tail xs)
[(1,1),(1,1),(1,2),(2,3),(3,4),(4,5),(5,3),(3,9),(9,9)]

> map (\(x,y) -> compare x y) $ zip xs (tail xs)
[EQ,EQ,LT,LT,LT,LT,GT,LT,EQ]

必要なのはそれだけです。これらの 2 行は完全な実装です -

zigzag xs = LT `elem` comparisons && GT `elem` comparisons
  where comparisons = map (\(x,y) -> compare x y) $ zip xs (tail xs)

このプログラムは、リストを 1 回だけ通過させて、増加するケースと減少するケースの両方をテストすることに注意してください。

ここまでで、おそらく反論を考えたことがあるでしょう。このアプローチは無駄ではありませんか? 最初の方向転換まで行けばよいのに、これは入力リスト全体を検索するのではないでしょうか? 実際には、遅延評価のため、そうではありません。上記の例では、印刷するために比較リスト全体を計算する必要があったためです。しかし、結果を に渡す場合は、 の 1 つのインスタンスとの 1zigzagつを見つけるのに十分なだけ比較リストを評価し、それ以上は評価しません。これを確信するには、次のケースを検討してください。GTLT

> zigzag $ 2:[1..]
True
> zigzag 1:[9,8..]
True

どちらの場合も、入力は無限リスト ([2,1,2,3,4,5..] および [1,9,8,7,6,5...]) です。それらを印刷しようとすると、画面いっぱいになります。しかし、それらを に渡すzigzagと、方向の最初の変更を見つけるとすぐに、非常に迅速に戻ります。

コードを読むのが難しいのは、多くの場合、制御フローの複数の分岐をたどるからです。そして、これらのブランチの多くは、必要以上の計算を避けるための努力です。しかし、同じことの多くは遅延評価でも達成でき、プログラムをより短くし、元の質問により忠実にすることができます。

于 2012-04-28T19:10:01.437 に答える
0

これを試して

(define sorted?
  (lambda (l)
     (cond ((null? l) #t)
           (else (check-asc? (car l) (sorted? (cdr l))
                 (check-desc? (car l) (sorted? (cdr l))))))


(define check-asc?
  (lambda (elt lst)
     (cond ((null? lst) #t)
           (else (or (< elt (car lst)) (= elt (car lst))) (check-asc? (car lst) (cdr lst))))))

(define check-desc?
  (lambda (elt lst)
     (cond ((null? lst) #t)
           (else (or (< elt (car lst)) (= elt (car lst))) (check-desc? (car lst) (cdr lst))))))

私自身初心者です。このコードはテストしていません。まだ再帰に苦労しています。それが機能したかどうか、またはどのようなエラーが発生したかを教えてください。

于 2012-05-02T06:27:52.153 に答える
0

私が与えた前の答えは本当に悪かった。

DrScheme でコードを実行したところ、エラーが発生しました。

しかし、私はそれを変更しました。動作するコードは次のとおりです。

(define sorted?
 (lambda (l)
   (cond ((null? l) #t)
       (else (if (check-asc? (car l) (cdr l)) #t
             (check-desc? (car l) (cdr l)))))))


(define check-asc?
(lambda (elt lst)
  (cond ((null? lst) #t)
       (else (if (or (< elt (car lst)) (= elt (car lst))) (check-asc? (car lst) (cdr lst))
                 #f)))))

(define check-desc?
 (lambda (elt lst)
  (cond ((null? lst) #t)
       (else (if (or (> elt (car lst)) (= elt (car lst))) (check-desc? (car lst) (cdr lst))
                 #f)))))

チェックされたケース:

(ソート済み? '(5 4 3 2 1)) #t を返す

(ソート済み? '(1 2 3 4 5)) #t を返す

(sorted? '(1 2 3 5 4)) は #f を返します

(ソート済み? '()) #t を返す

(ソート済み? '(1)) #t を返す

于 2012-05-02T13:46:29.510 に答える