From Array to List with transformation in the middle


#1

Hello,
Is there any way to turn an array into a List while you transform the elements that it contains?
The reason is because I want to read the files from a directory, add some metadata and return a List. It will be awesome if I can iterate it just once.
I looked using function signaturess in the array documentation and I don’t see anything there.

Regards


#2

AFAIK the closest you can get without writing your own is either Array.to_list followed by List.map, or Array.map followed by Array.to_list, both of which will create one intermediate data structure. I think the latter should be more efficient, though.


#3

What do you mean with writing my own? My own function for doing it or my own function to list a directory :smile:?
I think the method that I’m looking for is fold, but that will probably reverse the resulting list if I want to build the list efficiently (prepending instead of appending) that’s my guess.


#4

I can always use fold_left, but I don’t know if it is as efficient as fold. I understand that it is because array has good access to random elements, so iterating sholud be equally cheap, right?


#5

Your own function for converting the array to a list. You can do it in one pass by iterating over the array from the end, building up the list starting from the last element. I believe fold_right does this.


#6

This is what I ended with:

let listDir = dir => {
  open Caml
  Sys.readdir(dir) |> Array.fold_left((files, name) => {
    let path = Filename.concat(dir,name);
    [ Sys.is_directory(path) ? Folder(path,name) : File(name) 
    , ...files
    ]
  }
  ,[])
}

Maybe it should be fold_right, :smile: sometimes I confuse left and right


#7

That code looks pretty good to me.

If you think about how lists are constructed, a left fold will give you the files in reverse order. Right fold is probably what you want (unless the order doesn’t matter).


#8

Yes, right fold is what I was looking for, and it was my intention to use it from the beginning because, as you said, lists are build from the bottom up. But sometimes I write left when I want to write right. Something that has started to happen to me a bit recently.
Thanks for validating my code @spyder!


#9

If speed is important, I’d recommend considering/trying not concatenating, but instead initially creating a new Array of the correct length (but with a starting value), then filling each element. Concatenation can take a while. This seemed to help the performance of a a function I wrote, though also made it more messy in the process.


#10

Where do you see array concat on my example? I appreciate the advice, but I don’t see how it applies here


#11

it’s a common confusion for JS programmers coming to reason, [x, ...xs] is array concat in JS

In reason this is list syntax, not backed by an array, so it’s O(1)


#12

Oh, I see.
In fact, I know that but I completely overlooked that on my example.
At the end I am using a bit different solution, and I’m aware of the cost of list concatenation. In fact on my final solution I’m using fixed size arrays for string creation.
In any case, I’m using more caml syntax than reason, where it is a bit harder to make this kind of mistakes.
But, I appreciate both comments because It’s always nice to get good practices reminded.