Persistent Lists

The last post was a bit long and theoretical, this is going to be more practical. The problem is how to implement persistent lists operations, like concatenation or updating an element of list.
    First, concatenation, in the imperative way we can easily do it by changing pointers: make a tail of the first list pointing to the head of the second. Lists are concatenated after that, operation performs in constant time, but both lists are destroyed now. If we want to concatenate and have the old lists available, it should be done in that way: make a copy of the last node of the first list and make it pointing to the head of the second, and then make a copy of the before last node of the first list and make it pointing to the last one of the first list and so on... This leads us to the recursive algorithm:

fun-concat(lst1, lst2){
    if ( is-empty(lst1)) return lst2
        else
           return cons(car(lst1),   fun-concat(cdr(lst1),lst2))
 }

Cons, car, cdr, is-empty, accordingly means: adds element to the beginning of the list, returns the first element, returns the list of all but not the first and is-empty check if a list is empty. After this operation the old lists are still available, but there is a cost: it takes now linear O(n) time - tradeoff persistence for time. This pseudo cod may by easily transformed into Clojure:

(defn my-concat [xs ys] (if (empty? xs) ys 
  (cons (first xs) (my-concat (rest xs) ys))))

And Python:

def myConcat(xs, ys):
 if(myEmpty(xs)==1):
  return(ys)
 else:
  return([myHead(xs)] + myConcat(myCdr(xs), ys))

Python possible has cdr and head, but I just wrote my own, code available here.

   Another essential function is updating element. To do it in functional style we have to: copy the changed element of the lists (this affects node before this element), so we copying node before it and before it, and so on. So, actually we have to copy not the whole list, but all the nodes, that have pointers to the changed element. Algorithm in Clojure:

(defn my-update [xs n ys] 
      (cond 
      (empty? xs) (throw (Exception. "Can't change empty list!"))
      (= n 0) (cons ys (rest xs))
   :else
              (cons (first xs) (my-update (rest xs) (dec n) ys))))

And Python:

def myUpdateElement(xs, n, y):
 if(myEmpty(xs)==1):
  raise ValueError("Can't change an empty list")
 elif(n > (len(xs)-1) or n < 0):
  raise ValueError("Index Out Of Range")
 elif(n==0):
  return([y] + myCdr(xs))
 else:
  return([myHead(xs)] + myUpdateElement(myCdr(xs), dec(n), y))

This algorithm is a conditional statement: if list is empty raise error; in the case of changing first element of the lists, just cons new element to the rest of the list (base case of recursion); and when changing different than the first, recursively call function with decremented index - what does the job. That's it, it was the very base introduction to persistent lists operations; that code maybe ported to java or C++, and be use to perform persistent operations on mutable objects (like lists in java and python). Next time trees! Let the source be with you!

PS Clojure code here.