ラムダ関数のリスト

翻訳者注：オリジナルはこちら 。 オリジナルの例はすべてJavaScriptで記述されていますが、Schemeに翻訳することにしました。 それほど明確にならなかったと思いますが、この言語の美しさはすべて見えています。

UPD：右側のすべての例にJavaScriptの元の例を追加しました。





コンピューターの実用的な側面（サイズ、重量、価格、熱など）に目を向けると、プログラミング言語は実際に何ができるはずですか？ この質問を調べてみましょう。



この記事の例を理解するには、LISP（Scheme）の関数に関する基本的な概念が必要です。 このコードが何を印刷するかを理解している場合、さらに読むことができます：

(define x 10) (define (fy) (display x) (newline) (display y) (newline) ) (define gf) (f 1) (g 2)

var x = 10; var f = function(y) { console.log(x); console.log(y); } var g = f; f(1); g(2);

この記事は脳のための単なるトレーニングであり、実際のコードで使用できるものではありません。 しかし、ギタリストが実際の歌で決して使用しないスケールを演奏するのと同じように、プログラマーは時々脳を伸ばす必要があります。



デモにはSchemeを使用しますが、機能を一流の関数および字句スコープ（主にクロージャー）としてサポートする他の言語はすべて行います。



すでにそのようなものを見たことがあれば（おそらくSICPやThe Little Schemerで ）、あなた自身のために何か新しいものを探してコードを調べてみるべきです。



このようなものを見たことがなければ、おいしいものがあります。 初めて、すべてが非常に奇妙に見えます。 ゆっくり動かしてください。 前のパートを理解してから次のパートに進んでください。 ここで説明する概念は直感的ではないかもしれませんが、非常に単純な部分から構築されています。



そして最後に：もしあなたがどこかで立ち往生しているなら、絶望しないでください。 関数のパフォーマンスを紙の上で追跡することは、それがどのように機能するかを理解するための非常に良い方法です（快適な書き込みのために良いポータブルデスクを購入することをお勧めします）。 これで解決しない場合は、記事を閉じて明日読むだけに戻ります。 時々、新しい概念が彼らの場所を見つける前にあなたの頭の中で少しさまよう必要があります。

• リスト
  
  
  • if
    
    
    
    からのリスト
  • しかし、データはどこに行きましたか？
  • これらの基盤の上に構築
    
    
    • 地図
    • フィルター
    • および、または、ではありません
    
    
    
  • ラムダ関数のリスト
  
  
  
• 数字
  
  
  • 数字とは？
  • inc、dec
  • is_zero
  • 加える
  • サブ
  • サブパウ
  • is_equal
  • less_than、greater_than
  
  
  
• 円を閉じる
  
  
  • n番目
  • ドロップ、テイク
  • 長さ
  
  
  
• おわりに

1リスト

さあ、始めましょう！ プログラマーが最もよく実行するプロセスの1つは、データのグループ化です。 Schemeにはこのための組み込みリストがあります（それ以外の場合は、LISPではありません）。

(define names (list "Alice" "Bob" "Candice"))

var names = ["Alice", "Bob", "Candice"];

しかし、Schemeにリストがない場合はどうでしょうか？ 私たちはそれら、またはそれらに類似したものを自分で作ることができますか？



この質問に答えるために、リストのようなものを作成するために必要な最小限のことを考えてみましょう。 これを行うには多くの方法がありますが、そのうちの1つだけを検討します。



リストを操作するには、4つのものが必要です。

• 「空のリスト」の概念
  
  
• リストの一番上にアイテムを追加する方法
  
  
• リストの最初のアイテムを取得する方法
  
  
• リストの最初の要素を除くすべてを取得する方法
  
  

これら4つのものがある場合、それらに基づいて、私たちが望むすべてを構築できます。 たとえば、単一のアイテムからリストを作成するには、空のリストの一番上にこのアイテムを追加できます。



これらの4つの部分を実装するには多くの方法があります-関数を使用します。 彼らのスケッチは次のとおりです。

(define empty_list '()) (define (prepend el lst) ...) (define (head lst) ...) (define (tail lst) ...) (define (is_empty lst) ...)

var empty_list = null; var prepend = function(el, list) { // ... }; var head = function(list) { // ... }; var tail = function(list) { // ... }; var is_empty = function(list) { // ... };

これらの各定義の説明は次のとおりです。



empty_list



は、ゼロ要素のリストを表す特別な値です。 何でも構いませんので、Schemeの標準の'()



を使用します。 これについては後で説明します。



(prepend 1 some_list)



は、先頭に1



挿入された古いリストのように見える新しいリストを返します。 したがって、番号1



と2



リストを作成する場合、 (prepend 1 (prepend 2 empty_list))



追加(prepend 1 (prepend 2 empty_list))



追加(prepend 1 (prepend 2 empty_list))



または「空のリストに1



を追加した結果に2



を追加」と書くことができます



(head some_list)



は、リストの最初のアイテムを返します。 空のリストからの結果は定義されていないため、注意してください。



(tail some_list)



は、最初の要素がない古いリストのように見える新しいリストを返します。 繰り返しtail



が、空のリストからtail



を呼び出すと、すべてが台無しになります。



(is_empty some_list)



は、このリストが空の場合は#t



を返し、そうでない場合は#f



を返します。



これらの4つの関数（および空のリストに対する特別な意味）ができたら、それらに基づいて物事の構築を開始できるので、それらを実装する方法を見つけましょう！

1.1 If



リスト

cons



、 cdr



、 cdr



使用できると思うかもしれませんが、この記事は本当に必要なものを見つけるための実験であり、これが回避できる場合は言語の組み込み機能を使用しないでください。



したがって、言語の機能を使用したくない場合、何が残りますか？ さて、今のところ、関数（と'()



）しかありませんので、試してみましょう！



リストの実装の最初の作業バージョンは次のとおりです。

(define empty_list '()) (define (prepend el lst) (lambda (command) (if (equal? command "head") el (if (equal? command "tail") lst ) ) ) ) (define (head lst) (lst "head") ) (define (tail lst) (lst "tail") ) (define (is_empty lst) (equal? lst empty_list) )

var empty_list = null; var prepend = function(el, list) { return function(command) { if (command === "head") { return el; } else if (command === "tail") { return list; } } }; var head = function(list) { return list("head"); }; var tail = function(list) { return list("tail"); }; var is_empty = function(list) { return list === null; };

これをお気に入りのSchemeインタープリターに貼り付けて遊んでください：

(define e empty_list) (display (is_empty e)) ; #t (define names (prepend "Alice" (prepend "Bob" (prepend "Candice" empty_list ) ) ) ) (display (is_empty names)) ; #f (display (head names)) ; Alice (display (tail names)) ; Some function representing the list of ("Bob", "Candice") (display (head (tail names))) ; Bob

var e = empty_list; console.log(is_empty(e)); // true var names = prepend("Alice", prepend("Bob", prepend("Candice", empty_list))); console.log(is_empty(names)); // False console.log(head(names)); // Alice console.log(tail(names)); // Some function representing the list of ("Bob", "Candice") console.log(head(tail(names))); // Bob

1.2しかし、データはどこに行きましたか？

これらの機能の定義に驚きましたか？ リストはそのような重要なオブジェクト指向の概念のように見えますが、機能はあります！



実際にどのように機能するかを見てみましょう。 まず、「空のリスト」の概念は非常に簡単です。

(define empty_list '()) (define (is_empty lst) (equal? lst empty_list) )

var empty_list = null; var is_empty = function(list) { return list === null; };

任意の値を選択できます。 '()



が適切なので、私はそれを使用しました。



さて、最も重要なprepend



： prepend



。

(define (prepend el lst) (lambda (command) (if (equal? command "head") el (if (equal? command "tail") lst ) ) ) )

var prepend = function(el, list) { return function(command) { if (command === "head") { return el; } else if (command === "tail") { return list; } } };

ここですべての魔法が発生します。 考え直してみましょう。



まず、リストの先頭に何かを追加すると、（新しい）リストが返されることを知っています。 したがって、 prepend



の戻り値はリストである必要があります。



コードを一目見れば、 prepend



が関数を返すことを理解できます。 したがって、私たちのちょっとした実験では、リストは単なる（ラムダ）Scheme関数です！



それで、リストで何をする必要がありますか（すでにカバーしているボイドをチェックする以外）？ さて、頭と尻尾を取得する必要があります。 (prepend ht)



を呼び出すとき、引数としてheadとtailを渡すだけです！ そのため、 prepend



は、リクエストに応じて先頭または末尾を返す方法を知っている関数を返します。



したがって、「リスト」とは、「要求に応じて頭または尾を戻す方法を知っている」関数です。 head



とtail



機能はよく尋ねられるだけであることがわかります！

(define (head lst) (lst "head") ) (define (tail lst) (lst "tail") )

var head = function(list) { return list("head"); }; var tail = function(list) { return list("tail"); };

以上です！ 関数のみを使用して、24行のコードでリストを作成しました。 さらに先に進む前に、これがなぜ機能するのかを理解してください。 一枚の紙で練習できます。

1.3この基盤の上に構築

リストができたので、それらに基づいていくつかの一般的なことを練習して実装しましょう。

地図

リストの一般的なタスクの1つは、古いものをループして各要素に何らかの機能を適用することにより、新しいものを作成することです。 これはmap



と呼ばれmap



。

(define (map fn l) (if (is_empty l) empty_list (prepend (fn (head l)) (map fn (tail l))) ) )

var map = function(fn, l) { if (is_empty(l)) { return empty_list; } else { return prepend(fn(head(l)), map(fn, tail(l))); } };

このような再帰的な定義に慣れていない場合は、数分を費やしてその動作をペイントすることをお勧めします。 たとえば、次のように：

(define (square x) (* xx)) (define numbers (prepend 1 (prepend 2 (prepend 3 empty_list)))) (define squared_numbers (map square numbers)) ; (map square (1 2 3)) ; (prepend (square 1) (map square (2 3)) ; (prepend (square 1) (prepend (square 2) (map square (3)))) ; (prepend (square 1) (prepend (square 2) (prepend (square 3) (map square '())))) ; (prepend (square 1) (prepend (square 2) (prepend (square 3) '()))) ; (prepend (square 1) (prepend (square 2) (prepend 9 '()))) ; (prepend (square 1) (prepend (square 2) (9))) ; (prepend (square 1) (prepend 4 (9))) ; (prepend (square 1) (4 9)) ; (prepend 1 (4 9)) ; (1 4 9)

var square = function(x) { return x * x; } var numbers = prepend(1, prepend(2, prepend(3, empty_list))); var squared_numbers = map(square, numbers); // map(square, [1, 2, 3]) // prepend(square(1), map(square, [1, 2, 3])) // prepend(square(1), prepend(square(2), map(square, [3]))) // prepend(square(1), prepend(square(2), prepend(square(3), map(square, [])))) // prepend(square(1), prepend(square(2), prepend(square(3), []))) // prepend(square(1), prepend(square(2), prepend(9, []))) // prepend(square(1), prepend(square(2), [9])) // prepend(square(1), prepend(4, [9])) // prepend(square(1), [4, 9]) // prepend(1, [4, 9]) // [1, 4, 9]

Schemeスタイルのリスト（ (1 2 3)



）を書いていますが、実際にはprepend



から返される関数があります。



それでもまだ理解していない場合は、実行(map square empty_list)



を追跡してから、実行(map square (prepend 10 empty_list))



ます。



このスタイルの再帰的思考には、ある程度の練習が必要です。 これで落書きしたノートがたくさんあります。 経験豊富なギタリストは、新しい素材をゆっくりと系統的に学びます。プログラマーが同じことをしない理由はありません。 関数呼び出しの成長と破壊を見ると、これらの機能が実際にどのように機能するかを理解するのに役立ちますが、コードを長時間見ても何も起こりません。

フィルター

これから少し速く動き始めますが、先に進む前にすべてを完全に理解していることを確認する必要があります。 好きなだけ時間をかけて、紙に書いて、コードを実行して、感じてください。



リストに基づいて構築する次の関数はfilter



です。 関数とリストを取り、指定された関数が#t



返す元の要素を含む新しいリストを返します。 以下に例を示します。

(define numbers (prepend 1 (prepend 2 (prepend 3 empty_list)))) (define (is_odd x) (equal? (modulo x 2) 1)) (filter is_odd numbers) ; (1 3)

var numbers = prepend(1, prepend(2, prepend(3, empty_list))); var is_odd = function(x) { return x % 2 === 1; } filter(is_odd, numbers); // [1, 3]

ここでfilter



を実装しfilter



：

(define (filter fn l) (if (is_empty l) empty_list (if (fn (head l)) (prepend (head l) (filter fn (tail l))) (filter fn (tail l)) ) ) )

var filter = function(fn, l) { if (is_empty(l)) { return empty_list; } else if (fn(head(l))) { return prepend(head(l), filter(fn, tail(l))); } else { return filter(fn, tail(l)); } };

休憩して、例を確認してください。 これを完全に理解することによってのみ先に進みます。

および、または、ではありません

コースから逸脱し、「補助」機能を実装します。 それらはリストに関連していませんが、まだ必要です。

(define (not x) (if x #f #t ) ) (define (and ab) (if a (if b #t #f ) #f ) ) (define (or ab) (if a #t (if b #t #f ) ) )

var not = function(x) { if (x) { return false; } else { return true; } }; var and = function(a, b) { if (a) { if (b) { return true; } else { return false; } } else { return false; } }; var or = function(a, b) { if (a) { return true; } else { if (b) { return true; } else { return false; } } };

当然、Schemeにはすでにこれらすべてがありますが、それらを使用せずにできる限り、あらゆる種類の言語機能を使用しないようにしています。 関数とif



をどこまで使用できますか？



ちょっとした注意：これらはただのScheme関数なので、 (and ab)



は組み込みマクロのような速記計算を使用しません。 目標を損なうことはありませんが、忘れないでください。

1.4ラムダ関数のリスト

さて、少し練習して、関数の定義に戻ります。

(define empty_list '()) (define (prepend el lst) (lambda (command) (if (equal? command "head") el (if (equal? command "tail") lst ) ) ) ) (define (head lst) (lst "head") ) (define (tail lst) (lst "tail") ) (define (is_empty lst) (equal? lst empty_list) )

var empty_list = null; var prepend = function(el, list) { return function(command) { if (command === "head") { return el; } else if (command === "tail") { return list; } } }; var head = function(list) { return list("head"); }; var tail = function(list) { return list("tail"); }; var is_empty = function(list) { return list === null; };

この実装では、いくつかのことが重要です。 私たちの目標は、できるだけ少ない言語機能を使用することですが、すでに十分に使用しています！ 少なくとも5つカウントできます。

• 機能
  
  
• if
  
  
  
  条件
  
  
• 行
  
  
• ブール値（ #f
  
  
  
  および#t
  
  
  
  、結果is_empty
  
  
  
  ）
  
  
• 等価テスト（ equal?
  
  
  
  ）
  
  

このほとんどすべてを取り除くことができますが、読みやすさ（および精神的負担）を犠牲にするだけです。



文字列、等価性チェック、そして最初に構築物があったとしても削除しましょう：

(define (prepend el lst) (lambda (selector) (selector el lst) ) ) (define (head lst) (lst (lambda (ht) h)) ) (define (tail lst) (lst (lambda (ht) t)) )

var prepend = function(el, list) { return function(selector) { return selector(el, list); }; }; var head = function(list) { return list(function(h, t) { return h; }); }; var tail = function(list) { return list(function(h, t) { return t; }); };

あなたはそれを理解しようとする前に噛む必要があります！ 行も、平等性のチェックif



、 if



もありませんが、まだリストがあります！



prepend



関数は関数を返します。以前のバージョンと同じように、「リスト」は実際には要求に応じて先頭と末尾を返す方法を知っていた関数でした。



今回は、「リクエスト」を裏返しました。 このバージョンでは、「リスト」は「リクエストに応じて別の関数に先頭と末尾の両方を与える関数」です。 これで、呼び出し関数は両方の部分を受け取り、どちらを使用するかを決定します。



head



関数を見てみましょう：

• head
  
  
  
  はリストを受け入れて(list ...)
  
  
  
  を呼び出し(list ...)
  
  
  
  これは、「ちょっと、リスト、すべてのデータをこの小さな関数に渡してください」という意味です。
  
  
• リストは(... el lst)
  
  
  
  呼び出し(... el lst)
  
  
  
  これは、「さて、機能はほとんどありません。ここに私の頭と尻尾があります」という意味です。
  
  
• 補助関数は実際には(lambda (ht) h)
  
  
  
  です。これは、引数としてheadとtailを指定して呼び出されたときに、headを返すことを意味します。
  
  
• head
  
  
  
  は結果を取得し、呼び出し元の関数に直接渡します。
  
  

tail



はまったく同じように機能し、ヘルパー関数のみが2番目の引数（tail）を返し、最初の引数は返しません。



以上です！ 等しいif



、および消失したif



確認します。 どこに行ったのかわかりますか？ それらの代わりに今何ですか？



先に進む前に、空のリストの実装をクリーンアップしましょう。 彼女はまだ'()



と等価チェックを使用しています。 それらを削除し、すべてを多かれ少なかれ似たものにします。



これを行うには、他の機能をわずかに変更する必要がありますが、ここまでをすべて理解していれば、この変更は難しくありません。

(define (empty_list selector) (selector '() '() #t) ) (define (prepend el lst) (lambda (selector) (selector el lst #f) ) ) (define (head lst) (lst (lambda (hte) h)) ) (define (tail lst) (lst (lambda (hte) t)) ) (define (is_empty lst) (lst (lambda (hte) e)) )

var empty_list = function(selector) { return selector(undefined, undefined, true); }; var prepend = function(el, list) { return function(selector) { return selector(el, list, false); }; }; var head = function(list) { return list(function(h, t, e) { return h; }); }; var tail = function(list) { return list(function(h, t, e) { return t; }); }; var is_empty = function(list) { return list(function(h, t, e) { return e; }); };

リストを少し賢くしました。 頭と尻尾に補助機能を伝えることができることに加えて、彼らは今、彼らが空であるかどうかを知ることができます。 head



およびtail



関数に3番目の引数を考慮（および無視）させ、 is_empty



関数も残りと同じにしました。



最後に、特別な魔法の意味ではなく、 empty_list



を他の全員と同じ精神で再定義しempty_list



た。 空のリストは通常​​のリストと同じになりました。別のリストを取得して「頭と尻尾は'()



で空のリストです」と言う関数です。



Schemeではこれ以上良いものが見つからなかったため、 '()



を使用しましたが、他の値を自由に使用できます。 空のリストからhead



またはtail



を呼び出さないように注意するため、これらの値は表示されません。



最後に、リストの基本的な要素を実装しましたが、次の2つだけです。

• 機能
  
  
• 空のリストの場合は#t
  
  
  
  および#f
  
  
  
  。
  
  

必要に応じて、2番目を削除する方法を考えてください（この場合、 実際に削除するのですか 、それともSchemeの機能を暗黙的に使用しているだけですか？）。

2つの数字

prepend



、 head



tail



の定義は非常に頭が痛いようです。 ただし、 map



とfilter



定義filter



すでに簡単です。



これは、最初の4つの関数のリストの実装の詳細を隠したためです。 ほとんど何もないリストを作成するという面倒な作業をすべて行い、単純なprepend



、 head



およびtail



インターフェースの後ろに隠しました。



単純なコンポーネントからいくつかのものを作成し、それらを「ブラックボックス」に抽象化するというアイデアは、コンピューターサイエンスとプログラミングの最も重要なアイデアの1つです。

2.1数字とは何ですか？

この記事では、非負数のみを検討します。 負の数のサポートを自分で追加してみることができます。



どのように数字を表現できますか？ もちろん、Scheme番号を使用できますが、使用する言語機能の数を最小限にしようとしているため、それほどクールではありません。



数を表す1つの方法は、長さがその数に等しいリストを使用することです。 (1 1 1)



は「3」を意味し、 ("cats" #f)



は「2」を意味し、 '()



は「ゼロ」を意味します。



このリストの要素自体には意味がないため、すでに存在するもの、つまり空のリストを取り上げましょう。 感じて：

(define zero empty_list) ; '() (define one (prepend empty_list empty_list)) ; ( '() ) (define two (prepend empty_list (prepend empty_list empty_list))) ; ( '() '() )

var zero = empty_list; // [] var one = prepend(empty_list, empty_list); // [ [] ] var two = prepend(empty_list, prepend(empty_list, empty_list)); // [ [], [] ]

2.2 inc、dec

数字で何かをしたいので、数字のリスト表現で機能する関数を書きましょう。



主な建築材料は、 inc



とdec



（増分と減分）です。

(define (inc n) (prepend empty_list n) ) (define (dec n) (tail n) )

var inc = function(n) { return prepend(empty_list, n); }; var dec = function(n) { return tail(n); };

番号に1を追加するには、リストに別の要素を挿入するだけです。 したがって、 (inc (inc zero))



は2を意味します。



1を減算するには、要素の1つを単に削除します。 (dec two)



は「1」を意味します（負の数を無視することを忘れないでください）。

2.3 is_zero

リストの操作の最初に、 is_empty



をよく使用していis_empty



。そのため、 is_zero



関数is_zero



価値がis_zero



ます。

(define (is_zero n) (is_empty n) )

var is_zero = function(n) { return is_empty(n); };

ゼロは空のリストです！

2.4追加

ユニットの追加は簡単ですが、ほとんどの場合、任意の番号を追加できるようになります。 今、 inc



とdec



を持っているので、これを行うのはとても簡単です：

(define (add ab) (if (is_zero b) a (add (inc a) (dec b)) ) )

var add = function(a, b) { if (is_zero(b)) { return a; } else { return add(inc(a), dec(b)); } };

これは別の再帰的な定義です。 数字を追加すると、次の2つの可能性が生じます。

• b
  
  
  
  がゼロの場合、結果はただa
  
  
  
  
  
  
• それ以外の場合、加算a
  
  
  
  もb
  
  
  
  加算a+1
  
  
  
  と同じです。b-1
  
  
  
  
  
  

最終的に、それb



は終了し、答えはa



（減少するにつれて増加しますb



）になります。



リストについての言葉はないことに注意してください！「数字はリストである」という情報は背後is_zero



に隠れていることが判明したためinc



、dec



それを無視して「数字」の抽象化レベルで作業することができます。

2.5サブ

減算は加算に似ていますが、減少するにつれて増加する 代わりに、両方を一緒に削減します。a



b

(define (sub ab) (if (is_zero b) a (sub (dec a) (dec b)) ) )

var sub = function(a, b) { if (is_zero(b)) { return a; } else { return sub(dec(a), dec(b)); } };

これで、タイプの何かを書くことができ(add two (sub three two))



、結果はシステム内の数値「3」の表現になります（もちろん、これは3つの要素のリストです）。



しばらく立ち止まって、数字の中には実際にリストがあり、リストの中には関数以外は何もないことを思い出してください。数値を加算および減算することができ、このすべての中で、関数が前後に移動し、他の関数に拡張し、呼び出すと縮小します1+1=2



。かっこいい！

2.6 mul、パウ

トレーニングのために、数値の乗算を実装します。

(define (mul ab) (if (is_zero b) zero (add a (mul a (dec b))) ) )

var mul = function(a, b) { if (is_zero(b)) { return zero; } else { return add(a, mul(a, dec(b))); } };

可用性add



により、タスクは非常に単純になります。3 * 4は3 + 3 + 3 + 3 + 0と同じです。起こっていることの意味があなたから外れ始めたら、紙の上で機能のパフォーマンスを追跡し、準備ができたと感じたときに戻ってきます。



pow



（べき乗）は似てmul



いますが、数値のコピーを加算する代わりに、それらを乗算し、再帰の「ベース」はゼロではなく1になります。

(define (pow ab) (if (is_zero b) one (mul a (pow a (dec b))) ) )

var pow = function(a, b) { if (is_zero(b)) { return one; } else { return mul(a, pow(a, dec(b))); } };

2.7 is_equal

数値に関する別の問題は、等価性テストです。それで、それを書きましょう。

(define (is_equal nm) (if (and (is_zero n) (is_zero m)) #t (if (or (is_zero n) (is zero m)) #f (is_equal (dec n) (dec m)) ) ) )

var is_equal = function(n, m) { if (and(is_zero(n), is_zero(m))) { return true; } else if (or(is_zero(n), is_zero(m))) { return false; } else { return is_equal(dec(n), dec(m)); } };

3つのケースがあります。

• 両方の数値がゼロの場合、それらは等しい
  
  
  
  
• 数字の1つだけがゼロの場合、それらは等しくありません
  
  
  
  
• それ以外の場合は、それぞれから1を差し引いてもう一度やり直してください
  
  
  
  

この関数が2つの非ゼロ引数で呼び出されると、どちらも最初に「終了」するか、同時に「終了」するまで、両方とも減少します。

2.8 less_than、greater_than

同様に、以下を実装できますless_than



。

(define (less_than ab) (if (and (is_zero a) (is_zero b)) #f (if (is_zero a) #t (if (is_zero b) #f (less_than (dec a) (dec b)) ) ) ) )

var less_than = function(a, b) { if (and(is_zero(a), is_zero(b))) { return false; } else if (is_zero(a)) { return true; } else if (is_zero(b)) { return false; } else { return less_than(dec(a), dec(b)); } };

対照的にis_equal



、4つのケースがあります。

• 両方の数字がゼロで、その後、されていない場合はa
  
  
  
  何も未満b
  
  
  
  
  
  
• それ以外の場合、a
  
  
  
  （およびのみa
  
  
  
  ）がゼロに等しい場合、それはb
  
  
  
  
  
  
• それ以外の場合、b
  
  
  
  （およびのみb
  
  
  
  ）がゼロに等しい場合、それa
  
  
  
  より小さくすることはできませんb
  
  
  
  （負の数は考慮されません）
  
  
• それ以外の場合は、両方を減らして再試行してください。
  
  

繰り返しますが、両方の数値は少なくとも1つが「終了」するまで減少し、比較の結果はどちらが最初に「終了」したかによって決まります。



についても同じことができますgreater_than



が、もっと簡単な方法があります。

(define (greater_than ab) (less_than ba) )

var greater_than = function(a, b) { return less_than(b, a); };

2.9 div、mod

これでless_than



、除算と剰余を実装できます。

(define (div ab) (if (less_than ab) zero (inc (div (sub ab) b)) ) ) (define (rem ab) (if (less_than ab) a (rem (sub ab) b) ) )

var div = function(a, b) { if (less_than(a, b)) { return zero; } else { return inc(div(sub(a, b), b)); } }; var rem = function(a, b) { if (less_than(a, b)) { return a; } else { return rem(sub(a, b), b); } };

これら2つは、負の数を使用できないため、最初の3つの基本操作よりも少し複雑です。これがどのように機能するかを必ず理解してください。

3円を閉じる

現在までに、リスト上に構築された（非常に基本的な）ワーキングナンバーシステムが既にあります。最初に戻って、数字を使用する別のリスト関数を実装しましょう。

3.1番目

n



リストのi番目の要素を取得するには、単純にリストから要素を削除し、n



ゼロに達するまで数を減らします。

(define (nth ln) (if (is_zero n) (head l) (nth (tail l) (dec n)) ) )

var nth = function(l, n) { if (is_zero(n)) { return head(l); } else { return nth(tail(l), dec(n)); } };

, , n



, , dec



. , , ?

3.2 drop, take

— drop



take



.



(drop l three)



.



(take l three)



.

(define (drop ln) (if (is_zero n) l (drop (tail l) (dec n)) ) ) (define (take ln) (if (is_zero n) empty_list (prepend (head l) (take (tail l) (dec n))) ) )

var drop = function(l, n) { if (is_zero(n)) { return l; } else { return drop(tail(l), dec(n)); } }; var take = function(l, n) { if (is_zero(n)) { return empty_list; } else { return prepend(head(l), take(tail(l), dec(n))); } };

3.3 slice

«» , drop



, take



:

(define (slice l start end) (take (drop l start) (sub end start)) )

var slice = function(l, start, end) { return take(drop(l, start), sub(end, start)); };

start



, .

3.4 length

length



— — , :

(define (length l) (if (is_empty l) zero (inc (length (tail l))) ) )

var length = function(l) { if (is_empty(l)) { return zero; } else { return inc(length(tail(l))); } };

空のリストの長さは0で、空でないリストの長さは1にその末尾の長さを加えたものです。



あなたの考えがまだ強力な結び目に絡まっていない場合、これについて考えてください：

• 機能で作られたリスト
  
  
• 数字は、長さが数字を表すリストから作成されます
  
  
• length
  
  
  
  これはリストを受け取り、その長さを数値（長さがこの数値に等しいリスト）として返す関数です
  
  
• そして今だけ決定しましたがlength
  
  
  
  、かなり長い間（リストの長さを使って数字を表現する）数字を使ってきました！
  
  

あなたはすでにめまいを感じましたか？そうでない場合は、これを見てください：

(define mylist (prepend empty_list (prepend empty_list empty_list ) ) ) (define mylistlength (length mylist))

var mylist = prepend(empty_list, prepend(empty_list, empty_list)); var mylistlength = length(mylist);

mylist



これは、2つの空のリストのリストです。



mylistlength



これは長さmylist



です...



「2つ」があり



ます... 2つの空のリストのリストで表されます...



そしてこれですmylist



！

4結論

このちょっとした混乱した話が好きなら、The Little Schemerを読むことを強くお勧めします。これは、プログラミングに対する私の理解を実際に変えた最初の本の1つです。そこでSchemeが使用されていることを恐れないでください-言語は本当に重要ではありません。



また、この記事のすべてのコードを使用して要旨（ここでは元のJavaScriptの例）を作成しました。自由にフォークして、実験に使用してください。



また、再帰関数を練習するには、次を実装できます。

• append
  
  
  
  -リストの最後にアイテムを追加する
  
  
• concat
  
  
  
  -2つのリストを結合する
  
  
• min
  
  
  
  およびmax
  
  
  
  -2つの数値の小さい方（大きい方）を見つける
  
  
• remove
  
  
  
  -と同じですfilter
  
  
  
  が、テスト関数（述語）が返す要素のリストのみを返します#f
  
  
  
  
  
  
• contains_number
  
  
  
  -数値がリストに属しているかどうかを確認する
  
  

または、もっと深刻なものが必要な場合は、作成済みの概念に基づいて大規模な概念を実装します。

• 負の数
  
  
• 非負の有理数
  
  
• 負の有理数
  
  
• 連想リスト
  
  

重要なのは、実際のコンピューターでうまく機能するものを作成することではないということです。適切な電圧を得るためにトランジスタと回路の特定の組み合わせを取得する方法を考える代わりに、美しく完璧な抽象的な意味で「コンピューティング」を考えてください。