# Any built-in function to generate successive sublists from a list?

Given

lst = {a, b, c, d}


I'd like to generate

{{a}, {a, b}, {a, b, c}, {a, b, c, d}}


but using built-in functions only, such as Subsets, Partitions, Tuples, Permutations or any other such command you can choose. But it has to be done only using built-in commands. You can use a pure function, if inside a built-in command, i.e. part of the command arguments. That is OK.

It is of course trivial to do this by direct coding. One way can be

lst[[1 ;; #]] & /@ Range[Length[lst]]
(* {{a}, {a, b}, {a, b, c}, {a, b, c, d}}  *)


or even

LowerTriangularize[Table[lst, {i, Length[lst]}]] /. 0 -> Sequence @@ {}
(* {{a}, {a, b}, {a, b, c}, {a, b, c, d}}  *)


But I have the feeling there is a command to do this more directly as it looks like a common operation, but my limited search could not find one so far.

Sorry in advance if this was asked before. Searching is hard for such general questions.

-
How about something like Rest@FoldList[Append, {}, {a, b, c, d}]? More succinctly, FoldList[Append,{First@#},Rest[#]]&[{a,b,c,d}] – Leonid Shifrin Dec 18 '12 at 17:40
– Mr.Wizard Dec 19 '12 at 2:15

 lst={a,b,c,d};
ReplaceList[lst,{x__, ___} :> {x}]


Speaking of "common operation":

 Table[lst[[;; i]], {i, Length@lst}]

-
I was playing with a pattern based solution, +1 for ReplaceList. – image_doctor Dec 18 '12 at 19:27
+1, there's your 20k, btw. I've always had trouble with ReplaceList, and for me it is the second most annoying function that sounds useful. The most annoying being MapAt ... Although, I've more success with MapAt than ReplaceList. – rcollyer Dec 18 '12 at 19:53
@rcollyer, @image_doctor, Nasser, thanks for the votes. Rcollyer, for me too -- it always takes several attempts until I get MapAt and ReplaceList right. And, i don't remember ReplaceList winning any speed contests. – kglr Dec 18 '12 at 20:12
I found Position is a great way to get MapAt to behave itself, provided you can figure out how to specify what positions you need ... – rcollyer Dec 18 '12 at 20:27
@rcollyer Be careful with MapAt though. – Leonid Shifrin Dec 18 '12 at 20:29

Subsets takes an optional 3rd argument as Subsets[list, {n}, k] that gives you the kth sublist of length n. Since your sublists are in sequence, you'll always need k = 1. You can then use this as:

MapIndexed[First@Subsets[list, #2, 1] &, list]
(* {{a}, {a, b}, {a, b, c}, {a, b, c, d}} *)


Another alternative would be:

Reverse@Most@NestWhileList[Most, list, # != {} &]

-
Why are you using MapIndexed? Why not Subsets[list, #, 1][[1]]& /@ Range[Length@list]? It seems cleaner. – rcollyer Dec 18 '12 at 20:10
"Cleaner" is subjective and in this case, I positively dislike having to use Range@Length@foo when I don't have to. Far cleaner to use MapIndexed and ignore #1 – R. M. Dec 18 '12 at 20:20
+1. But the real clean solution here is to use linked lists, since all of the suggested ones have quadratic complexity in the length of the list. – Leonid Shifrin Dec 18 '12 at 20:28
@LeonidShifrin I thought of something like Flatten /@ Rest@FoldList[List, {}, {a, b, c, d}], but it was similar to your solution above and was hoping you'd post it – R. M. Dec 18 '12 at 20:39
FoldList by itself works. – rcollyer Dec 18 '12 at 20:41

A variant using Take.

list~Take~# & /@ Range@Length@list


{{a}, {a, b}, {a, b, c}, {a, b, c, d}}

One using NestList:

NestList[Most, list, Length@list - 1]


{{a, b, c, d}, {a, b, c}, {a, b}, {a}}

-

I am not sure this wins any speed contests, but it is a purely functional solution:

FoldList[#1~Join~{#2} &, {First@#}, Rest@#]& @ {a, b, c, d, e}
(* {{a}, {a, b}, {a, b, c}, {a, b, c, d}, {a, b, c, d, e}} *)

-
Ok, since you posted this, I am liberated from doing that (I gave it in comments to the question), and can happily upvote : +1. – Leonid Shifrin Dec 18 '12 at 21:03
+1, a variation: FoldList[Flatten@{##} &, {First@list}, Rest@list]? or FoldList[Sequence @@@ {##} &, {First@list}, Rest@list]? – kglr Dec 18 '12 at 21:06
@kguler I'd migrate list outside of FoldList, but I hate writing more than I have too. – rcollyer Dec 18 '12 at 21:15
@LeonidShifrin teach me to look at the comments before I post something ... Speed wise, though, is Join or Append faster. What about kguler's alternatives? – rcollyer Dec 18 '12 at 21:16
I think @kguler's use of ReplaceList is very elegant. For generic lists, should be quite fast. For packed arrays, Join and Append should be faster, since ReplaceList can not make use of those and will likely unpack. – Leonid Shifrin Dec 18 '12 at 21:20

What about Accumulate:

Function[lst, {{lst[[1]]}}~Join~Rest[Accumulate[lst] /. Plus -> List]]@{a, b, c, d, e}


Unfortunately it doesn't accept a custom function other than Plus and will not work for numerical list...

-

A variant using Partition:

First[Partition[list,#]]& /@ Range@Length@list

-

A joke solution:

Outer[Take, {{a, b, c, d, e}}, Range[5], 1] // First

-

This is not a built-in function to do it but it fits the criteria of only using buil-in functions. It avoids using patterns, mapping constructs and such things.

Maybe in the future ListCorrelate can accepts functions instead of heads (e.g. applying Plus to a list by default). I think that would make it more useful (but I am a beginner Mathematica user, so who am I to hold such opinions).

lst = {a, b, c, d};
DeleteCases[
ListCorrelate[lst, ConstantArray[1, Length@lst], 1, 0, Times,
List], 0, {2}]

-
FromLetterNumber@Range@Range[4]


{{a},{a,b},{a,b,c},{a,b,c,d}}

-