How To FLATTEN...Anything!

At one point, @szeng added a FLATTEN function (at least I think it was him, its only appearance is in Rebmake).

The idea was that sometimes you have a block of blocks, and you want to merge them all together:

>> flatten [[a] [b] c d [e f]]
== [a b c d e f]

>> flatten [[a] [b [c d]] c d [e f]]
== [a b [c d] c d e f]

>> flatten:deep [[a] [b [c d]] c d [e f]]
== [a b c d c d e f]

The usages in Rebmake look like:

rebmake.execution/run make rebmake.solution-class [
    depends: flatten reduce [
        vars
        prep
        t-folders
        dynamic-libs
    ]
]

I Started Fretting Over The Semantics :worried:

Being now the steward of this FLATTEN native, I had questions.

One set of questions are like: "Does it flatten just BLOCK!, or also GROUP! and FENCE!?"

But binding introduces more layers: "Does it bind the items using their container's binding before it tosses the container, or not?"

What kinds of refinements and interface complexities would you need to give people a good FLATTEN native?

...or Just Build Your Own Flatteners :building_construction:

SPLICE! is supported by MAP-EACH:

>> map-each item [[1 2] [3 4]] [reverse copy item]
== [[2 1] [4 3]]

>> map-each item [[1 2] [3 4]] [spread reverse copy item]
== [2 1 4 3]

That makes it a superpower for writing usermode flatteners. Here's the simplest version:

flatten: lambda [block [block!]] [
    map-each item block [
        either block? item [spread item] [item]
    ]
]

If you want a :DEEP you can have that too...

flatten: lambda [block [block!] :deep] [
    map-each item block [
        if deep and (block? item) [
            item: flatten:deep item
        ]
        if block? item [spread item] else [item]
    ]
]

Or, for you traditionalists....

flatten: lambda [block [block!] :deep] [
    map-each item block [
        all [
            deep
            block? item
            item: flatten:deep item
        ]
        either block? item [spread item] [item]
    ]
]

Here I'm using map-each item in my enumeration (as opposed to, say map-each 'item) so you're getting bindings propagated from the blocks to the items. But if you had logic for when to bind or unbind, you could throw that in too.

What About Cycles? (Recursive References To The Same List)

For what it's worth, the old FLATTEN native didn't handle this. So it may seem we're not any worse off...

But usermode doesn't have quite the same toolset to stop cycles. For instance: if you tried to maintain a mapping via MAP! from lists to whether they've been flattened already on a given descent branch, putting a BLOCK! in as a key would freeze its mutability deeply...which isn't generally desirable.

I think that suggests we need some kind of STUB! type, which holds onto the identity of a series without being the series. Basically a pointer that keeps the little tracking entity for a list alive for GC, that you can put in a MAP! without semantically putting the value itself in the map.

(Putting things like FLATTEN in usermode helps push on these features to make sure we're not relying on them being native to accomplish their work.)

1 Like

On top of everything else cool about this...

...the part I'm probably most proud of is:

The undecorated code is the correct code.

You don't have to worry about the edge cases that can bite you like in Redbol.

A Study In Contrasts

MAP-EACH is a poster-child for why you need to put splicing intent on the value. Because if you have just MAP-EACH and MAP-EACH/ONLY, then you can't pick on a per-iteration basis whether you'll splice or not.

(Well, if MAP-EACH always spliced, then you could pick not-splicing by wrapping things in blocks...though that's convoluted and wasteful.)

Anyway, Red doesn't have a MAP-EACH of any kind. If we use COLLECT and FOR-EACH, then we get a KEEP that can either splice or not:

red>> flatten: func [block [block!]] [
          collect [foreach item block [
               either block? item [keep item] [keep/only item]
          ]]
      ]

Of course, it's obfuscated. :roll_eyes: You have to know blocks splice by default, and you have to throw that /ONLY in on things you don't want to splice.)

Putting that aside for a moment, it seems to work...at first:

red>> flatten [[a] [b] c d [e f]]
== [a b c d e f]

Yet Red is easily foiled:

red>> flatten reduce [[10 + 20] :reverse [30 [+] 4]]
*** Script Error: either is missing its false-blk argument

Behind the scenes, when item holds an action like REVERSE it acts like that function:

either block? item [keep item] [keep/only item]

; acted like...

either block? reverse [keep reverse] [keep/only reverse]

Thus, you find out that if you were going to be correct you should have written:

red>> flatten: func [block [block!]] [
          collect [foreach item block [
               either block? :item [keep :item] [keep/only :item]
          ]]
      ]

red>> flatten reduce [[10 + 20] :reverse [30 [+] 4]]
== [10 + 20 make action! [[
     {Reverses the order of elements; returns at s...  ; (it's right)

(It was at your discretion whether to say [keep :item] or [keep item]once you knew it was a block, because the : wasn't required... but just to be safe, maybe you should do it all the time?)

This Shows You Just How Far Things Have Come

Putting them side-by-side...

; Redbol

flatten: func [block [block!]] [
    collect [foreach item block [
        either block? :item [keep item] [keep/only :item]
    ]]
]

; Ren-C

flatten: lambda [block [block!]] [
    map-each item block [
        either block? item [spread item] [item]
    ]
]

...you see the triumph of the Isotopic Model. And it only costs one...measly...byte.

:atom_symbol:

From my slides twelve years ago in Montreal:

1 Like

A Note About FRAME! in Ren-C

Ren-C is able to store functions in blocks, but not in their antiform state. (An ACTION! is an antiform of FRAME!, and the antiform state is the only one that dispatches through WORD! references.)

>> data: reduce [[10 + 20] reverse/ [30 [+] 4]]
** PANIC: Invalid use of ~&[frame! [series part]]~ antiform
** Id: bad-antiform

The oddly named UNRUN function turns antiform frames (actions) into regular FRAME!s. (Better names welcome, but RUNS is what you pass FRAME! to in order to get an ACTION!)

>> data: reduce [[10 + 20] unrun reverse/ [30 [+] 4]]
== [10 + 20 &[frame! [series part]] 30 + 4]

>> type of data.2
== \~{frame!}~\  ; antiform (datatype!)

As you see, picking the FRAME! out of the block with a TUPLE! does not run it. But you can run it using a PATH! access:

>> data/2 [a b c]
== [c b a]