The old Google Groups will be going away soon, but your browser is incompatible with the new version.
This is a Usenet group - learn more
Nested mapcar* application and possibly some variation of Y combinator
 There are currently too many topics in this group that display first. To make this topic appear first, remove this option from another topic. There was an error processing your request. Please try again. Standard view   View as tree
 17 messages
The group you are posting to is a Usenet group. Messages posted to this group will make your email address visible to anyone on the Internet.
Your reply message has not been sent.
Your post was successful

From:
To:
Cc:
Followup To:
 Add Cc | Add Followup-to | Edit Subject
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Aug 21 2011, 4:19 am
Newsgroups: gnu.emacs.help, comp.lang.lisp, comp.emacs, gnu.emacs, comp.lang.scheme
From: Swami Tota Ram Shankar <tota_...@india.com>
Date: Sun, 21 Aug 2011 01:19:20 -0700 (PDT)
Local: Sun, Aug 21 2011 4:19 am
Subject: Nested mapcar* application and possibly some variation of Y combinator
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

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Aug 21 2011, 4:30 am
Newsgroups: gnu.emacs.help, comp.lang.lisp, comp.emacs, gnu.emacs, comp.lang.scheme
From: "Pascal J. Bourguignon" <p...@informatimago.com>
Date: Sun, 21 Aug 2011 10:30:51 +0200
Local: Sun, Aug 21 2011 4:30 am
Subject: Re: Nested mapcar* application and possibly some variation of Y combinator
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 {}.

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Aug 21 2011, 12:50 pm
Newsgroups: gnu.emacs.help, comp.lang.lisp, comp.emacs, gnu.emacs, comp.lang.scheme
From: Barry Fishman <barry_fish...@acm.org>
Date: Sun, 21 Aug 2011 12:50:11 -0400
Local: Sun, Aug 21 2011 12:50 pm
Subject: Re: Nested mapcar* application and possibly some variation of Y combinator
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

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Aug 24 2011, 10:56 pm
Newsgroups: gnu.emacs.help, comp.lang.lisp, comp.emacs, gnu.emacs, comp.lang.scheme
From: Swami Tota Ram Shankar <tota_...@india.com>
Date: Wed, 24 Aug 2011 19:56:14 -0700 (PDT)
Local: Wed, Aug 24 2011 10:56 pm
Subject: Re: Nested mapcar* application and possibly some variation of Y combinator
On Aug 21, 9:50 am, Barry Fishman <barry_fish...@acm.org> wrote:

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

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Aug 24 2011, 10:52 pm
Newsgroups: gnu.emacs.help, comp.lang.lisp, comp.emacs, gnu.emacs, comp.lang.scheme
From: Swami Tota Ram Shankar <tota_...@india.com>
Date: Wed, 24 Aug 2011 19:52:05 -0700 (PDT)
Local: Wed, Aug 24 2011 10:52 pm
Subject: Re: Nested mapcar* application and possibly some variation of Y combinator
On Aug 21, 1:30 am, "Pascal J. Bourguignon" <p...@informatimago.com>
wrote:

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.

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Aug 24 2011, 10:48 pm
Newsgroups: gnu.emacs.help, comp.lang.lisp, comp.emacs, gnu.emacs, comp.lang.scheme
From: Swami Tota Ram Shankar <tota_...@india.com>
Date: Wed, 24 Aug 2011 19:48:52 -0700 (PDT)
Local: Wed, Aug 24 2011 10:48 pm
Subject: Re: Nested mapcar* application and possibly some variation of Y combinator
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.

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Aug 25 2011, 1:45 am
Newsgroups: gnu.emacs.help, comp.lang.lisp, comp.emacs, gnu.emacs, comp.lang.scheme
Followup-To: gnu.emacs.help
From: David Kastrup <d...@gnu.org>
Date: Thu, 25 Aug 2011 07:45:36 +0200
Local: Thurs, Aug 25 2011 1:45 am
Subject: Re: Nested mapcar* application and possibly some variation of Y combinator
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

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Aug 25 2011, 6:51 am
Newsgroups: gnu.emacs.help, comp.lang.lisp, comp.emacs, gnu.emacs, comp.lang.scheme
From: Robert Klemme <shortcut...@googlemail.com>
Date: Thu, 25 Aug 2011 12:51:43 +0200
Local: Thurs, Aug 25 2011 6:51 am
Subject: Re: Nested mapcar* application and possibly some variation of Y combinator
On 21.08.2011 10:19, Swami Tota Ram Shankar wrote:

<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/

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Aug 25 2011, 11:09 am
Newsgroups: gnu.emacs.help, comp.lang.lisp, comp.emacs, gnu.emacs, comp.lang.scheme
From: Barry Fishman <barry_fish...@acm.org>
Date: Thu, 25 Aug 2011 11:09:20 -0400
Local: Thurs, Aug 25 2011 11:09 am
Subject: Re: Nested mapcar* application and possibly some variation of Y combinator
[David, Sorry for ignoring your change of followup.  But I'm not sure
from what group the original poster is posting.]

On 2011-08-25 01:45:36 EDT, David Kastrup wrote:

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

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Aug 25 2011, 11:44 am
Newsgroups: gnu.emacs.help, comp.lang.lisp, comp.emacs, gnu.emacs, comp.lang.scheme
From: Barry Fishman <barry_fish...@acm.org>
Date: Thu, 25 Aug 2011 11:44:17 -0400
Local: Thurs, Aug 25 2011 11:44 am
Subject: Re: Nested mapcar* application and possibly some variation of Y combinator

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

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Aug 26 2011, 3:07 am
Newsgroups: gnu.emacs.help, comp.lang.lisp, comp.emacs, gnu.emacs, comp.lang.scheme
From: Barry Fishman <barry_fish...@acm.org>
Date: Fri, 26 Aug 2011 03:07:33 -0400
Local: Fri, Aug 26 2011 3:07 am
Subject: Re: Nested mapcar* application and possibly some variation of Y combinator
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:

(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

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Aug 26 2011, 3:24 am
Newsgroups: gnu.emacs.help, comp.lang.lisp, comp.emacs, gnu.emacs, comp.lang.scheme
From: Swami Tota Ram Shankar <tota_...@india.com>
Date: Fri, 26 Aug 2011 00:24:19 -0700 (PDT)
Local: Fri, Aug 26 2011 3:24 am
Subject: Re: Nested mapcar* application and possibly some variation of Y combinator
On Aug 26, 12:07 am, Barry Fishman <barry_fish...@acm.org> wrote:

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.

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Aug 26 2011, 3:52 am
Newsgroups: gnu.emacs.help, comp.lang.lisp, comp.emacs, gnu.emacs, comp.lang.scheme
Followup-To: comp.lang.lisp
From: David Kastrup <d...@gnu.org>
Date: Fri, 26 Aug 2011 09:52:46 +0200
Local: Fri, Aug 26 2011 3:52 am
Subject: Re: Nested mapcar* application and possibly some variation of Y combinator

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

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Aug 26 2011, 4:18 am
Newsgroups: gnu.emacs.help, comp.lang.lisp, comp.emacs, gnu.emacs, comp.lang.scheme
From: Swami Tota Ram Shankar <tota_...@india.com>
Date: Fri, 26 Aug 2011 01:18:07 -0700 (PDT)
Local: Fri, Aug 26 2011 4:18 am
Subject: Re: Nested mapcar* application and possibly some variation of Y combinator
On Aug 26, 12:24 am, Swami Tota Ram Shankar <tota_...@india.com>
wrote:

useful link on lexical closures

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Aug 26 2011, 4:18 am
Newsgroups: gnu.emacs.help, comp.lang.lisp, comp.emacs, gnu.emacs, comp.lang.scheme
From: Swami Tota Ram Shankar <tota_...@india.com>
Date: Fri, 26 Aug 2011 01:18:47 -0700 (PDT)
Local: Fri, Aug 26 2011 4:18 am
Subject: Re: Nested mapcar* application and possibly some variation of Y combinator
On Aug 26, 12:24 am, Swami Tota Ram Shankar <tota_...@india.com>
wrote:

useful link on lexical closures

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Aug 26 2011, 5:15 am
Newsgroups: gnu.emacs.help, comp.lang.lisp, comp.emacs, gnu.emacs, comp.lang.scheme
From: Swami Tota Ram Shankar <tota_...@india.com>
Date: Fri, 26 Aug 2011 02:15:17 -0700 (PDT)
Local: Fri, Aug 26 2011 5:15 am
Subject: Re: Nested mapcar* application and possibly some variation of Y combinator
On Aug 26, 12:24 am, Swami Tota Ram Shankar <tota_...@india.com>
wrote:

useful link on lexical closures

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
More options Oct 21 2012, 2:24 am
Newsgroups: comp.lang.scheme
From: tota_...@india.com
Date: Sat, 20 Oct 2012 23:24:16 -0700 (PDT)
Local: Sun, Oct 21 2012 2:24 am
Subject: Re: Nested mapcar* application and possibly some variation of Y combinator

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

You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
 End of messages
 « Back to Discussions « Newer topic Older topic »