Motivated by the first paragraph, I searched more information in order to understand terms like constant time operation and scale of algorithmic complexity. I also understood that giving a type the attribute mutable depends on how one implements the functions that operate on it (that’s what I understood from the “join” example - I don’t know if I understood correctly - and I also don’t know if other factors contribute in making a type mutable). While implementing the functions I didn’t know that the targeted algorithmic scale is O(n) for linked lists. I think that functions like take, select, (map?) have that algorithmic scale.

-finite set of ordered “Cons” elements, in which the last one points to another-earlier placed one in the finite “Cons” chain ( I believe this is what you explained in the last paragraph): this loop is something that isn’t supported ( to be created automatically by the above code / such constructor function doesn’t exist)

1st thought: Not correct ConsList[A, ConsList[B, ConsList[C, next]]

2nd thought: what I want to achieve in C code

//list of integers
typedef struct node
{
    int d;
    struct node*next ;
} Node ;

typedef Node * Node_ptr;
typedef Node * LinkedList;

int main(){
    Node first;
    Node second;
    Node third;

    //creating an actual loop
    first.d = 1;
    first.next= &second;
    second.d = 2;
    second.next = &third;
    third.d = 3;
    third.next = &first;

};

3rd thought: Wolfram Code

(*shorter code*)
x=10 (*number of loops*)
Nest[ReplaceAll[next :> ConsList[A, ConsList[B, ConsList[C, next]]]], 
 ConsList[A, ConsList[B, ConsList[C, next]]], x]
(*new memory (I think) is always being captured by looping in order to save the extended symbolic expression*)
(*I had this code but I didn’t think of using it because I am using replacement and not actual pointers - without ReplaceAll and Nest the expression ConsList[A, ConsList[B, ConsList[C, next]]]  (same with thought 1) isn’t actually pointing to itself*)

-infinite set of ordered “Cons” where the next IDs depend on the previous ones: I don’t know how to define the “end” element in order to implement such a “join” function. But I thought that maybe the code could be improved according to the following idea: when expanding an infinite “Cons” (finding the IDs until a certain extend) the found IDs can be saved so that they won’t have to be re-calculated in every operation until this extend + further extend would be based on the previous one. The above implementation recalculates the values when operating on them. This has both advantages and disadvantages for sure.

Thank you for your detailed answer and sorry for the late response. It turns out that I needed a little bit of time in order to think about my answer. Maybe my answer ended up being too long.

That clarifies the project goals and means.

As for complexity, my interest is far more run time than source code length. The idea is this. Say you have a (linked) list of length n, for n large. Consider the task: Traverse it, do some constant time operation on each element, perhaps replace the element with the result of that computation. You would want this to scale as O(n). If it scales say as O(n^2) then there is a problem.

Similarly, suppose you want to join ("Cons") a pair of such lists. This should be constant time; a good implementation will retain pointers to both first and last elements in each pair, and it is then constant time to hook them and adjust the last pointer of the initial list. This assumes you want these structures to be mutable, rather than to make new copies whenever there is a change. Which I believe is a plausible assumption for a linked list structure at least in the setting you describe. Also it assumes there is always an "end" element.

In your case you might want to allow the situation where the last element points to the first (or any other in the list, even to itself). This is to emulate infinite lists for example. This goes a bit outside of lists/trees and into graph structures. This can be finessed with linked lists but the bookkeeping will be trickier. But this is somewhat outside the scope of my original questions.

I gather the main goal is to simulate lazy infinite evaluation. But this does look rather Lisp-like, with a linked list emulation and related functionality. If that is the intent, have you checked that the algorithmic complexity of various operations is as expected for linked lists?