Samson's machete

Simple solution to mkdir a tree

Posted by NalaGinrut on 1 March 2015 1:18 AM (algorithm | scheme | guile | data structure | tree | dfs | artanis | high order function | fp)

The problem

Yesterday night I've written command line interface (CLI) for GNU Artanis, after took care of my daughter to sleep, I had only one hour to hack something.

My aim is to add `art create proj-name' command to create a bunch of files/directories for initializing a new Artanis web app. Just like Rails does. Well, since my Turing brain has limited time for this hack, I have to choose my favorite way to traverse the tree for this job, the recursive way. ;-)

Depth first traversal

One of the proper way to mkdir a directory tree is to use DFS. I chose the pre-order DFS.

If you have well structured Tree implementation like this, then the pseudo code below could be simple enough to try.

;; This is pseudo code
(define (preorder node visit)
   ((leaf? node) #t)
    (visit node)
    (for-each preorder (children node)))))

Actually, the same algorithm is used in my unfinished data-taistructure lib Nashkel. Could be optimized to iterative one though...

Tree structure

Here's a problem: I don't known if I'll add/remove directories in the future, so I need a flexible design to let me do this job easily. A proper tree design is a good start.

For example:

|-- app
|   |-- controller
|   |-- model
|   `-- view
|-- lib
|-- log
|-- prv
|-- pub
|   |-- css
|   |-- img
|   |   `-- upload
|   `-- js
|-- sys
|   |-- i18n
|   `-- pages
|-- test
|   |-- benchmark
|   |-- functional
|   `-- unit
`-- tmp
    `-- cache

In Scheme, the most convenient data structure is the list:

(define *dir-arch*
  '((app (model controller view)) ; MVC stuff
    (sys (pages i18n)) ; system stuff
    (log) ; log files
    (lib) ; libs
    (pub ((img (upload)) css js)) ; public assets
    (prv) ; private stuff, say, something dedicated config or tokens
    (tmp (cache)) ; temporary files
    (test (unit functional benchmark)))) ; tests stuffs

Let me explain this tree structure built with list, since the algorithm implementation has something to do with the data structure design. I gave the rule below:

((node1 (child1_1 child1_2 ...))
 (node2 ((node3 (child3_1 child3_2 ...)) child2_1 child2_2 (node4 (child4_1 child4_2 ...)) ...))
 (node5) ; no any children

The disadvantage of this tree is hard to modify dynamically (alright, you may use set-car! and set-cdr!). But it's easy to handle statically, because the hierarchy is clear.

Design the high-order-function

Now that I'm using Scheme, I'll choose FP way containly. High order function just like design pattern of FP. Design a good and generic one will save your lot time in the future development.

Here is mine:

(define (dfs tree visit level)
  (match tree
    (() #t)
    (((r (children ...)) rest ...)
     (visit r level)
     (for-each (lambda (x) (dfs (list x) visit (cons r level))) children)
     (dfs rest visit level))
    (((r) rest ...)
     (visit r level)
     (dfs rest visit level))
    ((children ...)
     (visit (car children) level)
     (dfs (cdr children) visit level))))

So it's easy to mkdir a directory tree now:

(define (create-framework)
  (define (->path x l)
    (format #f "~{~a~^/~}" (reverse (cons x l))))
  (dfs *dir-arch* (lambda (x l) (mkdir (->path x l))) '()))

This CLI feature won't appear in 0.0.3, and because it'll bring great change to GNU Artanis, maybe it should be in 0.1.0. Dunno...

Happy hacking!

5 responses

  1. Essay writing company says:

    Nice Post, I assume i have located suitable article.I have have a look at it often and also have many feelings. I were given many precious factors from this single publish to growing my knowledge approximately this concern remember or state of affairs of your submit. I'm hoping it's far actually very attractive for the readers who're interested to read such topis stocks assume so one can go to your web page more.

  2. says:

    Hey there, thanks for the post! That;s what I was looking for, really helped me out there! I've recently started to code a bit in my free time, so I will definitely try to make this by myself to remember it. Thanks a lot again! Keep up making posts like this, wanna be better at coding!

  3. Buy A Research Paper Online says:

    There is much pro course in fields of swap for that need particular aptitude, for example, necessary to be a pilot. There is a variety of informative open door.

  4. Can Someone Do My Essay For Me says:

    The look however don't stroke translation of Open Source, depends on sources, now being utilized to fiddle management in Europe. The chance that folks who request gratis programming Open foundation they articulate don't know what it implies

  5. UK Essay Writing says:

    This works as mkdir -p' does not produce errors if the entire information bank it is asked to generate already exist.

Comments are closed.