printing elements for file system tree

Question

I have this tree:

type filename = string
type content = Bytes.t

type fs = 
  | FileContent of content 
  | Folder of (filename * fs) list

let f1 = FileContent(Bytes.of_string "poum")
let f2 = FileContent(Bytes.of_string "think")
let f3 = Folder [("f1.mp3", f1); ("f2.mp3", f2)]
let f4 = FileContent (Bytes.of_string "text")
let f5 = Folder [("my music", f3); ("t.txt", f4)]

and I want to write a function iter with this signature: fs -> unit such that iter f prints the names of the elements in f and recursively applies the call to its elements. The order preferred is not important.

The expected output is:

my music
f1.mp3
f2.mp3
t.txt

I have started this way:

let rec iter f = 
  match f with
  | FileContent c -> ()
  | Folder ((n, f1)::t) -> ...
  | Folder [] -> ()

my problem is that I can recursively call f1 and so on, but how to do that for the list as well? Also Stdlib.Printf.printf c shows red error squiggly line under c.

Update

In a different way, I want to have a traverse func f function (signature: (content -> content option) -> fs -> fs), such that traverse returns the same structure as f where the leaf e = content can be modified according to the value of func e, and if this value is None we keep e, otherwise we return the value of the option returned. Building on the solution of the above question, I tried to this:

let rec traverse func f = 
  match f with
  | FileContent c -> 
    begin
      match func c with
      | Some e -> FileContent e
      | None -> FileContent c
    end
  | Folder ((n, f1)::t) -> 
    traverse func f1;
    traverse func @@ Folder t
  | Folder [] -> Folder []

But the problem is how to return structure fs within Folder ((n, f1)::t) -> , how to do that?

Answer 1

So you've given us this start, which shows that we clearly don't care about printing file content.

let rec iter f = 
  match f with
  | FileContent c -> ()
  | Folder ((n, f1)::t) -> ...
  | Folder [] -> ()

First off, you'll want to print the name of the file. That's easy:

let rec iter f = 
  match f with
  | FileContent c -> ()
  | Folder ((n, f1)::t) -> 
    print_endline n
  | Folder [] -> ()

But there's no recursion, so that prints the first filename and then stops. Next let's recursively print the file contents.

let rec iter f = 
  match f with
  | FileContent c -> ()
  | Folder ((n, f1)::t) -> 
    print_endline n;
    iter f1
  | Folder [] -> ()

But what do we do with t? Well, we recursively print it with iter.

let rec iter f = 
  match f with
  | FileContent c -> ()
  | Folder ((n, f1)::t) -> 
    print_endline n;
    iter f1;
    iter t
  | Folder [] -> ()

Well, now this doesn't compile, because iter expects a fs value, not a list, which is what this is. If we consider that Folder wraps a list, then the solution is to rewrap this list as a folder.

let rec iter f = 
  match f with
  | FileContent c -> ()
  | Folder ((n, f1)::t) -> 
    print_endline n;
    iter f1;
    iter @@ Folder t
  | Folder [] -> ()

Now, recognizing that the actual file contents don't matter, we can streamline this a bit:

let rec iter f =
  match f with
  | FileContent _ | Folder [] -> ()
  | Folder ((n, f1)::t) ->
    print_endline n;
    iter f1;
    iter @@ Folder t

---

As for your additional question (which should be it's own question) you seemingly want to map your tree to another tree, optionally updating file contents.

So let's use the name map and let's slightly rearrange your patterns. Keep in mind your function must always return the same type, so if we have a Folder, the result needs to be a Folder.

We can recursively call map func on the tail of the list after we wrap it in the Folder constructor. We then use pattern-matching to extract the resulting list.

let rec map func = function
  | Folder [] -> Folder []
  | FileContent c ->
    (match func c with
     | Some e -> FileContent e
     | None   -> FileContent c)
  | Folder ((n, f1)::t) ->
    let Folder t' = map func @@ Folder t in
    Folder ((n, map func f1) :: t')

# f5
  |> map 
       (fun c -> 
          if String.starts_with ~prefix:"t" (String.of_bytes c) then 
            Some (Bytes.of_string "replaced") 
          else 
            None);;
- : fs =
Folder
 [("my music",
   Folder
    [("f1.mp3", FileContent (Bytes.of_string "poum"));
     ("f2.mp3", FileContent (Bytes.of_string "replaced"))]);
  ("t.txt", FileContent (Bytes.of_string "replaced"))]