How to combine two strings sorted alphabetically in lisp using recursion

Question

I am learning Lisp. I implemented a generic lisp function that concatenates two strings ordered alphabetically using recursion. Here is my code, but something is wrong, and I did not understand this.

(defun merge (FL) (if (null F) (if (null L) F ; return f ( L )) ; else return L ;else if (if (null L) F) ; return F ;else if (if (string< (substring F 0 1) (substring L 0 1) (concat 'string (substring F 0 1) (merge (substring F 1 (length F)) L))) ( (concat 'string (substring L 0 1) (merge F (substring L 1 (length L)) )) )))) 

Edit: I just want to combine two lines, such as; the input is string a = adf and string b = beg and the result or result should be; abdefg

Thanks in advance.

Answer 1

Judging by your comments, it looks like you are trying to use if with a number of conditions (for example, the else if series in some other languages). For this, you probably need cond .

I replaced if with cond and cleared some other errors and it worked.

 (defun empty (s) (= (length s) 0)) (defun my-merge (FL) (cond ((empty F) (if (empty L) FL)) ((empty L) F) (t (if (string< (subseq F 0 1) (subseq L 0 1)) (concatenate 'string (subseq F 0 1) (my-merge (subseq F 1 (length F)) L)) (concatenate 'string (subseq L 0 1) (my-merge F (subseq L 1 (length L)))))))) 

Your test case came out as you wanted:

 * (my-merge "adf" "beg") "abdefg" 

Answer 2

Using string< is redundant, use char< instead, as shown by Kaz. Recalculation of length at each step will make this algorithm quadratic, so it should be avoided. Using sort to "fake" makes O (n log n) instead of O (n). Using concatenate 'string all the time probably also requires additional costs for unnecessary passes.

Here's a natural recursive solution:

 (defun str-merge (FL) (labels ((g (ab) (cond ((null a) b) ((null b) a) ((char< (car b) (car a)) (cons (car b) (ga (cdr b)))) (t (cons (car a) (g (cdr a) b)))))) (coerce (g (coerce F 'list) (coerce L 'list)) 'string))) 

But, Common Lisp does not have a tail call , not tail recursion modulo cons optimization (even if the latter was described back in 1974 using the "Lisp 1.6 rplaca and rplacd field rplacd operators"). Therefore, we must indicate this as a loop:

 (defun str-merge (FL &aux (s (list nil)) ) (do ( (ps (cdr p)) (a (coerce F 'list) (if qa (cdr a))) (b (coerce L 'list) (if q (cdr b) b)) (q nil)) ( (or (null a) (null b)) (if a (rplacd pa) (rplacd pb)) (coerce (cdr s) 'string)) (setq q (char< (car b) (car a))) (if q (rplacd p (list (car b))) (rplacd p (list (car a)))))) 

Answer 3

There were quite a few good answers, so why should I add another one? Well, lower is probably more efficient than the other answers here.

 (defun merge-strings (ab) (let* ((lena (length a)) (lenb (length b)) (len (+ lena lenb)) (s (make-string len))) (labels ((safe-char< (xy) (if (and xy) (char< xy) (not (null x)))) (choose-next (xy) (let ((ax (when (< x lena) (aref ax))) (by (when (< y lenb) (aref by))) (xy (+ xy))) (cond ((= xy len) s) ((safe-char< ax by) (setf (aref s xy) ax) (choose-next (1+ x) y)) (t (setf (aref s xy) by) (choose-next x (1+ y))))))) (choose-next 0 0)))) (merge-strings "adf" "beg") 

It is more efficient specifically in terms of memory allocation - it allocates enough memory to write the result string, never requires anything (from a list to a string or from an array to a string, etc.). It may not look very pretty, but this is because he tries to make each calculation only once.

This, of course, is not the most efficient way to write this function, but programming absolutely without efficiency considerations will not lead you far.

Answer 4

A recursive way to do this (corrected according to the comment - other solutions can also get the IF form).

 (defun merge-strings (ab) (concatenate 'string (merge-strings-under ab))) (defun merge-strings-under (ab) (when (and (= (length a) (length b)) (> (length a) 0)) (append (if (string< (aref a 0) (aref b 0)) (list (aref a 0) (aref b 0)) (list (aref b 0) (aref a 0))) (merge-strings-under (subseq a 1) (subseq b 1))))) 

---

Here's an iterative way to do this.

 (concatenate 'string (loop for i across "adf" for j across "beg" nconc (list ij))) 

Note that they rely on building a string in a list of characters and then vectorizing it (the string is a character vector).

You can also write a more C-esque approach ...

 (defun merge-strings-vector (ab) (let ((retstr (make-array (list (+ (length a) (length b))) :element-type 'character))) (labels ((merge-str (abi) (when (and (= (length a) (length b)) (/= i (length a))) (setf (aref retstr (* 2 i)) (aref ai)) (setf (aref retstr (1+ (* 2 i))) (aref bi)) (merge-str ab (1+ i))))) (merge-str ab 0) retstr))) 

Note that this - unlike the other 2 - has side effects inside the function. This is also, imo, harder to understand.

All 3 take a different number of cycles to execute on SBCL 56; It seems that in most of my trials each of them takes from 6 to 11 thousand. I'm not sure why.