Arc Forum | Small Idea For List Processing Functions...

Arc Forum

Small Idea For List Processing Functions...

2 points by drcode 6103 days ago | 14 comments

I noticed something today: In arc it appears 'nil is destructurable as multiple nils. For example, here's a crude list printing function:

  (def print-list ((a . b))
     (when a 
        (prn a) 
        (print-list b)))

This function can be used in the expected way:

  >(print-list '(a b c))
  a
  b
  c

Unfortunately, the function has a small wart- It will fail with a nil value in the list:

  >(print-list '(a b nil c d))
  a
  b

...then it occured to me: Any list can have its car taken, except the empty list- An empty list is unable to "supply" the car as a value. In my mind, this is analogous to failing to supply a parameter to a function...

So what if we allowed the car value to be an optional parameter, which the empty list would "fail to supply":

  (def print-list (((o a 'end) . b))
     (when (isnt a 'end) 
       (prn a) 
       (print-list b)))

(This currently does not work)

This would fit perfectly into the current optional parameter syntax. Having an explicit ending value is usually no problem: For almost 99% of list processing functions there is an acceptable choice for an ending symbol such as this, from my experience...

...just an idea...

1 point by bogomipz 6102 days ago | link

I think the most interesting aspect of this discussion is that it shows a problem with destructuring a list you want to recurse over.

Traditionally, your function would be written like this;

  (def print-list (lst)
     (when lst 
        (prn (car lst)) 
        (print-list (cdr lst))))

This works as expected and is what lispers have done for half a century. The root of your problem is that the original cons is lost when the function destructures it to a and b, so you cannot do the above test.

Existing languages that support argument destructuring, AFAIK do so through pattern matching. In this case the problem does not exist because the matching is the branch.

Imagining Arc with pattern matching, your function would look something like this;

  (def print-list (nil)
     | print-list ((a . b))
       (prn a)
       (print-list b))

EDIT:

This can already be done with almkglor's pattern matching library;

  (require "lib/defpat.arc")

  (defpat print-list (nil) nil
                     ((a . b)) (do
          (prn a)
          (print-list b)))

-----

2 points by pg 6103 days ago | link

I don't think I understand. Can you give me an example of function that would take advantage of an optional parameter in that position?

-----

1 point by drcode 6103 days ago | link

The basic idea is:

  arc> (def foo ((a . b))
                a)
  #<procedure:  foo>
  arc> (foo nil)
  nil

...the reason it returns nil is I think because (car nil) in arc is nil. I think this is the Right Thing overall, even though an empty list doesn't really have a car.

However, in the case of parameter destructuring we could do better, because during destructuring we could (if it worked this way) supply default optional values to have more intelligent handling if a part of a destructuring encounters an empty list and "runs out" of values to destructure. It would look like this:

  arc> (def foo (((o a 'falafel) . b))
                a)
  #<procedure: foo>

  arc> (foo '(bar baz))
  bar

  arc>(foo nil)
  falafel

The value of this would be: 1. List processing functions, among others, could tell when they run out of values for destructuring by checking for the magic optional value 2. It might be possible to get this behavior "for free" without growing the source of arc, since it seems like it might just be a generalization of current destructuring/optional support.

-----

2 points by nlavine 6102 days ago | link

Hmm. A quick check in the arc interpreter reveals that (car nil) and (cdr nil) are both nil, so you're right about that.

However, there could be another reason this is working. In your particular example, the full expanded version of the function call is

  (foo . (nil . nil)),

or in other words,

  (cons foo
           (cons nil
                     nil)).

So it really should be destructuring that way anyway.

Now, having said that, can anyone give a good reason that (car nil) and (cdr nil) are nil? It seems a little strange to me, although I can see that it helps destructuring.

-----

1 point by almkglor 6103 days ago | link

  (from "arc.arc")
  [fn]  (map f . seqs)
   Applies the elements of the sequences to the given function.
      Returns a sequence containing the results of the function.
      See also [[each]] [[map1]] [[mappend]] [[andmap]] [[ormap]]
      [[reduce]]

-----

1 point by drcode 6103 days ago | link

Yes, you could of course use map for the simple example in the post. I didn't want to make it more complicated than necessary for a post- If you want a more complicated example that can't be done with map, here's a function that removes pairs of identical items from a list:

  (def rem-pairs ((a . (b . c)))
      (when a
           (if (is a b) (rem-pairs c)
              (cons a (rem-pairs:cons b c)))))

  arc> (rem-pairs '(d r b s d d e w))
  (d r b s e w)

This function, also, will work in every case but break when there are nils in the list)

-----

1 point by almkglor 6103 days ago | link

For everything else, there's pattern matching (on nex-3's arc-wiki).

  (pat-match:def rem-pairs
    ( (a b . c) )
        (if (is a b)
          (rem-pairs c)
          `(,a ,@(rem-pairs `(,b ,@c))))
    ( (a) )
         `(,a)
    ( () )  ())

Possibly I can make it such that you can even say something like (a ,(b (is a b)) . c) in the pattern guard, but it seems a semi-hard problem.

  ;does not work in current version yet!!
  (pat-match:def rem-pairs
    ( (a ,(b (is a b)) . c) )
      (rem-pairs c)
    ( (a . as) )
      `(,a ,@(rem-pairs as))
    ( () )
      () )

-----

1 point by greatness 6102 days ago | link

I'm still not seeing the win of pattern matching here, I'm afraid. This is actually longer than the standard definition using car/cdr. Maybe it's better for more complicated things, I suppose, but that'll defeat the purpose because it wouldn't be legible at that point (as if it is now).

-----

1 point by almkglor 6102 days ago | link

The big win is that it's assuredly correct, and you don't have to mess around dealing with car and cdr. Crossref def varline in app.arc : arc1 had a bug there because it's ridiculously easy to make a mistake dealing with car and cdr. If you can't find the bug, try rewriting the code into pattern-matching form.

-----

1 point by greatness 6102 days ago | link

I'm not seeing the big win over something like this:

  (def print-list ((a . b))
    (when or.a.b
       prn.a
       print-list.b))

  (def rem-pairs ((a . (b . c)))
    (when or.a.b.c
      (if is.a.b rem-pairs.c
                 (cons a (rem-pairs:cons b c)))))

-----

1 point by drcode 6102 days ago | link

Well, I'd be happy with that, except it doesn't work- There's no way to know with or.a.b if you're at the end of the list or if there's just a nil as a last item in the list. Notice the missing item here:

  > (do (print-list '(nil nil nil)) 1)
  nil
  nil
  1

-----

1 point by greatness 6102 days ago | link

Ah, I see. When destructuring the arguments, if the last argument is nil it is equivalent to not being an item. ie:

  arc> (= a '(1 2 nil))
  (1 2 nil)

has a last destructuring bind of (nil . nil) so 'a would be nil and 'b would be nil, making my code not work and making it impossible to differentiate between the end of the list and the list with a last item of nil.

Even so, it's not that much of a problem:

  (def print-list (args)
    (unless no.args
       (prn:car args)
       (print-list:cdr args)))

This code shares almost the same amount of brevity, though I believe it defeats the purpose of what you were trying to do with the destructuring bind (make the calls to car/cdr disappear).

I don't believe your solution is the right thing to do because it wouldn't make sense for the car to be optional and then not force the cdr to be optional. I do not believe an optimal destructuring solution exists that could improve on the brevity of the original car/cdr solution.

-----

1 point by parenthesis 6103 days ago | link

It would be something like this

  (w/uniq end
    (def print-list (((o a end) . b))
      (when (isnt a end) 
        (prn a) 
        (print-list b))))

to avoid the problem of the symbol end being in the input list.

-----

1 point by drcode 6103 days ago | link

Of course, going down that road makes it bulkier and starts making the brevity less convincing :)

-----