4

これまでの私の知識レベルは、The Little Schemer を問題なく完了した程度であり、現在、The Seasoned Schemer を 70% 完了しています。頭の片隅には、Scheme を使った実世界での経験を積むために取り組みたいプロジェクトのアイデアがありますが (おそらく、キャリアを通じて主に OO 言語を扱ってきたため)、どのようにすればよいのか、いまだに疑問に思っています。 OO 言語に対するいくつかのかなり基本的な問題に、Scheme のような関数型言語で取り組むことができます。

すべての質問を 1 つの stackoverflow の質問に押し込むのではなく、時間の経過とともにそれらを少しずつ取り出して、断片が所定の位置に収まると想定するので、実際には他の質問への回答は必要ありません。

Scheme がリストであることは明らかです。リストとリストのリスト。私は、すばやく取得できる (つまり、ハッシュ) "属性" を含むリストを格納し、別のリスト内に入れ子にすることができることに慣れています。

ファイル システム内のファイルとディレクトリのリストを再帰的に渡す例を挙げると、Scheme でこのようなアプローチを行うにはどうすればよいでしょうか。次の形式のデータ構造を渡すことができると思います。

'(("foo" (("bar.txt")
          ("zip.txt")
          ("button.txt")))
  ("other.txt")
  ("one-more" (("time.txt"))))

各ノードがリストの car として表され、その子がその cdr の car に含まれる別のリストとして表される場合、上記は次のツリー構造になります。

foo/
  bar.txt
  zip.txt
  button.txt
other.txt
one-more/
  time.txt

それとも、ある種のディープ ツリー トラバーサルを行う代わりに、ビジターを受け入れるイテレータ関数を渡すでしょうか? (ディレクトリをいつ切り替えているかを知るという点では、それがどのように見えるかは完全にはわかりません)。

この種の問題に関しては、ディレクトリ ツリーだけでなく、ツリー構造 (メタ データが添付されている) 全般に一般的なパターンはありますか?

オブジェクト指向の同等物と比較すると、これは必然的に非常に手間がかかりますか?

4

2 に答える 2

6

あなたの質問には 2 つの部分があります。

パート 1: Scheme でツリーを実装する方法。

標準の R5RS では、ほとんどのツリー実装でベクトルを使用してツリー内のノードを表します。1 つのバイナリ ツリーの場合、いくつかのヘルパー関数を定義できます。

(define (tree-left t) (vector-ref t 0))
(define (tree-right t) (vector-ref t 1))
(define (tree-value t) (vector-ref t 2))
(define (make-node l r v) (vector l r v))
(define (leaf? t) (eq? t #f))

構造/レコードを含むスキームでは、上記は次のように置き換えられます>

(define-struct tree (left right value))
(define (leaf? t) (eq? t #f))

構造の階層がサポートされている場合は、次のように記述できます

(define-struct tree ())
(define-struct (leaf tree) ())
(define-struct (node tree) (left right value))

ツリーを操作するパターン マッチング コードをサポートするスキームの場合、ML や Haskell でツリーを処理するコードのように見えます。

HtDP のバイナリ検索ツリーに関するセクションをお勧めします: http://htdp.org/2003-09-26/Book/curriculum-ZH-19.html#node_sec_14.2

パート 2: ディレクトリ トラバーサルの処理方法

いくつかのアプローチがあります。一般的な方法の 1 つは、指定されたディレクトリが一度に 1 つの要素 (ファイルまたはサブディレクトリ) を生成できる関数またはシーケンスを生成する関数を提供することです。これにより、潜在的に巨大なファイル ツリーをメモリに格納する必要がなくなります。

Racket では、シーケンスを使用できます。

#lang racket
(for ([file (in-directory "/users/me")])
   (displayln file))

R5RS で利用できるディレクトリ トラバーサル メカニズムはありませんが、もちろん、すべての主要な実装では何らかの方法でそうすることができます。

ところで: 確かに、Scheme は単一のリンクされたリストに対して非常に優れたサポートを提供しますが、機能的なデータ構造を実装する場合は、ランダムな要素へのアクセスが高速なため、ベクトルまたはさらに優れた構造を使用する方がよいことがよくあります。

于 2012-06-22T13:54:23.373 に答える
6

Scheme がリストであることは明らかです。

伝統的に、はい。しかし、R6RS 以降では、名前付きフィールドを持つレコードもあり、他の種類のデータ構造の操作がはるかに簡単になります。実用的な Scheme の実装には何十年もの間、これらがありましたが、標準化されていなかったため、構文はさまざまです。

この種の問題に関しては、ディレクトリ ツリーだけでなく、ツリー構造 (メタ データが添付されている) 全般に一般的なパターンはありますか?

はい、そして「イテレータ関数」のアイデアで、頭に釘を打ちました。(ただし、代わりにマクロを定義する方がより洗練されているため、次のように言えます。

(for-each-label (x tree 'in-order)
  (display x))

マクロは で作成されdefine-syntaxます。)

于 2012-06-22T10:15:58.030 に答える