Pythonの関数を使用して簡単なデータ構造を作成する

はじめに ：去年の夏、私は壮大なSICPの本を発見しました。本の最初のセクションだけを読んで、関数プログラミングの新しい世界を開いてくれました。 匿名関数、関数を返す関数、高次の関数。 本の2番目のセクションで、著者は、関数だけでペア、リスト、ツリーなどのさまざまなデータ構造を作成できることを示しました。 今日は、Pythonプログラミング言語でこの本のいくつかのアイデアを実装したいと思います。 もちろん、もっぱら機能の助けを借りて。

開始 ：Pythonは、ほぼすべてのプログラミングパラダイムをサポートする優れたプログラミング言語です。 Pythonは理解しやすく、この記事を読むには言語の基本的な知識で十分です。 また、この記事を少し見直す必要もありません。

I.ペアリング。 カップルとは何ですか？
ペアは、おそらく異なるタイプの2つの要素で構成される順序付きセットです。 Python Pythonでは、タプル（ペアはタプルの特殊なケース）は特別なデータ型であり、次のように作成されることに注意してください： p =（a1、a2、..、an） 。 ただし、関数のみを使用することに同意したため、独自のペアの実装を作成する必要があります。

def make_pair(x,y): return lambda n: x if n==0 else y def first(p): return p(0) def second(p): return p(1) 

ちょっと待って！ ただし、make_pairはペアではなく関数を返します。 実際、ビューのペアは、任意の数の引数を取る関数であり、引数が0の場合は最初の要素を返し、反対の場合は2番目の要素を返します。 抽象化のレベルを上げるために、ペアの要素であるfirstとsecondのアクセス関数も作成しました。 ペアの実装が正常に機能することを確認します。

  p = make_pair(5,6) first(p) #5 second(p) #6 p1 = make_pair('hello',6) first(p1) #'hello' 

II。 リストリストとは何ですか？

リストは抽象データ型であり、特定の値が複数回出現する可能性がある順序付けられた値のセットです。

現在、リンクリストを実装しています。これは、リストの可能な実装の1つです。

リンクリストは、コンピューターサイエンスの基本的な動的データ構造であり、各ノードには、実際のデータと、次および/または前のリストノードへの1つまたは2つのリンク（「リンク」）の両方が含まれます

実際、リンクリストは、リストの「ヘッド」とその「テール」の2つの値で構成されるペアとして表すことができます。 たとえば、リスト[1,2,3,4]は次のように表すことができます。

 l = make_pair(1,make_pair(2,make_pair(3,4))) first(l) #1 first(second(l)) #2 

空のリストのサポートを追加します。 空のリストは、アイテムを含まないリストです。 その要素にアクセスするとき、何らかの形でエラーを報告する必要があります。

 def nil(): def closure(n): raise Exception return closure null = nil() first(null) #Exception second(null) #Exception def create_list(x): return make_pair(x,null) 

残念ながら、 1番目と2番目の関数はリストアイテムにアクセスするための直感的な関数ではありません。 頭と尾の機能を使用するのがはるかに一般的です。

 def head(l): return first(l) def tail(l): return second(l) 

Pythonでは、関数はファーストクラスオブジェクトであることを思い出してください
したがって、コードを大幅に簡素化できます。

 head = first tail = second 

リストの基本的な操作は、リストの先頭に新しい要素を追加することです。

 def add_to_list(l,x): return make_pair(x,l) 

すべてが非常に簡単です。新しいリストを作成します。その「ヘッド」は新しい要素になり、「テール」は前のリストになります。
実際のところ、本格的なデータ型（リスト）を作成しているため、ここで停止できますが、おそらくリストトラバーサル操作も考慮する必要があります。

 def iterate_over_list(l,f): if l==null: return else: f(head(l)) iterate_over_list(tail(l),f) 

最も簡単な操作は、すべての要素を調べて、リストの各要素に対して関数fを呼び出すことです。 たとえば、この関数を使用すると、画面にリストを表示できます。

 def print_list(l): def put(n): print n iterate_over_list(l,put) l = create_list(5) l =add_to_list(l,6) l = add_to_list(l,7) print_list(l) #7 6 5 

iterate_over_list関数はどのように機能しますか？ Lが空のリストと等しくなるまで、関数fをリストLの先頭に再帰的に適用します。
次に、リストに基本的な機能操作を実装します。
map（l、f）は、リストを新しいリストに転送し、その要素に関数fを適用する関数です。
filter（l、p）は、ある述語pに対応する要素のみを含む新しいリストを作成する関数です。
累積（l、op、初期） -削減として知られています。

_map関数は再帰的に機能します。リストが空の場合、空のリストを返します。それ以外の場合は、リストの「先頭」が関数fをリストlの最初の要素に適用した結果、「テール」がリストの「テール」に_map関数を適用した結果になりますl。

 def _map(l,f): if null_seq(l): return null else: return make_pair(f(head(l)),_map(tail(l),f)) l = make_list(5) l = add_to_list(l,6) l = add_to_list(l,7) l2 = _map(l,lambda n: n*n) iterate_over_list(l2,pr) # 49 36 25 def _filter(l,p): if null_seq(l): return null else: if p(head(l)): return make_pair(head(l),_filter(tail(l),p)) else: return _filter(tail(l),p) def accumulate(l,op,initial): if null_seq(l): return initial else: return accumulate(tail(l),op,op(initial,head(l))) #      accumulate from operator import add _sum = accumulate(l,add,0) 

そして最後の仕上げはレンジ機能です。 この要素まで読んだら、おそらくこの関数を自分で実装できるでしょう。


結論の代わりに
もちろん、「実際の」プログラミングでそのような手法を使用する人はいませんが、この記事が関数型プログラミングに慣れるのに役立つことを願っています。