LIST.md

Lab42::List a linked list implementation with a LISP like API

As for when to use a linked list and when not, this is not the scope for a detailed discussion.

However a some very quick guidelines

Introduction

Use a linked list

• When you access only a bound number of elements from the top (e.g. a stack)

• When your list size is bound to a relatively small number (depends on a lot of factors but 100 should not be a problem) unless the other constrains listed here hold

• When you push often to the top of the list

• When you remove often from the top of the list

• The length is tracked though and is of complexity O(1)

• List is immutable and thusly thread safe

• List paired with the ListOf constraint creates an efficient way to update list attributes in DataClass instances with O(0) constraint validation (unless you use merge(list: ...)

As a résumé, when your use case is similar to a stack

Do not use a linked list

When the following operations which are all O(n) may be too costly (see above for when n should not be a problem)

• Random Access à la list[k]

• Appending and reading the end

• Traversing (that includes reversing) the list with its Enumerable API Though a typical use case is ok:

  • Start with an empty list

  • Extensive computations pushing elements to the top

  • Eventually and only once reverse the list (into an array)

Context: API

Base Constructor cons

Given we constract a list with Nil

    let(:list) { Lab42::List }
    let(:my_list) { list.cons(42, Nil) }

Convenience Constructor

And with the convenience constructor

    let(:same_list) { List(42) }

Then they are actually the same

    expect(my_list).to eq(same_list)

And the convenience constructor is actually nothing other than:

    expect(List(1, 2)).to eq(list.new(1, 2))

And remark also that the constructor can return Nil

    expect(List()).to eq(Nil)

Context: Length

As mention in the README.md length is tracked and can be computed in O(n)

And therefore

    expect(List(*1..100).length).to eq(100)
    expect(Nil.length).to eq(0)

Context: PatternMatching

By the nature of a linked list we can deconstruct it only into car and cdr

Given a list

    let(:for_match) { List(:a, :b) }

Then we can pattern match as follows:

    for_match => [h, t]
    expect(h).to eq(:a)
    expect(t.car).to eq(:b)

And for edge cases we have

    List(1) => [_, t]
    expect(t).to eq(Nil)

And Nil only matches the empty list

    Nil => []

Context: Enumerable

⚠️ using the Enumerable mixin means O(n)

But if you can afford it ;)

Given a list like

   let(:letters) { %w[alpha beta gamma delta epsilon sita] }
   let(:a_list) { List(*letters) }

Then we can happily use the Enumerable mixin

    expect(a_list.to_a).to eq(letters)

And a lazy version might be preferable

    expect(a_list.lazy).to be_kind_of(Enumerator::Lazy) # same as YHS