Re: [Outreachy] Use of impure functional programming and use of vlists

["Ludovic Courtès" <ludo@gnu.org>]

Hi Magali,

Magali Lemes <magalilemes00@gmail.com> skribis:

> As my Outreachy internship approaches an end, I'd like to know which
> of the following options is better for walking and displaying the Git 
> commit history:
> 1) having a list and then using for-each it to display the commit
> information;
> 2) display the list while building it.

In addition to Arun’s suggestion, an option would be to achieve #2 while
keeping a functional approach; this can be done using SRFI-41 “streams”.

Streams are lazy lists, meaning that the elements of a stream are
computed on demand.  If you do:

  (use-modules (srfi srfi-41))

  (stream-for-each (lambda (n)
                     (pk (car (gettimeofday)) n))
                   (stream-cons 1
                                (stream-cons (begin (sleep 2) 2)
                                             stream-null)))

You’ll see that the first element is printed before we sleep for two
seconds.

I don’t know if this could work in your case; the Guile-Git API is eager
(as opposed to lazy), so maybe it’s not directly applicable.

> Another question is, could vlists be used? Since it would be fast to
> have the commits in a hash table implemented with vlists, we could use 
> 'vlist-for-each' to display the commits. I haven't seen vlist-for-each
> being used anywhere in Guix, so I wondered if there's a special reason 
> for it not being used, or if it hasn't really been necessary at all
> thus far.

Vlists are a sort of immutable data structures for vectors; for a
regular list, the cost of random access is linear in the size of the
list, whereas for vlists random access is “typically” constant-time,
almost like a vector.

The graph of commits is usually traversed linearly, so the complexity of
random access doesn’t matter much.  Likewise, in Guix proper, there are
probably few or no occasions where we need vector-like structures, which
is why vlists are not used.

HTH!

Ludo’.