After a lot of trouble I've finally come pretty close to what I want to do. I now have a list that looks like this:

{"turen", {{"as", {{"lä", {}}}}, {"al", {{"säd", {}}, {"jäs", {}}}}, {"aj", {{"lä", {}}, {"säl", {}}, {"säd", {}}, {"läs", {}}}}, {"sa", {{"lä", {}}}}, 
  {"la", {{"säd", {}}, {"jäs", {}}}}, {"lä", {{"as", {}}, {"aj", {}}, {"sa", {}}, {"ja", {}}}}, {"ja", {{"lä", {}}, {"säl", {}}, {"säd", {}}, {"läs", {}}}}, 
  {"sal", {}}, {"säl", {{"aj", {}}, {"ja", {}}}}, {"säd", {{"al", {}}, {"aj", {}}, {"la", {}}, {"ja", {}}}}, {"läs", {{"aj", {}}, {"ja", {}}}}, 
  {"dal", {{"jäs", {}}}}, {"jäs", {{"al", {}}, {"la", {}}, {"dal", {}}}}, {"sälj", {}}, {"själ", {}}, {"läsa", {}}, {"ädla", {}}, {"dals", {}}, {"jäsa", {}}, 
  {"sälja", {}}, {"ädlas", {}}}}

Now the last thing I need to do is pick out all strings on the fourth level and concatenate them with their ancestors. There aren't any fourth level elements in my example list because those lists are huge. But imagine there is. If I know how to do it for two levels I can probably do it for three or four as well.

For example, if I concatenate up to the second level I should get a list that starts like

{"turen as lä","turen al säd" ...}
  • 1
    $\begingroup$ There is apparently some confusion as to your requirements. Are the answers below working as desired or do you need what rm-rf describes in the comments below mine? $\endgroup$
    – Mr.Wizard
    Jan 13, 2013 at 3:34
  • 1
    $\begingroup$ @Mr.Wizard I was being vague, but in the end I got good solutions that work for me anyway. I may have had in mind something like what rm-rf said but I don't particularly need it. So it's not a necessary criteria for a solution. Thanks. $\endgroup$
    – C. E.
    Jan 14, 2013 at 1:00

2 Answers 2


What you really want is a recursive traversal function, since what you constructed is a form of a prefix tree. Here is one possibility:

traverse[prev_List, {s_String, {sub__}}] :=
  Map[traverse[{prev, s}, #] &, {sub}];

traverse[prev_List, {s_String, {}}] := 
  StringJoin[Riffle[Flatten[{prev, s}], " "]];

traverse[tree_List] := Flatten[traverse[{}, tree]];

The usage is


where tree is your nested list above. The result is a list of strings you are after:

(* {turen as lä,turen al säd,turen al jäs,<<34>>,turen sälja,turen ädlas} *)
  • $\begingroup$ I see that you interpreted this differently (and probably correctly). Try try again... $\endgroup$
    – Mr.Wizard
    Jan 13, 2013 at 0:55
  • $\begingroup$ @Mr.Wizard Somehow we have different results. In my case, there are more strings, but all of them contain 3 parts (for this particular case). You have less strings but some of them containing more parts. $\endgroup$ Jan 13, 2013 at 0:57
  • $\begingroup$ Yes, after reading the question again I think I got it totally wrong. $\endgroup$
    – Mr.Wizard
    Jan 13, 2013 at 0:57
  • 1
    $\begingroup$ @Mr.Wizard To tell you the truth, I've been disappointed in the methods like those based on many nested Map,Thread etc. for a long time, as long as treatment of trees and other recursive structures is concerned. The biggest problem with them is that they realize recursion internally, while what is needed is a custom recursion tuned to a very particular data structure. But they work very well as a part of a recursive solution, making the code much shorter indeed. $\endgroup$ Jan 13, 2013 at 1:00
  • $\begingroup$ I think I've got it now. Can you confirm? $\endgroup$
    – Mr.Wizard
    Jan 13, 2013 at 1:34

Second try:

dat = {"turen", {{"as", {{"lä", {}}}}, {"al", {{"säd", {}}, {"jäs", {}}}}, {"aj", {{"lä", \
{}}, {"säl", {}}, {"säd", {}}, {"läs", {}}}}, {"sa", {{"lä", {}}}}, {"la", {{"säd", {}}, \
{"jäs", {}}}}, {"lä", {{"as", {}}, {"aj", {}}, {"sa", {}}, {"ja", {}}}}, {"ja", {{"lä", \
{}}, {"säl", {}}, {"säd", {}}, {"läs", {}}}}, {"sal", {}}, {"säl", {{"aj", {}}, {"ja", \
{}}}}, {"säd", {{"al", {}}, {"aj", {}}, {"la", {}}, {"ja", {}}}}, {"läs", {{"aj", {}}, \
{"ja", {}}}}, {"dal", {{"jäs", {}}}}, {"jäs", {{"al", {}}, {"la", {}}, {"dal", {}}}}, \
{"sälj", {}}, {"själ", {}}, {"läsa", {}}, {"ädla", {}}, {"dals", {}}, {"jäsa", {}}, \
{"sälja", {}}, {"ädlas", {}}}};


dat //. {{s_, {}} :> s, {x_, y_List} :> Thread[x ~~ " " ~~ y]};

Flatten[Thread /@ %]
turen as lä
turen al säd
turen al jäs
turen aj lä
turen aj säl
turen aj säd
turen aj läs
turen sa lä
turen la säd
turen la jäs
turen lä as
turen lä aj
turen lä sa
turen lä ja
turen ja lä
turen ja säl
turen ja säd
turen ja läs
turen sal
turen säl aj
turen säl ja
turen säd al
turen säd aj
turen säd la
turen säd ja
turen läs aj
turen läs ja
turen dal jäs
turen jäs al
turen jäs la
turen jäs dal
turen sälj
turen själ
turen läsa
turen ädla
turen dals
turen jäsa
turen sälja
turen ädlas
  • 1
    $\begingroup$ Looks like you've nailed it, +1. Generally, I found recursion to be more powerful than rules + ReplaceRepeated, but here apparently the latter is enough. Nice solution! $\endgroup$ Jan 13, 2013 at 1:39
  • 1
    $\begingroup$ I think the question asked for a way to be able to join words up to some level X, not all the way. Or rather, start with an inner string at level X and prepend all its predecessors. $\endgroup$
    – rm -rf
    Jan 13, 2013 at 2:24
  • $\begingroup$ @rm-rf what is supposed to happen to the deeper elements then? $\endgroup$
    – Mr.Wizard
    Jan 13, 2013 at 2:39
  • $\begingroup$ My interpretation was that the deeper ones will be ignored. Taking the above example, if they wanted to concatenate for "level 1" with its ancestors (taking "turen" to be level 0), then they'd get {"turen as", "turen al", "turen aj"...}. For level 2, they'd get the above list without the two word strings (i.e. "turen själ", "turen jäsa",...) $\endgroup$
    – rm -rf
    Jan 13, 2013 at 2:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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