add flatten() to flatten list by mopp · Pull Request #3676 · vim/vim

mopp · 2018-12-08T09:01:09Z

This change adds a new small function flatten({list} [, {maxdepth}]) to flatten the given list to depth {maxdepth} like Ruby's flatten and Scala's flatten.

This function assists list processing combining list manipulation functions.
Here is example

" Collect paths from some patterns
echo flatten(map(['./xxx/*', './yyy/*'], 'glob(v:val, 0, 1)'))
" Split and filter strings
echo filter(flatten(map(zzz, 'split(v:val, ",")')), '!empty(v:val)')

The performance is good because it uses a loop instead of a recursive function call.
Some plugins (e.g., gina.vim, vim-snipmake) also need this function.
Currently these use library provided function (e.g., vital.vim, tlib_vim).

Thanks

codecov-io · 2018-12-08T09:18:11Z

Codecov Report

Merging #3676 into master will decrease coverage by <.01%.
The diff coverage is 94.87%.

@@            Coverage Diff             @@
##           master    #3676      +/-   ##
==========================================
- Coverage   78.47%   78.47%   -0.01%     
==========================================
  Files         103      103              
  Lines      141874   141913      +39     
==========================================
+ Hits       111333   111362      +29     
- Misses      30541    30551      +10

Impacted Files	Coverage Δ
src/evalfunc.c	`87.69% <100%> (+0.03%)`	⬆️
src/list.c	`89.32% <91.3%> (+0.11%)`	⬆️
src/gui.c	`58.05% <0%> (-0.31%)`	⬇️
src/sign.c	`92.23% <0%> (-0.14%)`	⬇️
src/gui_gtk_x11.c	`48.23% <0%> (-0.1%)`	⬇️
src/ex_cmds2.c	`84.7% <0%> (-0.1%)`	⬇️
src/window.c	`83.39% <0%> (+0.03%)`	⬆️
src/if_xcmdsrv.c	`83.99% <0%> (+0.35%)`	⬆️

Continue to review full report at Codecov.

Legend - Click here to learn more
Δ = absolute <relative> (impact), ø = not affected, ? = missing data
Powered by Codecov. Last update b1443b4...af475dd. Read the comment docs.

[Patch for https://github.com/mopp/vim/tree/add_flatten](https://gist.github.com/h-east/f229f9c380bd86c574f5ef421633e87b)

brammool · 2018-12-08T12:58:15Z

Mopp wrote:

This change add new small function `flatten({list} [, {maxdepth}])` to flatten the given list to depth `{maxdepth}`. This function assists list processing combining list manipulation functions. Here is example ```vim " Collect paths from some patterns echo flatten(map(['./xxx/*', './yyy/*'], 'glob(v:val, 0, 1)')) " Split and filter strings echo filter(flatten(map(zzz, 'split(v:val, ",")')), '!empty(v:val)') ``` The performance is good because it uses loop instead of recursive function call.

I'm a bit confused by the maxdepth argument. I would expect it to specify the maximum depth of the resulting list, thus flatten(list, 1) would always result in items that are not a list. But it appears it flattens by one level, thus if one of the items is a list of lists, the item becomes a list. Isn't it more useful to specify the maximum resulting depth? With the default being 1 this would result in a list of items: flatten([[[1, 2], 3, [4]], [5, 6]]) gives [1, 2, 3, 4, 5, 6] And flatten([[[1, 2], 3, [4]], [5, 6]], 2) gives [[1, 2, 3, 4], [5, 6]] That would work for two-dimensional arrays. I would expect the most often used form is to flatten a nested list into a list of items.

…

-- BLACK KNIGHT: The Black Knight always triumphs. Have at you! ARTHUR takes his last leg off. The BLACK KNIGHT's body lands upright. BLACK KNIGHT: All right, we'll call it a draw. "Monty Python and the Holy Grail" PYTHON (MONTY) PICTURES LTD /// Bram Moolenaar -- Bram@Moolenaar.net -- http://www.Moolenaar.net \\\ /// sponsor Vim, vote for features -- http://www.Vim.org/sponsor/ \\\ \\\ an exciting new programming language -- http://www.Zimbu.org /// \\\ help me help AIDS victims -- http://ICCF-Holland.org ///

mopp · 2018-12-08T13:48:31Z

@brammool Thanks for your comment.

I would expect the most often used form is to flatten a nested list into a list of items.

Yes, I think so too.

The documentation about maxdepth is not enough or the name maxdepth is not suitable.
Some examples are here

It is called limit in case of vital.vim.

echo s:L.flatten([[['a']], [[['b']], 'c']], 2)
" => ['a', ['b'], 'c']

It is called level in case of Ruby's flatten.

a = [ 1, 2, [3, [4, 5] ] ]
a.flatten!(1) 
# => [1, 2, 3, [4, 5]]

The argument means "How deeply it makes flatten the list" usually.

I think it is better to follow them.
The name maxdepth may be required to change such as limit, level, expand_depth or etc.

andymass · 2019-01-06T19:21:51Z

src/list.c

+    item = list->lv_first;
+    while (item != NULL && !got_int)
+    {
+	line_breakcheck();


Why do a breakcheck? I think many list processing functions do not check for interrupts. But most importantly, it appears to put the list into an indeterminate state; if the function does return OK I would expect the list to be list flattened to maxdepth.

it appears to put the list into an indeterminate state; if the function does return OK

Yes, It should return FAIL if interrupted.
I will fix it.

andymass · 2019-01-06T19:30:05Z

runtime/doc/eval.txt

 		it finds the file "tags.vim".

+flatten({list} [, {maxdepth}])					*flatten()*
+		Flatten {list} to depth {maxdepth}.  {maxdepth} means how


It should be noted that flattening is done in-place, i.e., modifies the list (as other vim list functions)

andymass · 2019-01-06T19:32:53Z

runtime/doc/eval.txt

+			:echo flatten([[[1], [2], [3]]], 1)
+<			[[1], [2], [3]]
+							        *E964*
+		{maxdepth} must be positive number.


Since zero is explicitly allowed (why?), this should say "must be a non-negative Number."

This description is right because the given list is NOT modified when the maxdepth is 0.

It can deal with when a calculation result of maxdepth becomes 0.

andymass · 2019-01-06T19:36:47Z

runtime/doc/eval.txt


+flatten({list} [, {maxdepth}])					*flatten()*
+		Flatten {list} to depth {maxdepth}.  {maxdepth} means how
+		deeply it makes flatten the list.  the depth is 1 when


This is not completely clear. Is it correct to say that the result is a List having depth N, i.e., a depth 1 List contains only Dict, Number, String, etc, whereas a depth 2 List may contain other lists (which do not contain lists themselves)?

I'm sorry. My English is not good.

Is it correct to say that the result is a List having depth N

I already described at the #3676 (comment) .
Please check src/testdir/test_flatten.vim for more examples.

Thanks for your reviews 😄

mopp · 2020-06-09T04:19:07Z

Thank you for merging! 🎉

brammool · 2020-06-09T12:50:52Z

Thank you for merging! 🎉

I did change the default depth from 1 to "max". It think it makes more sense.

…

-- Luxury. We used to have to get out of the lake at three o'clock in the morning, clean the lake, eat a handful of hot gravel, go to work at the mill every day for tuppence a month, come home, and Dad would beat us around the head and neck with a broken bottle, if we were LUCKY! /// Bram Moolenaar -- Bram@Moolenaar.net -- http://www.Moolenaar.net \\\ /// sponsor Vim, vote for features -- http://www.Vim.org/sponsor/ \\\ \\\ an exciting new programming language -- http://www.Zimbu.org /// \\\ help me help AIDS victims -- http://ICCF-Holland.org ///

vim-ml · 2020-06-09T14:16:19Z

Hi,

On Tue, Jun 9, 2020 at 5:51 AM Bram Moolenaar ***@***.***> wrote: > Thank you for merging! 🎉 I did change the default depth from 1 to "max". It think it makes more sense.

The ASAN build in Travis/CI is failing in test_flatten.vim. - Yegappan

Problem: Flattening a list with existing code is slow. Solution: Add flatten(). (Mopp, closes vim/vim#3676) vim/vim@077a1e6

mopp added 13 commits December 8, 2018 17:11

add flatten

60e7aae

refine flatten()

e07031d

fix style

eb67e99

remove unnecessary argument current_depth

63ccc52

raise error if maxdepth is negetive (wip)

97b5bc8

check interrupt

c12b716

use loop instead of recursive call (by mattn)

ed85e6b

add tests

365ea16

make the default maxdepth 1

13da15e

keep the given list if maxdepth is 0

a3a2486

fix error handling

0011f01

return FAIL if out of memory

aad61ca

add document

4b17de2

merge patch from h-east

934809f

[Patch for https://github.com/mopp/vim/tree/add_flatten](https://gist.github.com/h-east/f229f9c380bd86c574f5ef421633e87b)

mopp added 3 commits December 9, 2018 19:46

fix test

2e34152

update doc

c29fd36

use two spaces after a period

a564396

andymass reviewed Jan 6, 2019

View reviewed changes

mopp added 5 commits January 8, 2019 22:59

Merge branch 'master' into add_flatten

3e07951

use tv_get_number_chk

e883857

return FAIL if interrupted

a26d299

Note that flatten modifies the given list

1176e23

Merge branch 'master' into add_flatten

af475dd

brammool closed this in 077a1e6 Jun 8, 2020

mopp deleted the add_flatten branch June 9, 2020 01:56

cbarrete mentioned this pull request Jun 30, 2020

[RFC] vim-patch:8.2.{0935,0937} neovim/neovim#12575

Merged

shlomif pushed a commit to shlomif/neovim that referenced this pull request Jul 30, 2020

vim-patch:8.2.0935: flattening a list with existing code is slow

c5446db

Problem: Flattening a list with existing code is slow. Solution: Add flatten(). (Mopp, closes vim/vim#3676) vim/vim@077a1e6

Uh oh!

Conversation

mopp commented Dec 8, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

codecov-io commented Dec 8, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Codecov Report

Uh oh!

brammool commented Dec 8, 2018 via email

Uh oh!

mopp commented Dec 8, 2018

Uh oh!

andymass Jan 6, 2019

Choose a reason for hiding this comment

Uh oh!

mopp Jan 8, 2019

Choose a reason for hiding this comment

Uh oh!

andymass Jan 6, 2019

Choose a reason for hiding this comment

Uh oh!

andymass Jan 6, 2019

Choose a reason for hiding this comment

Uh oh!

mopp Jan 8, 2019

Choose a reason for hiding this comment

Uh oh!

andymass Jan 6, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

mopp Jan 8, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

mopp commented Jun 9, 2020

Uh oh!

brammool commented Jun 9, 2020 via email

Uh oh!

vim-ml commented Jun 9, 2020 via email

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

mopp commented Dec 8, 2018 •

edited

Loading

codecov-io commented Dec 8, 2018 •

edited

Loading

andymass Jan 6, 2019 •

edited

Loading

mopp Jan 8, 2019 •

edited

Loading