I have tried to construct a function that flattens a list and then adds the
contents eg
(flatten '(1 ((5 6) 3) (2))) produces (17). The problem is that I cannot get
it to add the list once it has been flattened. I have tested the flatten
function without adding the list members and it works fine, but I cannot get
it to add.
Any suggestions
(defun flatten (s)
(cond ((null s) 0)
((atom s) (list s))
(t (append (flatten (car s)) (flatten (cdr s)) <= ok upto here
(apply '+ '(flatten s)))))) <= how do you add once
flattened
(flatten '(1 ((5 6 ) 3) (2)))
David Nixon wrote:
>
> I have tried to construct a function that flattens a list and then adds the
> contents eg
> (flatten '(1 ((5 6) 3) (2))) produces (17). The problem is that I cannot get
> it to add the list once it has been flattened. I have tested the flatten
> function without adding the list members and it works fine, but I cannot get
> it to add.
> Any suggestions
> (defun flatten (s)
> (cond ((null s) 0)
> ((atom s) (list s))
> (t (append (flatten (car s)) (flatten (cdr s)) <= ok upto here
> (apply '+ '(flatten s)))))) <= how do you add once
> flattened
>
> (flatten '(1 ((5 6 ) 3) (2)))
I'd suggest you separate the summing and the flattening parts: write a
function flatten, which only flattens lists, and another function, which
you use to sum the results. Pretty simple:
(defun flatten-and-sum (tree)
(reduce #'+ (flatten tree)))
- Probably not worth writing as a separate function in a large piece of
code, the contents are reasonably readable as such. Of course you could
do this also using flet, but the flatten -function might be useful
elsewhere, too.
Mostly, it is useful to write Lisp functions so that they do only one
thing, and combine them as convenient.
--
________________________________________________________________
^. Martti Halminen
/ \`. Design Power Europe Oy
/ \ `. Tekniikantie 12, FIN-02150 Espoo, Finland
/\`. \ | Tel:+358 9 4354 2306, Fax:+358 9 455 8575
/__\|___\| ······················@dpe.fi http://www.dpe.fi
From: David McClain
Subject: Re: Flatten function problem
Date:
Message-ID: <77d78d$s5$1@remarQ.com>
One of the problems I have encountered in situations such as this is that
there is frequently a limit to the number of arguments permitted to any
function call. I had a situation like this just recently in Harlequin
Lispworks 4.01. Whenever the list of items exceeded 255 it silently
discarded the first 256 items and operated on the tail.
David McClain
Sr. Scientist
Raytheon Missile Systems Co.
Tucson, AZ
http://www.azstarnet.com/~dmcclain/homepage.htm
David Nixon wrote in message <············@news6.svr.pol.co.uk>...
>I have tried to construct a function that flattens a list and then adds the
>contents eg
>(flatten '(1 ((5 6) 3) (2))) produces (17). The problem is that I cannot
get
>it to add the list once it has been flattened. I have tested the flatten
>function without adding the list members and it works fine, but I cannot
get
>it to add.
>Any suggestions
>(defun flatten (s)
> (cond ((null s) 0)
> ((atom s) (list s))
> (t (append (flatten (car s)) (flatten (cdr s)) <= ok upto here
> (apply '+ '(flatten s)))))) <= how do you add once
>flattened
>
> (flatten '(1 ((5 6 ) 3) (2)))
>
>
>
>
In article <···········@remarQ.com>,
David McClain <········@azstarnet.com> wrote:
>One of the problems I have encountered in situations such as this is that
>there is frequently a limit to the number of arguments permitted to any
>function call. I had a situation like this just recently in Harlequin
See the contant CALL-ARGUMENTS-LIMIT, which an implementation must set to
this limit.
>Lispworks 4.01. Whenever the list of items exceeded 255 it silently
>discarded the first 256 items and operated on the tail.
That's why you should generally use (reduce #'+ list) rather than (apply
#'+ list).
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Don't bother cc'ing followups to me.
From: David McClain
Subject: Re: Flatten function problem
Date:
Message-ID: <77iocd$h8a$1@remarQ.com>
Actually, the problem manifests itself in the construction of the list
argument. I found that the Lisp reader discards the first batch of elements
if the count exceeds 255.
But thanks for the info on CALL-ARGUMENTS-LIMIT. I was unaware of this
variable.
- DM
Barry Margolin wrote in message ...
>In article <···········@remarQ.com>,
>David McClain <········@azstarnet.com> wrote:
>>One of the problems I have encountered in situations such as this is that
>>there is frequently a limit to the number of arguments permitted to any
>>function call. I had a situation like this just recently in Harlequin
>
>See the contant CALL-ARGUMENTS-LIMIT, which an implementation must set to
>this limit.
>
>>Lispworks 4.01. Whenever the list of items exceeded 255 it silently
>>discarded the first 256 items and operated on the tail.
>
>That's why you should generally use (reduce #'+ list) rather than (apply
>#'+ list).
>
>--
>Barry Margolin, ······@bbnplanet.com
>GTE Internetworking, Powered by BBN, Burlington, MA
>*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
>Don't bother cc'ing followups to me.
"David Nixon" <·····@nixon25.freeserve.co.uk> writes:
< I have tried to construct a function that flattens a list and then adds the
< contents eg
< (flatten '(1 ((5 6) 3) (2))) produces (17). The problem is that I cannot get
< it to add the list once it has been flattened. I have tested the flatten
< function without adding the list members and it works fine, but I cannot get
< it to add.
< Any suggestions
< (defun flatten (s)
< (cond ((null s) 0)
< ((atom s) (list s))
< (t (append (flatten (car s)) (flatten (cdr s)) <= ok upto here
< (apply '+ '(flatten s)))))) <= how do you add once
< flattened
<
< (flatten '(1 ((5 6 ) 3) (2)))
Rather than construct a new list then add the numbers you could just
add the numbers as you recurse through the list. You just have to
return 0 when you hit a nil (the end of the list usually). I think you
got the harder part right (returning a zero), you just have to move
the `+' function.
(defun add-numbers (list)
(cond ((null list) 0)
((atom list) list)
(t (+ (add-numbers (first list))
(add-numbers (rest list))))))
(add-numbers '(1 ((5 6 ) 3) (2))) => 17
You can trace the function to see what's happening.
USER(9): (trace add-numbers)
(ADD-NUMBERS)
USER(10): (add-numbers '(1 ((5 6 ) 3) (2)))
0: (ADD-NUMBERS (1 ((5 6) 3) (2)))
1: (ADD-NUMBERS 1)
1: returned 1
1: (ADD-NUMBERS (((5 6) 3) (2)))
2: (ADD-NUMBERS ((5 6) 3))
3: (ADD-NUMBERS (5 6))
4: (ADD-NUMBERS 5)
4: returned 5
4: (ADD-NUMBERS (6))
5: (ADD-NUMBERS 6)
5: returned 6
5: (ADD-NUMBERS NIL)
5: returned 0
4: returned 6
3: returned 11
3: (ADD-NUMBERS (3))
4: (ADD-NUMBERS 3)
4: returned 3
4: (ADD-NUMBERS NIL)
4: returned 0
3: returned 3
2: returned 14
2: (ADD-NUMBERS ((2)))
3: (ADD-NUMBERS (2))
4: (ADD-NUMBERS 2)
4: returned 2
4: (ADD-NUMBERS NIL)
4: returned 0
3: returned 2
3: (ADD-NUMBERS NIL)
3: returned 0
2: returned 2
1: returned 16
0: returned 17
17
This is not `tail-recursive', but it shouldn't be too hard to write it
in a tail-recursive manor.
Also tracing the `+' function may be helpful as well.
USER(14): (untrace add-numbers)
(ADD-NUMBERS)
USER(15): (trace +)
(+)
USER(16): (add-numbers '(1 ((5 6 ) 3) (2)))
0: (+ 6 0)
0: returned 6
0: (+ 5 6)
0: returned 11
0: (+ 3 0)
0: returned 3
0: (+ 11 3)
0: returned 14
0: (+ 2 0)
0: returned 2
0: (+ 2 0)
0: returned 2
0: (+ 14 2)
0: returned 16
0: (+ 1 16)
0: returned 17
17
Hope this helps some...
David Nixon wrote in message <············@news6.svr.pol.co.uk>...
>I have tried to construct a function that flattens a list and then adds the
>contents eg
>(flatten '(1 ((5 6) 3) (2))) produces (17). The problem is that I cannot
get
>it to add the list once it has been flattened. I have tested the flatten
>function without adding the list members and it works fine, but I cannot
get
>it to add.
>Any suggestions
>(defun flatten (s)
> (cond ((null s) 0)
> ((atom s) (list s))
> (t (append (flatten (car s)) (flatten (cdr s)) <= ok upto here
> (apply '+ '(flatten s)))))) <= how do you add once
>flattened
>
> (flatten '(1 ((5 6 ) 3) (2)))
>
You may have a problem with the representation of atoms in your flattened
list. In my version of lisp (MuLisp90), the function you describe would
probably
result in a list of charater atoms rather than numeric atoms. Test this by
taking
your resulting list and performing a NUMBERP predicate on any element of
the list. If you get 'NIL, you will need to write a function that converts
characters
to their numeric equivalent.
In article <············@news.hal-pc.org>,
charliew <········@hal-pc.org> wrote:
>You may have a problem with the representation of atoms in your flattened
>list. In my version of lisp (MuLisp90), the function you describe would
>probably
>result in a list of charater atoms rather than numeric atoms.
Why would flattening a tree containing numbers at its leaves result in a
list of characters? Shouldn't the elements of the flattened list be the
same as the leaves of the original tree? Or are you saying that in
MuLisp90, '((1 2) 3 (4 5)) creates a tree with characters at its leaves
instead of numbers? Seems like a pretty strange thing to do, but maybe the
MuLisp designers had a good reason for it.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Don't bother cc'ing followups to me.
Barry Margolin wrote in message ...
>In article <············@news.hal-pc.org>,
>charliew <········@hal-pc.org> wrote:
>>You may have a problem with the representation of atoms in your flattened
>>list. In my version of lisp (MuLisp90), the function you describe would
>>probably
>>result in a list of charater atoms rather than numeric atoms.
>
>Why would flattening a tree containing numbers at its leaves result in a
>list of characters? Shouldn't the elements of the flattened list be the
>same as the leaves of the original tree? Or are you saying that in
>MuLisp90, '((1 2) 3 (4 5)) creates a tree with characters at its leaves
>instead of numbers? Seems like a pretty strange thing to do, but maybe the
>MuLisp designers had a good reason for it.
>
As I recall, I have encountered this effect when using functions like
UNPACK, which separate characters, and convert numeric components of a
number into their character equivalents. When I have encountered numbers,
and used numeric functions on them, I haven't seen the referenced effect.
However, I suggested this as a possibility that should be checked out and
eliminated, just to be on the safe side.
* "charliew" <········@hal-pc.org>
| As I recall, I have encountered this effect when using functions like
| UNPACK, which separate characters, and convert numeric components of a
| number into their character equivalents. When I have encountered
| numbers, and used numeric functions on them, I haven't seen the
| referenced effect. However, I suggested this as a possibility that
| should be checked out and eliminated, just to be on the safe side.
looks like the implementation uses small integers to mean both small
integers and the character-code of characters. Emacs Lisp does this.
C also does this. it's a very bad idea.
#:Erik
In article <················@naggum.no>, Erik Naggum <····@naggum.no> wrote:
>* "charliew" <········@hal-pc.org>
>| As I recall, I have encountered this effect when using functions like
>| UNPACK, which separate characters, and convert numeric components of a
>| number into their character equivalents. When I have encountered
>| numbers, and used numeric functions on them, I haven't seen the
>| referenced effect. However, I suggested this as a possibility that
>| should be checked out and eliminated, just to be on the safe side.
>
> looks like the implementation uses small integers to mean both small
> integers and the character-code of characters. Emacs Lisp does this.
> C also does this. it's a very bad idea.
But in those languages, the integers don't lose their integral identity,
the way charliew was suggesting they do in MuLisp. Whether a small integer
is treated as a number or a character depends on how it's used: if you use
it as a parameter to +, it's a number; if you call putc(), it's a
character. Actually, these languages don't have character types at all
(C's "char" data type would be more properly named "smallint" or "byte"),
they simply use integers to represent characters.
MACLISP didn't have a character type, either. It used symbols with
single-character names to represent them, and strings were represented as
hunks with a special tag in the CAR (a hunk was a cross between a cons and
an array -- they came only in power-of-two sizes, the slots were indexed
numerically like arrays using CXR, with CAR and CDR being equivalent to
slots 0 and 1 -- I suspect they were created because MACLISP's array
interface was kind of baroque (or broke), or perhaps for some efficiency
reasons).
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Don't bother cc'ing followups to me.
In article <············@news6.svr.pol.co.uk>,
"David Nixon" <·····@nixon25.freeserve.co.uk> wrote:
(...)
> (apply '+ '(flatten s))))))
^^^
Apart from everything else that has already been mentioned,
there shouldn't be a single quote here:
(reduce #'+ (flatten s))
Vassil Nikolov <········@poboxes.com> www.poboxes.com/vnikolov
(You may want to cc your posting to me if I _have_ to see it.)
LEGEMANVALEMFVTVTVM (Ancient Roman programmers' adage.)
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own