15

I'm implementing a simple linked list and to denote the fact that there is no next node, I'm using the value Nil. The thing is that when assigned to a container, Nil will attempt to revert the container to its default value which means I need to use the container's default value or Any to determine if the linked list's end has been reached. However, I'd still like to use Nil (if only for its clear intent) and no other value to test for the non-existence of a next node in the code (e.g., until $current === Any, last if $current-node === Any;). For some context:

class Node {
    has $.data is rw is required;
    has $.next is rw = Nil;
}

class UnorderedList {
    has $!head = Nil;
    
    method add(\item --> Nil) {
        my $temp = Node.new: data => item;
        $temp.next = $!head;
        $!head = $temp;
    }

    method size(--> UInt) {
        my $current = $!head;
        my UInt $count = 0;
        
        until $current === Any {          # <=== HERE
            $count += 1;
            $current .= next;
        }
        
        return $count;
    }
   
    method gist(--> Str) {
        my $current-node = $!head;
        my $items := gather loop {
            last if $current-node === Any; # <=== HERE
            take $current-node.data;
            $current-node .= next;
        }
        
        $items.join(', ')
    }
}
Improve this question
3
  • Before attempting to understand the problem or answer, wouldn't it be a better idea to create a "None" value totally unrelated to Nil with its own semantics? Commented Jul 5, 2020 at 15:24
  • Again, not trying to answer, but IterationEnd is also intended for that purpose. Still haven't got into your problem, but it might be that using Nil is precisely the problem. Commented Jul 5, 2020 at 16:44
  • 2
    IterationEnd is really an implementation detail that is only documented to help developers of classes that implement the Iterator role. It should not be used anywhere else, as it can create unexpected effects, especially as soon as such a value is produced by an Iterator. Commented Jul 5, 2020 at 16:51

3 Answers 3

Reset to default
10

This is a bit like asking "how can I still have rain fall on my head while using an umbrella". :-) The primary reason Nil exists in Raku is to provide a value that a function can return on a soft failure to produce a result, which will be safe if assigned into any container that supports being undefined (or defaulted).

Thus, one can write a function func that can return Nil, and it will Just Work for a caller my SomeType $foo = func() or for a caller my OtherType $bar = func().

While there is the is default(Nil) trick, I'd strongly suggest using some other value as your sentinel. Trying to use a language feature in a situation where you don't want the primary behavior it exists to provide will generally not go smoothly.

The Node type object itself would be a reasonable choice. Thus this:

has $!head = Nil;

Becomes:

has Node $!head;

And the test becomes:

until $current === Node {

However, I'd probably write it as:

while $current.defined {

Which also supports subclassing of Node. On the other hand, if I know Node is an implementation detail of my class, I'd feel safe enough to use rely on the default boolification semantics to remove the clutter:

while $current {

Meanwhile, this:

last if $current-node === Any;

Could become:

last without $current-node;

Or for consistency if choosing the "rely on the boolification" approach:

last unless $current-node;

Finally, if Node is just an implementation detail, I'd move it inside UnorderedList and make it my scoped.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

8

Some choices, with the ones I would find most appealing toward the top, and one I would positively discourage at the bottom:

  • Use Node (the type object of your Node class). This is the option jnthn recommends. This would make sense to all rakuns familiar with Raku's distinction between defined and undefined values, and would be especially convenient if you add Node type constraints to node variables. Imo this would be the idiomatic solution.

  • Use Empty. It arguably has most of the same positives as Nil without most of the negatives I perceive and discuss later in this answer. If you go with Empty (or End or whatever) you can create a subset MaybeNode where Node | Empty or whatever to allow for adding a type constraint to a node variable. (Though such boilerplate mostly serves just to highlight the simple elegant ergonomics that underly the option of using Node.)

  • Use is default(Nil) to set the default for the node attribute. This is the option Liz suggested. Again, one can use, say, is default(Empty) as part of using anything other than Node.

  • Pick a new name. None might be a poor choice because it has an established meaning in many languages that has yet other semantics. Perhaps End? (Declared as, say, role End {}.)

  • Declare your own Nil and lexically shadow Raku's built in Nil. I would say that that's a crazy thing to do; and would remonstrate against it if I were to peer review your code; and would anticipate most rakuns agreeing with me; but you could.

Further discussion of the options

Per Nil's doc, its definition is:

Absence of a value or a benign failure

Imo this overloading is genius on Larry's part. But it is best respected for what it is. It's not just an overloaded semantic but explicitly so. Continuing with the doc:

Failure is derived from Nil, so smartmatching Nil will also match Failure. ... Along with Failure, Nil and its subclasses may always be returned from a routine even when the routine specifies a particular return type [even] regardless of the definedness of the return type.

All of these semantics will mentally and actually apply to your code even if you don't want them. Are you absolutely sure you want them? See my first reply to @ElizabethMattijsen in comments below this answer for a brief discussion of the sort of troubles I'm suggesting this can lead to. And another is that folk reading your code could think of the same troubles. This is arguably an unnecessary overhead.

On the other hand, such troubles (actual rather than imagined) are pretty unlikely even in fairly complicated code. And your code is very simple. So my focus on this failure aspect is overblown for your provided scenario. And Liz's solution is simple and nice.

On the gripping hand, it's also nice to adopt simple solutions that are most generally applicable, even for the most complex code, and to expose newbies to those simple and general solutions early on. Also it's possible that you were interested in hearing about the range of options. And of course I might be wrong about what I write and get good feedback. Hence this answer.

I'd still like to use Nil (if only for its clear intent)

If the code is only for your eyes, then whatever you find clear is for you to decide.

Imo the clear intent of Nil to those who know Raku is to symbolize Raku's Nil.

Raku's Nil has the specific semantics I quoted above.

To the degree someone focuses their attention on "absence of a value", your solution will seem perfectly cromulent. To the degree they focus on "benign failure", and consider how this semantic is used throughout Raku, they may raise an eyebrow. Clearly, reaching the node that has no next node fits pretty well with "benign failure" as well as "absence of value". Indeed, this is why Larry overloaded them. But other code is also using Nil to mean these things, and they probably don't mean "end of link list".

A similar mixed story applies to Node and Empty, but with different flavors.

Node makes a lot of sense because it's idiomatic in Raku that a type object is undefined, and you can type constrain a node variable and it'll accept Node. But it's also an idiomatic way to represent something being uninitialized. Do you really want that overloaded semantic? Maybe it's fine, maybe it's not.

Empty makes sense because it reads well, is undefined like Nil and Node (but without their other unwanted semantics), and the chances of encountering it by mistake are vanishingly small. Its downsides are that it misses the nice idiomatic duality of Node for defined / undefined values; it's not quite as ultra safe as a new locally defined name (eg End); someone might wonder why your code is using a Slip; and it's by definition not going to be quite as appealing to you as Nil given your stated preference.

Improve this answer

4 Comments

I think "test for the non-existence of a next node in the code" matches "explicitly indicate that no value is present", and that therefore Nil and is default(Nil) are a valid way of approaching this.
@ElizabethMattijsen I'm not saying it's not a valid approach. Raku's built in Nil explicitly indicates no value is present or benign failure. Any code that fails is free to return Nil to indicate it went wrong in a manner it wishes to indicate is benign. But it may not be benign. If, when writing linked list code, one is confident it will never evolve in its lifetime to encounter some code that has a benign failure (or a bug that manifests as if it were a benign failure) in such a way that that gets written as the link value then sure. But imo the idiomatic solution would be Node.
hi @raiph - great, comprehensive answer (as usual), it did send me searching for the Node type on rakudocs, until I realised you mean the type object of the class that uxlzzzz defined - so suggest a short edit to your answer to explicitly state that (?)
@p6steve Oops. Fixed. Thanks. :)
4

The answer is: Nil can also be a default value. So instead of saying:

has $.next is rw = Nil;

all you have to do, is:

has $.next is rw is default(Nil);

Assigning Nil to such an rw attribute, will give you Nil.

Improve this answer

3 Comments

A pretty straightforward solution! However, the issue I encountered is that I must declare with is default(Nil) any variable that stores $!head and that will subsequently be "iterated over" (e.g., $current-node) if I wanted to keep using the value identity comparison. Using raiph's first point does the trick a little bit cleaner while also making the intent clear ((defined vs undefined). Although to be honest, using the value identity operator (===) was a bit of an overkill and relying on Raku's defined and undefined values would've done the job too.
I was going for your comment "However, I'd still like to use Nil (if only for its clear intent)", and gave you the answer to that. But indeed, TIMTOWTDI :-)
Thanks for your answer! TIMTOWTDI indeed :-)!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.