Prev: Evaluating/compiling forms in the current lexical environment.
Next: When are clojures more advantageous than CLOS?
From: Tayssir John Gabbour on 2 Feb 2010 16:32
On Jan 29, 10:15 pm, Kaz Kylheku <kkylh...(a)gmail.com> wrote:
> I dislike all of the solutions hitherto given. :)
>
> The following is fantasy syntax, based on imaginary extensions to Fare Rideau's
> pattern notation:
>
> ;; munch the input-list as follows: sequences of strings are catenated
> ;; into a single string object which is collected. All other items are
> ;; collected as-is.
>
> (lex-collect input-list (tok)
> ((list (1+ (of-type string))) (apply #'concatenate 'string tok))
> ((list item) item))

Thanks Kaz for the brilliant idea. Combined with the pattern matching
lib* I saw today on Planet Clojure, here's this little beauty:

(defn concat-adj-strings [lst]
(lazy-seq
(match (split-with string? lst)
[[] []] nil
[[] b] (cons (first b) (concat-adj-strings (rest b)))
[a b] (cons (apply str a) (concat-adj-strings b)))))


Let the soul sing.
Tayssir


* http://github.com/brool/clojure-misc/tree
From: Richard Fateman on 2 Feb 2010 18:31
Kaz Kylheku wrote:
> On 2010-01-30, Ole Arndt <ole(a)sugarshark.com> wrote:
>> Richard Fateman <fateman(a)cs.berkeley.edu> writes:
>>
>>> (defun f(lis)
>>> (let ((h (first lis))(r (rest lis)))
>>> (cond ((and(stringp h)(stringp (first r)))
>>> (f (cons (concatenate 'string h (first r))
>>> (rest r))))
>>> (r (cons h (f r)))
>>> (t lis))))
>> Much nicer, but not tail recursive anymore ;)
>
> Don't forget that we can rewrite tail recursion into proper iteration
> with a macro, which preserves the tail recursive expression.
>
> Search the archives for the TAILPROG macro.

This is tail recursive:

(defun f(l)
(cond ((null l) nil)
((and(stringp (car l))(stringp (cadr l)))
(cons (concatenate 'string (car l) (cadr l))
(f (cddr l))))
((cadr l) (cons (car l)(f (cdr l))))
(t l)))

;; and (cadr l) should not be a problem as long as l is a proper list.
;; (cadr nil) is nil. I don't know what other peoples' solutions would
;; do with, say, ( "1" "2" 3 4 . 5)
From: Kaz Kylheku on 2 Feb 2010 19:56
On 2010-02-02, Richard Fateman <fateman(a)cs.berkeley.edu> wrote:
> Kaz Kylheku wrote:
>> On 2010-01-30, Ole Arndt <ole(a)sugarshark.com> wrote:
>>> Richard Fateman <fateman(a)cs.berkeley.edu> writes:
>>>
>>>> (defun f(lis)
>>>> (let ((h (first lis))(r (rest lis)))
>>>> (cond ((and(stringp h)(stringp (first r)))
>>>> (f (cons (concatenate 'string h (first r))
>>>> (rest r))))
>>>> (r (cons h (f r)))
>>>> (t lis))))
>>> Much nicer, but not tail recursive anymore ;)
>>
>> Don't forget that we can rewrite tail recursion into proper iteration
>> with a macro, which preserves the tail recursive expression.
>>
>> Search the archives for the TAILPROG macro.
>
> This is tail recursive:
>
> (defun f(l)
> (cond ((null l) nil)
> ((and(stringp (car l))(stringp (cadr l)))
> (cons (concatenate 'string (car l) (cadr l))
> (f (cddr l))))
> ((cadr l) (cons (car l)(f (cdr l))))
> (t l)))

These recursive calls are arguments in a call to CONS, and so they are relied
upon to return to that expression, so that it can complete evaluating its
arguments and invoke the CONS function.

Rule of thumb: if the algorithm would break if a recursive call did not return
normally, then it's not a tail call.
From: Thomas A. Russ on 2 Feb 2010 19:51
Richard Fateman <fateman(a)cs.berkeley.edu> writes:

> This is tail recursive:
>
> (defun f(l)
> (cond ((null l) nil)
> ((and(stringp (car l))(stringp (cadr l)))
> (cons (concatenate 'string (car l) (cadr l))
> (f (cddr l))))
> ((cadr l) (cons (car l)(f (cdr l))))
> (t l)))
>
> ;; and (cadr l) should not be a problem as long as l is a proper list.
> ;; (cadr nil) is nil. I don't know what other peoples' solutions would
> ;; do with, say, ( "1" "2" 3 4 . 5)

Unfortunately, it is also slightly incorrect, in that if fails if there
are three strings in a row. Try it on:

("1" "2" "WWW" 3 4)

But I think the fix is easy. The recursive call in the second COND
clause needs to be outside the concatenate, whose results need to be
combined with the remaining list to be processed again.

(defun f(l)
(cond ((null l) nil)
((and (stringp (car l))(stringp (cadr l)))
(f (cons (concatenate 'string (car l) (cadr l))
(cddr l))))
((cadr l) (cons (car l)(f (cdr l))))
(t l)))



--
Thomas A. Russ, USC/Information Sciences Institute
From: Tayssir John Gabbour on 2 Feb 2010 20:27
On Feb 3, 12:31 am, Richard Fateman <fate...(a)cs.berkeley.edu> wrote:
> (defun f(l)
> (cond ((null l) nil)
> ((and(stringp (car l))(stringp (cadr l)))
> (cons (concatenate 'string (car l) (cadr l))
> (f (cddr l))))
> ((cadr l) (cons (car l)(f (cdr l))))
> (t l)))
>
> ;; and (cadr l) should not be a problem as long as l is a proper list.
> ;; (cadr nil) is nil. I don't know what other peoples' solutions would
> ;; do with, say, ( "1" "2" 3 4 . 5)

I like the brevity of your solution (more succinct than some of my
attempts), but it unfortunately has a bug or two even with proper
lists. Under SBCL:
cl-user> (f '(1 nil "2" "3" "4" "5"))
(1 NIL "2" "3" "4" "5")

That input is by definition a proper list, as it's a list terminated
by the empty list.
<http://www.lispworks.com/documentation/HyperSpec/Body/
26_glo_p.htm#proper_list>

This input can occur in the real world. If you already have a mix of
strings and non-strings, then some of those non-strings could be
nulls. Maybe the original poster is writing a tokenizer, and nil
represents some kinda null object.


All the best,
Tayssir
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5 6 7
Prev: Evaluating/compiling forms in the current lexical environment.
Next: When are clojures more advantageous than CLOS?