Nested mapcar* application and possibly some variation of Y combinator

[Swami Tota Ram Shankar]

Dear elispWizards,

Consider the following command to halve every element in a vector or a
list

(mapcar* '(lambda(x) (* 0.5 x)) '[1 2 3 4 5 6 7] ) ---> (0.5 1.0
1.5 2.0 2.5 3.0 3.5)

Now, I intend to vary it so that it operated like this on a singly
nested list

(mapcar* '(lambda(x) (* 0.5 x)) '[[1 2 3] [4 5 6 7]] ) --->
((0.5 1.0 1.5) (2.0 2.5 3.0 3.5))

It would be nice if this can be accomplished without opening the
nested list or vector and nesting it again.

I could not put the mapcar* inside the lambda ... maybe made some
simple mistake. I dont have a strong enough intuition to say if this
is possible or not.

However, I am inspired by this approach for factorial which I picked
up from somewhere a while ago. Its said that it is a Y combinator
implmentation and it works, and I kinda understand it, but if someone
has a crisp and constructive methodical derivation from problem
statement, you're very welcome !

(
(lambda (f n) (funcall f f n) )
(lambda (f n) (if (zerop n) 1
(* n (funcall f f (1- n))))
)
5)

However, I picked up this line also and I cant understand it at all as
well as it has something missing, certainly a 5

( (lambda(f) ((lambda (Y) (f (Y Y))) (lambda (Y) (f (Y Y)))))
(lambda (ff n) (if (< n 1) 1 (* n (ff (- n 1))))) )

Hopefully, these may inspire you along the lines, I am having some
vague inspirational thoughts, however, the problem on the top is
rather well defined, to solve it as simply as possible, preferably
carrying the style of the first line.

Swami Tota Ram Shankar

[Pascal J. Bourguignon]

Swami Tota Ram Shankar <tota...@india.com> writes:

> Dear elispWizards,
>
> Consider the following command to halve every element in a vector or a
> list
>
> (mapcar* '(lambda(x) (* 0.5 x)) '[1 2 3 4 5 6 7] ) ---> (0.5 1.0
> 1.5 2.0 2.5 3.0 3.5)

If you quote the lambda list, you prevent the ccompiler to compile the
anonymous function. Why do you want to slow down you code like that?

Why do you call the function mapcar* ?
There's no car in '[1 2 3...7] to map over.
Only cons cells have car slots, and since lists are built of cons cells,
car can be applied to lists, to get the first element. But car cannot
be applied to vectors.

> Now, I intend to vary it so that it operated like this on a singly
> nested list
>
> (mapcar* '(lambda(x) (* 0.5 x)) '[[1 2 3] [4 5 6 7]] ) --->
> ((0.5 1.0 1.5) (2.0 2.5 3.0 3.5))

What about: [[1 2 3] 4 [5 [6 7]]] ?
What about: [[1 2 3] (4 5 [6 7] 8 9)] ?
What about: [[1 2 3] #s(hash-table size 65 test eql rehash-size 1.5
rehash-threshold 0.8 data (:a 10 :b 11))] ?

--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.

[Barry Fishman]

On 2011-08-21 04:19:20 EDT, Swami Tota Ram Shankar wrote:
> Dear elispWizards,

I'm far from an elisp wizard, but I can give you something that works.

> Consider the following command to halve every element in a vector or a
> list
>
> (mapcar* '(lambda(x) (* 0.5 x)) '[1 2 3 4 5 6 7] ) ---> (0.5 1.0
> 1.5 2.0 2.5 3.0 3.5)
>
> Now, I intend to vary it so that it operated like this on a singly
> nested list
>
> (mapcar* '(lambda(x) (* 0.5 x)) '[[1 2 3] [4 5 6 7]] ) --->
> ((0.5 1.0 1.5) (2.0 2.5 3.0 3.5))
>
> It would be nice if this can be accomplished without opening the
> nested list or vector and nesting it again.

I'm not sure what you mean. How else would you do it?

> I could not put the mapcar* inside the lambda ... maybe made some
> simple mistake. I dont have a strong enough intuition to say if this
> is possible or not.

If you want a function that traverses sequences recursively you might
do something like:

(defun map-r (fun seq)
(mapcar* #'(lambda (x)
(if (sequencep x)
(map-r fun x)
(funcall fun x)))
seq))

> However, I am inspired by this approach for factorial which I picked
> up from somewhere a while ago. Its said that it is a Y combinator
> implmentation and it works, and I kinda understand it, but if someone
> has a crisp and constructive methodical derivation from problem
> statement, you're very welcome !
>
> (
> (lambda (f n) (funcall f f n) )
> (lambda (f n) (if (zerop n) 1
> (* n (funcall f f (1- n))))
> )
> 5)

I assume you want a create a function for use in a mapcar* which knows
how to call itself when faced with a nested sequence, so you don't have
to regenerate a lambda function at each nest level (as I did). And do
this in a dynamically scoped lisp like e-lisp.

I will leave that for somebody posting from a emacs group.
--
Barry Fishman

[Swami Tota Ram Shankar]

Your problem description is close to what I want.
However, no one has replied yet with any thing useful.

[Swami Tota Ram Shankar]

On Aug 21, 1:30 am, "Pascal J. Bourguignon" <p...@informatimago.com>
wrote:

> Swami Tota Ram Shankar <tota_...@india.com> writes:
>
> > Dear elispWizards,
>
> > Consider the following command to halve every element in a vector or a
> > list
>
> > (mapcar* '(lambda(x) (* 0.5 x)) '[1 2 3 4 5 6 7] )     --->   (0.5 1.0
> > 1.5 2.0 2.5 3.0 3.5)
>
> If you quote the lambda list, you prevent the ccompiler to compile the
> anonymous function.  Why do you want to slow down you code like that?
>
> Why do you call the function mapcar* ?
> There's no car in '[1 2 3...7] to map over.
> Only cons cells have car slots, and since lists are built of cons cells,
> car can be applied to lists, to get the first element.  But car cannot
> be applied to vectors.
>
> > Now, I intend to vary it so that it operated like this on a singly
> > nested list
>
> > (mapcar* '(lambda(x) (* 0.5 x)) '[[1 2 3] [4 5 6 7]] )     --->
> > ((0.5 1.0 1.5) (2.0 2.5 3.0 3.5))
>
> What about: [[1 2 3] 4 [5 [6 7]]] ?
> What about: [[1 2 3] (4 5 [6 7] 8 9)] ?
> What about: [[1 2 3] #s(hash-table size 65 test eql rehash-size 1.5
>                         rehash-threshold 0.8 data (:a 10 :b 11))] ?

If you can do it easily, ie unpack and pack, then go ahead. Otherwise,
uniform tensors, ie lists of lists, or lists of lists of lists of i x
j x k ... type are also ok.

You could assume () instead of [] if you have a function for () that
you dont have for []. mapcar and mapcar* works uniformly for both as
you know.

Perhaps, you could take some hint from Gary Fishman and take it
towards a solution.

Not many people around in the newsgroups these days.

[Swami Tota Ram Shankar]

On Aug 21, 9:50 am, Barry Fishman <barry_fish...@acm.org> wrote:

This is probably a good description of the problem but for so many
days no one has given any reply.

[David Kastrup]

Swami Tota Ram Shankar <tota...@india.com> writes:

> Consider the following command to halve every element in a vector or a
> list
>
> (mapcar* '(lambda(x) (* 0.5 x)) '[1 2 3 4 5 6 7] ) ---> (0.5 1.0
> 1.5 2.0 2.5 3.0 3.5)
>
> Now, I intend to vary it so that it operated like this on a singly
> nested list
>
> (mapcar* '(lambda(x) (* 0.5 x)) '[[1 2 3] [4 5 6 7]] ) --->
> ((0.5 1.0 1.5) (2.0 2.5 3.0 3.5))

((lambda (f o s) (funcall f o s f))
(lambda (o s f)
(if (sequencep s)
(mapcar (lambda (s) (funcall f o s f)) s)
(funcall o s)))
(lambda (s) (* 0.5 s))
[[1 2 3] [4 5 6 7]])

--
David Kastrup

[Robert Klemme]

On 21.08.2011 10:19, Swami Tota Ram Shankar wrote:
> Dear elispWizards,
>
> Consider the following command to halve every element in a vector or a
> list
>
> (mapcar* '(lambda(x) (* 0.5 x)) '[1 2 3 4 5 6 7] ) ---> (0.5 1.0
> 1.5 2.0 2.5 3.0 3.5)
>
> Now, I intend to vary it so that it operated like this on a singly
> nested list
>
> (mapcar* '(lambda(x) (* 0.5 x)) '[[1 2 3] [4 5 6 7]] ) --->
> ((0.5 1.0 1.5) (2.0 2.5 3.0 3.5))
>
> It would be nice if this can be accomplished without opening the
> nested list or vector and nesting it again.

<disclaimer>I am a only starting to dig into Lisp / Scheme
myself.</disclaimer>

I am not sure what you mean. What's wrong with doing

(define (maptree* f l)
(if (null? l)
l
(let ((first (car l)))
(cons (if (list? first)
(maptree* f first)
(f first))
(maptree* f (cdr l))))))

Then you can do

guile> (define (times10 n) (* n 10))
guile> (maptree* times10 '(1 2 (3 (4 (5 6)) 7) 8))
(10 20 (30 (40 (50 60)) 70) 80)

or

guile> (maptree* (lambda (n) (* n 10)) '(1 2 (3 (4 (5 6)) 7) 8))
(10 20 (30 (40 (50 60)) 70) 80)

Note: I used a Scheme implementation for this.

If you want to use map/mapcar then it seems you have part of the
iteration logic in map/mapcar (for a list, that is) and part of the
iteration logic in whatever function you pass (decision to recurse on
nested lists). That seems like a bad way to distribute functionality
because there is no clean separation between modifying a single element
and traversing the nested structure. Or am I missing something?

> I could not put the mapcar* inside the lambda ... maybe made some
> simple mistake. I dont have a strong enough intuition to say if this
> is possible or not.

It seems if you want to use a function which does only straightforward
mapping on a list (like map or mapcar) then you would need a way to
reference the function itself which does the decision about tree traversal:

;; does not work
(define (treeadapter m f)
(let ((rf
(lambda (first)
(if (list? first)
(m rf first) ;; rf is undefined here!
(f first)))))
rf))

(map (treeadapter map times10) '(1 2 (3 (4 (5 6)) 7) 8))

As far as I understand you need anonymous recursive functions for this.
Further from what I understand you can use Y combinator do get that.
In this case this works:

;; does work
(define (treeadapter mm ff)
(Y (lambda (f)
(lambda (first)
(if (list? first)
(mm f first)
(ff first))))))

(map (treeadapter map times10) '(1 2 (3 (4 (5 6)) 7) 8))

What's not so nice about this is that you need to declare "map" twice.
If we want to avoid it we can do this:

(define (maptree mm ff)
(let ((x (treeadapter mm ff)))
(lambda (l) (mm x l))))

and voila

guile> ((maptree map times10) '(1 2 (3 (4 (5 6)) 7) 8))
(10 20 (30 (40 (50 60)) 70) 80)

Now my head is spinning and I need someone to explain to my why this
might be better than maptree* presented above. :-)

Kind regards

robert

--
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/

[Barry Fishman]

[David, Sorry for ignoring your change of followup. But I'm not sure
from what group the original poster is posting.]

Very neat, but does anyone really code that way? I get the impression
that at each sequencep level an new lambda is constructed for the
mapcar. This answers the OP's requirements, but I don't think it deals
with the additional requirement that that I proposed, that a new
function is not create at each recursion level.

If elisp had lexical closures, the following common lisp like code
would work:

--8<---------------cut here---------------start------------->8---
(defun rfunc (fun)
(let ((sfun nil))
(flet ((recur (f)

#'(lambda (x)
(if (sequencep x)

(mapcar sfun x)
(funcall f x)))))
(setq sfun (recur fun)))
sfun))

(mapcar (rfunc (lambda (x) (* 0.5 x))) [[1 2 3] [4 5 6]])
--8<---------------cut here---------------end--------------->8---

It doesn't.

But if you allow a lexical-let this could be adapted to:

--8<---------------cut here---------------start------------->8---
(defun rfunc (fun)
(lexical-let ((sfun nil)
(afun fun))
(flet ((recur ()

#'(lambda (x)
(if (sequencep x)

(mapcar sfun x)
(funcall afun x)))))
(setq sfun (recur)))
sfun))
--8<---------------cut here---------------end--------------->8---

This works. Then you could do:

(mapcar (rfunc (lambda (x) (* 0.5 x))) [[1 2 3] [4 5 6]])

Or even just:

(funcall (rfunc (lambda (x) (* 0.5 x))) '[[1 2 3] [4 5 6]])

--
Barry Fishman

[Barry Fishman]

On 2011-08-25 11:09:20 EDT, Barry Fishman wrote:
> (defun rfunc (fun)
> (lexical-let ((sfun nil)
> (afun fun))
> (flet ((recur ()
> #'(lambda (x)
> (if (sequencep x)
> (mapcar sfun x)
> (funcall afun x)))))
> (setq sfun (recur)))
> sfun))

Oops, once the recur argument have been eliminated, you no longer
need the function:

(defun rfunc (fun)
(lexical-let ((sfun nil)
(afun fun))

(setq sfun #'(lambda (x)

(if (sequencep x)
(mapcar sfun x)
(funcall afun x))))

sfun))

And maybe, since this function is only useful processing trees:

(defun maptree (fun tree)

(lexical-let ((sfun nil)
(afun fun))

(setq sfun #'(lambda (x)

(if (sequencep x)
(mapcar sfun x)
(funcall afun x))))

(funcall sfun tree)))

--
Barry Fishman

[Barry Fishman]

I thought I was done with this, but at 3 AM I woke up thinking,
"This no longer requires a closure", so it can be simplified to:

(defun maptree (func tree)
(let ((sfunc nil))
(setq sfunc (lambda (x)
(if (sequencep x)
(mapcar sfunc x)
(funcall func x))))
(funcall sfunc tree)))

--
Barry Fishman

[Swami Tota Ram Shankar]

On Aug 26, 12:07 am, Barry Fishman <barry_fish...@acm.org> wrote:
> On 2011-08-25 11:44:17 EDT, Barry Fishman wrote:
>
> > On 2011-08-25 11:09:20 EDT, Barry Fishman wrote:
> > And maybe, since this function is only useful processing trees:
>
> > (defun maptree (fun tree)
> >   (lexical-let ((sfun nil)
> >               (afun fun))
> >     (setq sfun #'(lambda (x)
> >                  (if (sequencep x)
> >                      (mapcar sfun x)
> >                    (funcall afun x))))
> >     (funcall sfun tree)))
>
> I thought I was done with this, but at 3 AM I woke up thinking,
> "This no longer requires a closure",  so it can be simplified to:
>

This means that you dont have a strong enough intuition about the
lexical closures. I studied it a year ago in connection with
javascript. Javascript has scope chaining. In C you can create a local
scope using {}, but this is not the case in javascript. All the
variables from the outside are visible inside unless over-ridden by a
local redefinition. This is called scope chaining. In JS, lexical
scoping means, that functions create their environment (scope) ie
symbol-value pairs in the table when they are defined and not when
they are executed. I guess, I need someone to discuss with slightly
different elementary series of examples to make it clear and crisp. It
shall help the author also.

[David Kastrup]

Barry Fishman <barry_...@acm.org> writes:

The lambda function uses the outer function parameter func as well as
the outer let-binding sfunc (which, from the view of the anonymous
lambda, has no inherent connection to itself). So to make this version
unclosured, you can't really use mapcar in the recursion since the
recursion needs to have more information than available from the
list/tree.

Followup to comp.lang.lisp since this is not specific to Emacs or Scheme.

--
David Kastrup

[Swami Tota Ram Shankar]

On Aug 26, 12:24 am, Swami Tota Ram Shankar <tota_...@india.com>
wrote:

useful link on lexical closures

http://c2.com/cgi/wiki?LexicalClosure

[Swami Tota Ram Shankar]

On Aug 26, 12:24 am, Swami Tota Ram Shankar <tota_...@india.com>
wrote:

useful link on lexical closures

http://c2.com/cgi/wiki?LexicalClosure

>

[Swami Tota Ram Shankar]

On Aug 26, 12:24 am, Swami Tota Ram Shankar <tota_...@india.com>
wrote:

useful link on lexical closures

http://c2.com/cgi/wiki?LexicalClosure

>

[tota...@india.com]

Hi David, if you are still around on this newsgroup, can you explain how you derived this from the Y combinator's definition?

Swami

Hi David, if you are still around, can you explain how you derived the above from the first definition of the Y-combinator?

Regards
Swami Tota Ram Shankar