Algorithms for data tree structure in a schema?

Question

My level of knowledge so far is that I graduated from The Little Schemer without any problems, and now I am 70% through The Seasoned Schemer. I mean my ideas for projects that I would like to work on in order to get real experience with Scheme, but (perhaps because I worked mainly with OO languages ​​throughout my career). I'm still wondering how one could solve some pretty simple problems for the OO language in a functional language like Scheme.

Instead of asking all my questions in a single stack question, I just work them out over time and assume that the parts will be put in place, so I really don't need answers to other questions.

It's pretty clear that Scheme is lists. Lists and lists of lists. I’m used to the fact that I can store lists containing “attributes” that can be quickly obtained (ie hashes) and can be nested together.

Taking an example of enumerating a list of files and directories in a file system, recursively, how can one approach something similar in Scheme? I think you could pass the data structure of the form:

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

Where each node is represented as a list car, and its children are represented as another list contained in its cdr car, so the above is a tree structure for:

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

Or maybe someone would pass in an iterator function that takes a visitor instead, which does some kind of deep tree traversal? (Not quite sure how it looks, in terms of knowledge, when you switch directories).

Is there a common pattern when it comes to this problem, not just the directory tree, but tree structures (with attached metadata) in general?

Does this inevitably end up being quite difficult compared to the object-oriented equivalent?

Answer 1

It's pretty clear that Scheme is lists.

Traditionally, yes. But with R6RS there are also records with named fields, which makes it easier to work with other data types. Practical implementations of circuits have had these decades, but they have never been standardized, so the syntax is changing.

Is there a common pattern when it comes to this problem, not just the directory tree, but tree structures (with attached metadata) in general?

Yes, and with your idea of ​​"iterator function" you hit a nail on the head. (Except that it would be even more elegant to define a macro, so you can say:

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

Macros are created using define-syntax .)

Answer 2

I see two parts of your question.

Part one: how to implement trees in a circuit.

In the standard R5RS, most tree implementations use vectors to represent nodes in the tree. For a binary tree with one, you can define some helper functions:

 (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 lrv) (vector lrv)) (define (leaf? t) (eq? t #f)) 

In schemas with structures / records, this is replaced by>

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

If hierarchies of structures are supported, you can write

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

For schemes that support pattern matching code that controls trees, they look like tree-like processing code in ML and Haskell.

I can recommend the section on binary search trees in HtDP: http://htdp.org/2003-09-26/Book/curriculum-ZH-19.html#node_sec_14.2

Part Two: How to handle directory crawls

There are several approaches. One common way is to provide a function that defines a directory of a function or sequence that can an element (file or subdirectory) at a time. This avoids the need to store a potentially huge file tree in memory.

You can use sequences in Racket:

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

There are no directory traversal mechanisms in R5RS, but all major implementations, of course, offer one way or another by doing this.

BTW: It is true that Scheme provides very good support for single linked lists, but when implementing functional data structures, it is often better to use vectors or even better structures due to faster access to random elements.