# P Pr Pre Pref Prefi Prefix Prefixe Prefixes

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.)

### Details

• 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.
• This is , so the shortest code in bytes wins

### Example

[] -> [[]]
[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]]

• 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? Dec 8 '18 at 20:37
• @NieDzejkob I'm not sure what consensus there is for this case, but the Brainfuck answer seems to do something like that. Dec 8 '18 at 21:18
• Can we expect the list to be null-terminated?
– user77406
Dec 9 '18 at 10:02
• It's especially common in C/C++, main use being strings.
– user77406
Dec 13 '18 at 14:46
• @Rogem If it is that common I think allowing it is reasonable. Dec 13 '18 at 14:49

# Ruby, 31 29 bytes

->a{[a*i=0]+a.map{a[0,i+=1]}}


Try it online!

Explanation:

->a{             # take array input a
[a*i=0]+       # set i to 0 and add whatever comes next to [[]] (a*0 == [])
a.map{         # for every element in a (basically do a.length times)
a[0,i+=1]  # increment i and return the first i-1 elements of a to map
}
}


# 05AB1E, 8 bytes

That was my first succesfull golf! Thanks for being such a nice community!

)UŒ¹g£Xš


Try it online!

## Explanation:

)UŒ¹g£Xš
)        : Create an empty list
U       : Save it to variable ˙X˙
Œ      : Make the "substrings" of the implicit input
¹g£   : Take the first n elements of the result where n is the lenght of input
Xš : Add the empty list to the beginning


# Scala, 21 bytes

_.inits.toSeq.reverse


Try it online!

Not quite a trivial answer, since I had to deal with the fact that the inits method returns an iterator in the reverse of the required order.

• Not sure if this is valid since this is a function, not a lambda (and you're excluding the function declaration part). Hmmmmmm Jan 2 '19 at 2:05
• @ASCII-only This is Scala's underscore shorthand syntax. It's basically a lambda. Compare to Haskell's sections. See also codegolf.meta.stackexchange.com/questions/11223/… Jan 2 '19 at 6:24
• Yes, but it can not be assigned to a variable (lambda function). On the other hand, {_.inits.toSeq.reverse} can. Jan 2 '19 at 6:27
• @ASCII-only Nope, the braces are not needed (though you do need to use val instead of var for some reason): tio.run/##JYq9CgIxEAb7e4qvTCAE/… Jan 2 '19 at 6:38
• Oh wait, you can define functions like variables, nvm Jan 2 '19 at 6:39

# C (gcc), 102 97 bytes

Pretty long, as C quite obviously isn't well-suited to manipulating lists of lists. Dependent on certain behavior; running on some platforms requires changing int to short (for +2 bytes), due to wchar_t being UTF-16 rather than UTF-32. Should work on Linux as-is.

Takes in a pointer to the first element of the input array, the length of the array, and a pointer to the variable in which the pointer to output will be stored. Produces a list of lists such that the first integer in the linear array stores the number of sub-lists. Sub-lists start with the number of elements, and are stored in memory in a contiguous manner.

p(r,e,f,i,x)int*e,**r,*x;{x=*r=malloc(4-++f*~f*2);*x++=f;for(i=0;i<f;x+=++i)wmemcpy(x+1,e,*x=i);}


Try it online!

## Degolf

p(r,e,f,i,x) int**r,*e,*x; // Function p(), where r is a pointer to the output variable,
// e is a pointer to the input location and f is the size of
// the input.
{
x=*r=malloc(4-++f*~f*2); // Allocate 4*(x+1)*(x+2)/2+4 bytes of memory.
// This is the exact amount of memory needed.
*x++=f;                  // Store n+1 (number of sub-lists) in the first four bytes.
for(i=0;i<f;x+=++i)      // Iterate over [0, n]->i and
// increment the pointer to x by i+1 every iteration.
wmemcpy(x+1,e,*x=i);   // Set first element at location pointed to by x to i,
// then copy i of either 2 or 4 byte elements, depending on
// the system wchar implementation, to location pointed to
// by x+1.
}

• @ceilingcat Thanks, will edit it in later when I get back onto a PC.
– user77406
Jan 2 '19 at 20:34

# C# (Visual C# Interactive Compiler), 48 bytes

l=>new int[l.Count()+1].Select((_,n)=>l.Take(n))


Try it online!

### Explanation

l=>                                                // Function with list l as argument
new int[l.Count()+1]                            // A new array (int is shortest type available) of length l + 1
.Select((_,n)=>l.Take(n))   // Where every element is mapped to the first n elements of the input list, where n is the index


# Lua 5.3, 92 bytes

function f(...)t=...if#t>0then return f({table.unpack(t,1,#t-1)},...)else return{...}end end


Keeps creating a copy of the array-like table with the element at the end removed and prepending it to the varargs until the length of the table is 0, then puts the varargs in a table. Relies on defining the variable f to allow recursion.

# Lua 5.1, 87 bytes

function f(...)t=...if#t>0 then return f({unpack(t,1,#t-1)},...)else return{...}end end


unpack is a global variable rather than a member of the table library. 0then is syntactically invalid in Lua 5.1, but strangely not in Lua 5.3.

# Pari/GP, 23 bytes

a->[a[1..n]|n<-[0..#a]]


Try it online!

# Pip, 16 bytes

{h@<a}M,1+#(h:a)


Try it online!

### Explanation

      M            Map
{h@<a}                 Function returning global variable h, cut at index a, and left part taken (0-indexed)
,               Range from 1 to
1+#(   )           1 + the length of
h:a                Assign global variable h to a, evaulating to the value of h (which is also the value of a - the first parameter to the function)


# Factor, 63 bytes

USE: fry [ [ dup '[ nip _ swap head ] map-index ] keep suffix ]


Keeps a copy of the input to tack on at the end, like C#.

# FALSE, 57 bytes

1^[$~][\1+^]#%a:0[$a;1->~][0[$@$@>][$a;\-ø,1+]#\%10,1+]#  Try it online! (you'll have to copy paste the code. Click "Show" and then run) Like brainf*ck, FALSE only takes one char at a time as input, so this program splits a string into prefixes, separating them with a newline. Explanation: 1^ {push 1 {counter) and first character onto stack} [~][ {while a character is input:} \1+^ {add 1 to the counter} ]# % {drop truth value from stack} a: {define the counter as the variable "a'} 0 {push 0 onto stack (loopvar)} [a;1->~][ {while loopvar is less than a-1:} 0 {push 0 (loopvar2)} [@@>][ {while loopvar is greater than loopvar2}$a;\- {a-loopvar2 (to get index of char to print)}
ø,     {copy value at index to top of stack and print}
1+     {increment loopvar2}
]#
\%       {swap'n'drop (get rid of loopvar2)}
10,      {print newline}
1+       {increment loopvar}
]#


A FALSE expert could probably do this using no variables (pure stack) but since I only learnt this language yesterday I think this is alright.

# MathGolf, 7 bytes

hæ_ï<\]


Try it online!

## Explanation

h         length of array/string without popping
æ        start block of length 4
_       duplicate TOS
ï      index of current loop, or length of last loop
<     slice list
\    swap top elements
]   end array / wrap stack in array

• Nice 7 byte alternative to my 7-byter I found an hour ago. :) Actually, I see I can golf mine to 6 bytes by changing { to Å. Thanks for the implicit golf. Now I just need to fix the test suite somehow.. Dec 10 '18 at 14:49
• You could save a byte for that one by replacing { with Å and removing the }. MathGolf has 1-byte literals for blocks of size up to 8 bytes.
– maxb
Dec 10 '18 at 14:53
• Just edited my comment when I realized that. Just not sure how to fix the test suite.. Dec 10 '18 at 14:53

# MathGolf, 97 6 bytes

hÅ_╡]x


-1 byte thanks to @maxb.

Explanation:

h        # Push the length of the (implicit) input-array, without popping the array
Å       # Loop this length amount of times,
# and do the following two commands each iteration:
_      #  Duplicate the array at the top of the stack
╡     #  Remove the right-most item of the array
]    # After the loop, wrap everything on the stack in an array
x   # Reverse it (and output implicitly)

• hÅ_╡]x saves one byte. For doing test suites, just add one input per line, and the code will be executed separately for each input. Check my answer for an example. I should describe that feature better in the docs.
– maxb
Dec 10 '18 at 14:56
• @maxb Thanks, that simplifies the test suite a lot. Need to remember that. And thanks for the golf! Dec 10 '18 at 15:00

## Clojure, 21 bytes

#(reductions conj[]%)


# Ruby, 34 31 bytes

->l{(0..l.size).map{|i|l[0,i]}}


Try it online!

Thanks @ConorO'Brien!

• You can golf this a bit like so: ->l{(0..l.size).map{|i|l[0,i]}}, using [0,i] for indexing instead of .first i Dec 10 '18 at 23:25
• @ConorO'Brien: Thanks a lot! 1 fewer byte than Python now :D Dec 11 '18 at 8:24

# Gambit Scheme (gsi), 77 72 bytes

(define(p z)(if(pair?(car z))(p(cons(reverse(cdr(reverse(car z))))z))z))


Try it online!

First time using Scheme. It's a function that takes a wrapped list ((list (list 1 2 3 4))) as an argument.

• I think you might want to reverse that if test. Dec 12 '18 at 20:00
• @ØrjanJohansen Yep. Thank you. Dec 12 '18 at 20:23

# D, 70 bytes (31 imports, 39 expression)

import std.algorithm,std.range;
alias prefixes = t=>(t.length+1).iota.map!(i=>t.take(i));


Try it online!

edit: Do I count the alias prefixes = part? You can use the lambda without it, but you have to add parens to disambiguate, so should I count it as 42?

• I don't program in D, but I think you don't count the alias prefixes. Python lambdas are very similar and they act in that way. Dec 10 '18 at 15:39
• There is one problem though. I'm pretty sure you need to count the imports. Dec 10 '18 at 18:32
• Wait, none of the others use standard library routines? edit: I feel it'd be kind of silly to make code size dependent on what standard definitions the language chooses to make available by default. That seems more of a judgment of a language's module system than its expressivity. Dec 10 '18 at 21:33
• Though fair enough, the Java example seems to count module names. Bleh. edit: Though it seems pretty nonsensical to count the imports and not the alias, and in any case what about the void main()... seems like it'd just become a boilerplate size contest, rather than expression size. Dec 10 '18 at 21:39
• So, in response to my above comment: this would count as 70 bytes. (Note: a golf was applied changing two imports to a single import) Dec 11 '18 at 18:38

• Input is in Row 1
• A2: COUNTA(1:1)
• Output: =ArrayFormula(IF(A2,{T(SEQUENCE(1,A2));IF(SEQUENCE(A2)>=SEQUENCE(1,A2),OFFSET(A1,,,,A2),)},

## Output Formatted:

=ArrayFormula(IF(
A2,
{
T(SEQUENCE(1,A2));
IF(
SEQUENCE(A2)>=SEQUENCE(1,A2),
OFFSET(A1,,,,A2),
)
},
))


# Vyxal, 3 bytes

K¾p


Try it Online!

• Unfortunately, the results have to contain the empty list. May 31 '21 at 3:06
• I'm not happy that the 1 byte answer isn't valid either. But 3 bytes is the best I can think of May 31 '21 at 3:07
• @lyxal oh i didn't notice the empty list requirement before, but we have to accept our fate, whatever May 31 '21 at 3:08

i[]=[[]]
i l=i(init l)++[l]


Try it online!

# Canvas, 6 5 bytes

）╶［｝）


Try it here!

Outputs to the stack; Linked with a trailing ｒａｗ so that's visible.

)      wrap the (currently empty) stack in an array
╶[}   map nothing over the prefixes of the input
)  wrap the stack (the empty array and the prefixes) in an array


2 bytes without the starting empty array.

# Attache, 13 bytes

{_[0...0:#_]}


Try it online!

## Explanation

{_[0...0:#_]}
{           }    block taking _ as input
_[        ]     index from the input
0:#_      range from 0 to the length of _ inclusive
0...          range from 0 to each number that range, right exclusive


# Tcl, 81 bytes

set i -1
set a {{}}
foreach _ $argv {lappend a [lrange$argv 0 [incr i]]}
puts $a  Try it online! # Red, 76 bytes func[b][a: copy[[]]c: b until[append/only a copy/part b c: next c tail? c]a]  Try it online! # Kotlin, 32 bytes {l->(0..l.size).map{l.take(it)}} { list -> (0..list.size).map { // map over range [0, length of list] list.take(it) // first n items of list } }  Try it online! # Pushy, 7 bytes 1@$O_vI


Try it online!

# Tcl, 65 bytes

proc P {L J\ {{}}} {lmap e $L {lappend J [lappend K$e]}
list $J}  Try it online! # MY, 7 bytes ωωι0;↑←  Try it online! Woah ... never thought MY would actually come in handy. ## How? ωωι0;↑← • ω = push(arg[0]) • ω = push(arg[0]) • ι = push([1 ... pop()]) • 0 = push(0) • ; = push(pop() + pop()) • ↑ = does the prefixing work by vecifying in a stupid manner. • ← output # Z80Golf, 18 bytes 00000000: 2511 00ff 1b1a ffa7 20fa cd03 802b 7730 %....... ....+w0 00000010: f076 .v  Try it online! Takes bytes through STDIN with no null bytes and prints a series of prefixes, each terminated by a null byte. Source code:  dec h start: ld de,$ff00
.printloop:
dec de
ld a, (de)
rst $38 and a jr nz, .printloop call$8003
dec hl
ld (hl), a
jr nc, start
halt


# Forth (gforth), 57 bytes

: x here 0 begin 2dup type cr 1+ key dup c, 5 < until ; x


Try it online!

Takes bytes through STDIN and prints a series of prefixes, each terminated by a newline.

# str, 6 bytes

e;:dno


Try it online!

Each output line corresponds to an entry in the prefix array.

## Explanation

e;:dno
-- preamble --
e           push empty string
-- iteration --
:         append current char to build string
d        duplicate it
n       push "\n"
o      output it
(implicitly output duplicated entry)