Does "map" necessarily produce an additional level of nesting?

Question

Does using nested maps automatically create another level of nesting? Here is a basic example that I used:

; One level
(map (lambda (x1)
   "Hi")
 '(1))

; Two levels
(map (lambda (x1)
   (map (lambda (x2)
          "Hi")
        '(1)))
     '(1))

; Three levels
(map (lambda (x1)
   (map (lambda (x2)
      (map (lambda (x3)
          "Hi")
           '(1)))
        '(1)))
     '(1))

; Four levels
(map (lambda (x1)
   (map (lambda (x2)
      (map (lambda (x3)
         (map (lambda (x4)
          "Hi")
           '(1)))
        '(1)))
     '(1)))
   '(1))

("Hi")
(("Hi"))
((("Hi")))
(((("Hi"))))

Or, are there any counterexamples where adding another map will not produce additional nesting? I'm having trouble 'getting' how map adds another level. For example, for the first level:

(map (lambda (x1)
   "Hi")
 '(1))

I understand that there is one element in the list, and 'for each element' in the list -- we will return the element "Hi"at that position in the list, so for the first level we get ("Hi").

But then how, for example, from the list ("Hi") do we get a nested list at the second level? I know I've asked a lot of questions related to map and nesting, but hopefully if I can just understand the going from 1 level to 2 I can figure out the rest...

`map` returns a list of the results. If you nest them, you get a nested list. — Barmar, Jun 23 '21 at 22:43

score 3 · Answer 1 · answered Jun 23 '21 at 22:50

map collects the return values of all the function calls, and wraps them in another list.

If the function returns a list, you'll get a list of lists.

So if you have nested maps, you always get nested lists as the final result. And each level of mapping adds another level of nesting.

Note that this is only true if you're actually returning the value of map at each level. You could do other things with it, e.g.

;; Two levels
(map (lambda (x1)
       (length (map (lambda (x2)
                      "Hi")
                    '(1))))
     '(1))

This will return (1)

score 2 · Answer 2 · answered Jun 23 '21 at 22:54

The map will return a list for each element in that list. Let us go through a multi-map example where we can show how nesting comes into play.

First, let's do a single map on a sequence of numbers and "do nothing" to them. That is, just return the element from the input:

(map (lambda (x) x)
     '(1 2 3))
; (1 2 3)

At this point, it may be easy to think that another level of nesting should not occur if we add on another map since here we have not 'nested' the input list. It has simply 'stayed' at (1 2 3).

But if we add an outer level, we can see how this may occur:

(map (lambda (ignore-me)
       (map (lambda (x) x)
            '(1 2 3)))
     '(1))
; (( 1 2 3 ))

With just one 'outer-element' it's hard to see this, but instead, let's add 5 outer elements and make it much easier to spot:

(map (lambda (ignore-me)
       (map (lambda (x) x)
            '(1 2 3)))
     '(5 5 5 5 5))
;(
;  (1 2 3) 
;  (1 2 3) 
;  (1 2 3) 
;  (1 2 3) 
;  (1 2 3)
;)

Here we can see for each outer element -- and there are five of them -- we are returning the "inner-result" -- which is (1 2 3) in the above case. If we did the same thing again, this time producing two additional outer loops, we can see a similar result occurring:

(map (lambda (ignore-me1)
(map (lambda (ignore-me2)
       (map (lambda (x) x)
            '(1 2 3)))
     '(5 5 5 5 5)))
     '(2 2))
; (
;   ((1 2 3) (1 2 3) (1 2 3) (1 2 3) (1 2 3)) 
;   ((1 2 3) (1 2 3) (1 2 3) (1 2 3) (1 2 3))
; )

Mulan · Accepted Answer · 2021-06-26T19:52:59.697

one-to-one

Your examples include (map (lambda (x) x) ...)

(map (lambda (ignore-me)
       (map (lambda (x) x) ; <- no-op
            '(1 2 3)))
     '(1))

((1 2 3))

It's "hard to see" because the inner map is essentially a no-op. map creates a 1:1 relationship between the input and the output, with no opinions about what the mapping procedure does. If the mapping procedure returns a single element, a list, or a very nested list, it doesn't matter -

(map (lambda (ignore-me)
       '(1 2 3))
     '(foo))

((1 2 3))

(map (lambda (_)
       '(((((really nested))))))
     '(1 2 3))

((((((really nested)))))
 (((((really nested)))))
 (((((really nested))))))

Or with some ascii visualization -

(define (fn x) (+ x x))

(map fn '(1 2 3))
;          \ \ \
;           \ \ (fn 3)
;            \ \      \
;             \ (fn 2) \
;              \      \ \
;               (fn 1) \ \
;                     \ \ \
;  output:           '(2 4 6)

Should you choose to map inside of the mapping procedure to another map call -

(map (lambda (...)
       (map ...)) ; <- nested map
     ...)

The same rules apply. Each map output has a 1:1 relationship with its input list. We can imagine map's type for more insight -

map : ('a -> 'b, 'a list) -> 'b list
       --------  -------     -------
         \        \           \_ returns a list of type 'b
          \        \
           \        \__ input list of type 'a
            \
             \__ mapping procedure, maps
                 one element of type 'a
                 to one element of type 'b

implementing map

As a learning exercise, it's useful to implement map to gain an intimate understanding of how it works -

(define (map fn lst)
  (if (null? lst)
      '()
      (cons (fn (car lst))
            (map fn (cdr lst)))))

(map (lambda (x)
       (list x x x x x))
     '(1 2 3))

((1 1 1 1 1)
 (2 2 2 2 2)
 (3 3 3 3 3))

As you can see, map does not have an opinion on the type of elements in lst or what the return value of fn is. map plainly passes the car of the list to fn and cons'es it onto the recursive result of the cdr of the list.

append-map

Another relevant procedure we should look at is append-map -

append-map : ('a -> 'b list, 'a list) -> 'b list
              -------------  -------     -------
                \             \           \_ returns a list of type 'b
                 \             \_ input list of type 'a
                  \
                   \_ mapping function, maps
                      one element of type 'a
                      to a LIST of elements of type 'b

The only difference here is the mapping procedure is expected to return a list of elements, not just a single element. In this way, append-map creates a 1:many relationship between in the input list and the output list.

(append-map (lambda (x)
              (list x x x x x))
            '(1 2 3))

(1 1 1 1 1 2 2 2 2 2 3 3 3 3 3)

This characteristic of append-map is why it is sometimes called flatmap, as it "flattens" a level of nesting -

(append-map (lambda (x)
              (map (lambda (y)
                     (list x y))
                   '(spade heart club diamond)))
            '(J Q K A))

((J spade)
 (J heart)
 (J club)
 (J diamond)
 (Q spade)
 (Q heart)
 (Q club)
 (Q diamond)
 (K spade)
 (K heart)
 (K club)
 (K diamond)
 (A spade)
 (A heart)
 (A club)
 (A diamond))

Follow-up exercises for the reader:

What would the output be if we traded append-map for map in the example above?
Define map in another way or two. Verify the correct behaviour
Define append-map in terms of map. Define it again without using map.

loose typing

Scheme is an untyped language and thus a list's contents are not required to be homogenous. Still, it's useful to think about map and append-map in this way as the type helps communicate how the function will behave. Here are more accurate type definitions provided by Racket -

(map proc lst ...+) → list?
  proc : procedure?
  lst : list?

(append-map proc lst ...+) → list?
  proc : procedure?
  lst : list?

These are much looser and do reflect the loose programs you can actually write. For example -

(append-map (lambda (x)
              (list 'a-symbol "hello" 'float (* x 1.5) 'bool (> x 1)))
            '(1 2 3))

(a-symbol "hello" float 1.5 bool #f a-symbol "hello" float 3.0 bool #t a-symbol "hello" float 4.5 bool #t)

variadic map and append-map

Do you see those ...+ in the types above? For the sake of simplicity, I've been hiding an important detail up until this point. The variadic interface of map means that it can accept 1 or more input lists -

(map (lambda (x y z)
       (list x y z))
     '(1 2 3)
     '(4 5 6)
     '(7 8 9))

((1 4 7) (2 5 8) (3 6 9))

(append-map (lambda (x y z)
              (list x y z))
            '(1 2 3)
            '(4 5 6)
            '(7 8 9))

(1 4 7 2 5 8 3 6 9)

Follow-up exercises for the reader:

Define variadic map
Define variadic append-map

a touch of lambda calculus

You are aware of lambda calculus. Did you know (lambda (x y z) (list x y z) is the same as list? This is known as Eta reduction -

(map list '(1 2 3) '(4 5 6) '(7 8 9))

((1 4 7) (2 5 8) (3 6 9))

(append-map list '(1 2 3) '(4 5 6) '(7 8 9))

(1 4 7 2 5 8 3 6 9)

delimited continuations

Remember when we talked about delimited continuations and operators shift and reset? After learning about append-map, let's see amb, the ambiguous choice operator -

(define (amb . lst)
  (shift k (append-map k lst)))

We can use amb like this -

(reset (list (amb 'J 'Q 'K 'A) (amb '♡ '♢ '♤ '♧)))

(J ♡ J ♢ J ♤ J ♧ Q ♡ Q ♢ Q ♤ Q ♧ K ♡ K ♢ K ♤ K ♧ A ♡ A ♢ A ♤ A ♧)

(reset (list (list (amb 'J 'Q 'K 'A) (amb '♡ '♢ '♤ '♧))))

((J ♡) (J ♢) (J ♤) (J ♧) (Q ♡) (Q ♢) (Q ♤) (Q ♧) (K ♡) (K ♢) (K ♤) (K ♧) (A ♡) (A ♢) (A ♤) (A ♧))

In a more useful example, we use the pythagorean theorem to find-right-triangles -

(define (pythag a b c)
  (= (+ (* a a) (* b b)) (* c c))) ; a² + b² = c²

(define (find-right-triangles . side-lengths)
  (filter ((curry apply) pythag)
          (reset (list
                   (list (apply amb side-lengths)
                         (apply amb side-lengths)
                         (apply amb side-lengths))))))

(find-right-triangles 1 2 3 4 5 6 7 8 9 10 11 12)

((3 4 5) (4 3 5) (6 8 10) (8 6 10))

Delimited continuations effectively turn your program inside-out, allowing you to focus on declarative structure -

(define (bit)
  (amb #\0 #\1))

(define (4-bit)
  (reset (list (string (bit) (bit) (bit) (bit)))))

(4-bit)

("0000" "0001" "0010" "0011" "0100" "0101" "0110" "0111" "1000" "1001" "1010" "1011" "1100" "1101" "1110" "1111")

amb can be used anywhere in any expression to evaluate the expression once per supplied value. This limitless use can yield extraordinary results -

(reset
  (list
    (if (> 5 (amb 6 3))
        (string-append "you have "
                       (amb "dark" "long" "flowing")
                       " "
                       (amb "hair" "sentences"))
        (string-append "please do not "
                       (amb "steal" "hurt")
                       " "
                       (amb "any" "other")
                       " "
                       (amb "people" "animals")))))

("please do not steal any people"
 "please do not steal any animals"
 "please do not steal other people"
 "please do not steal other animals"
 "please do not hurt any people"
 "please do not hurt any animals"
 "please do not hurt other people"
 "please do not hurt other animals"
 "you have dark hair"
 "you have dark sentences"
 "you have long hair"
 "you have long sentences"
 "you have flowing hair"
 "you have flowing sentences")

surely this one is not "nebulous" in any way. :) – Will Ness Jun 26 '21 at 17:38 — Will Ness, Jun 26 '21 at 17:38
"exceeds comment limit" lmao :D – Mulan Jun 26 '21 at 17:40 — Mulan, Jun 26 '21 at 17:40

Does "map" necessarily produce an additional level of nesting?

3 Answers3

Linked