Given some finite list, return a list of all its prefixes, including an empty list, in ascending order of their length.

(Basically implementing the Haskell function inits.)


  • The input list contains numbers (or another type if more convenient).
  • The output must be a list of lists.
  • The submission can, but does not have to be a function, any default I/O can be used.
  • There is a CW answer for all trivial solutions.


[] -> [[]]
[42] -> [[],[42]]
[1,2,3,4] -> [[], [1], [1,2], [1,2,3], [1,2,3,4]]
[4,3,2,1] -> [[], [4], [4,3], [4,3,2], [4,3,2,1]]
  • \$\begingroup\$ If a language does not define any types except for characters, can I take input as a string and separate the input by newlines, in the case of a full program? \$\endgroup\$ – NieDzejkob Dec 8 '18 at 20:37
  • \$\begingroup\$ @NieDzejkob I'm not sure what consensus there is for this case, but the Brainfuck answer seems to do something like that. \$\endgroup\$ – flawr Dec 8 '18 at 21:18
  • \$\begingroup\$ Can we expect the list to be null-terminated? \$\endgroup\$ – user77406 Dec 9 '18 at 10:02
  • \$\begingroup\$ It's especially common in C/C++, main use being strings. \$\endgroup\$ – user77406 Dec 13 '18 at 14:46
  • \$\begingroup\$ @Rogem If it is that common I think allowing it is reasonable. \$\endgroup\$ – flawr Dec 13 '18 at 14:49

64 Answers 64

1 2

Elixir, 37 bytes

fn x->Enum.scan [[]|x],&(&2++[&1])end

Try it online!

Looking at other languages, this looks rather verbose, but I'm definitely not an expert in Elixir, so please let me know if I missed something obvious.

| improve this answer | |

APL (Dyalog Unicode), 12 bytes


Try it online!

Prefix tacit function. TIO link has boxing enabled to make the output more readable.


(0,∘⍳∘≢⊢)↑¨⊂ ⍝ Tacit fn, taking a vector as argument, which will be called ⍵ for simplicity.
         ↑   ⍝ Take the first ⍺ (left arg) elements of ⍵
          ¨⊂ ⍝ Since the ⍺ for ↑ is a vector, we enclose the ⍵ and apply ↑ to it for each of the elements in ⍺.
(      ⊢)    ⍝ Use ⍵ as argument for
      ≢      ⍝ Tally; yields the number of elements in ⍵
    ⍳∘       ⍝ Then, yield the range [1..≢⍵]
 0,∘         ⍝ and prepend a 0.

The function returns a vector of vectors, each with the first [0..≢⍵] elements of the argument.

| improve this answer | |

Bash, 34 bytes

I output each list element on a new line as someone else did - bash only has 1-D arrays:

for((;c<=$#;c++)){ echo ${*:1:c};}

Could be 1 byte less but this does not work for null case - don't see why... c++ does not get evaluated...

for((;c<=$#;)){ echo ${*:1:c++};}

This can output text as suggested by OP:

C='echo -n ';A=(${1//[],[]/ });$C[[];for((c=0;c<${#A[*]};)){ B=${A[*]::++c};$C,[${B// /,}];};echo ]

No one should have to decode that. Here is annotated version:

C='echo -n '              # basically a macro to improve my golf
A=( ${1//[],[]/ } )       # convert [,] to spaces - like magic this one
$C[[]                     # echo [[] since every list needs this
for((c=0;c<${#A[*]};)){   # for all elements of list
  B=${A[*]::++c}          # make space separated list of first c elements
  $C,[${B// /,}]          # prefix with ,[ and convert space to comma
echo ]                    # terminate list with ]
| improve this answer | |

Reticular, 60 bytes


Try it online!

Assumes that the input list is at the top of the stack. To test input, run the following code



B                         # Push every element from the input list to the stack.
 q                        # Reverse stack.
  l                       # Push the size of the stack to the stack.
   :D=                    # Save it as the variable D.
      :D`:E=              # Define the variable E = D.
            l             # Push D to the stack.
             [:D`@d]      # Push the function which duplicates the top D items in the stack
                    ~     # Swap the top two items in the stack
                     *    # Call the above function D number of times.

[                          ]            # Push a function that does the following:
 :E`b                                   # Put the top E items in a list.
     @q                                 # Reverse list that is at the top of the stack.
       M                                # Rotate stack so that top of stack -> bottom of stack.
        [$]:D`:E`-*                     # Delete the top D-E items from the stack.
                   :E`1-:E=             # Define E = E - 1.
                            :D`1+*      # Call the above function D+1 number of times.
                                  q     # Reverse stack.
                                   lb   # Put every item in the stack into a list.
                                     o; # Output the resulting list and exit.
| improve this answer | |
1 2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.