Prolog flatten/2 implementation

Question

Here is my implementation of flatten/2:

flt([], []).
flt([H|L], [H|X]):-
    not(is_list(H)),
    flt(L, X).
flt([H|L], X):-
    append(R, F, X),
    flt(H, R),
    flt(L, F).

The expected result is given:

?- flt([1,[2,3,[4,5],6],7], X).
X = [1, 2, 3, 4, 5, 6, 7]

However, when I hit ; the stack limit is exceeded. Why does this happen? Where is the infinite recursion?

Thanks.

Answer 1

The problem is that you call append(R, F, X) with only uninstantiated variables.

There is only one solution for flt(+List, -Flatlist). However, on backtracking, append(R, F, X) is tried again and again and again without ever finding another solution...

You can test this by asking

?- append(R, F, X).
R = [],
F = X ;
R = [_948],
X = [_948|F] ;
R = [_948, _960],
X = [_948, _960|F] ;
R = [_948, _960, _972],
X = [_948, _960, _972|F] ;
R = [_948, _960, _972, _984],
X = [_948, _960, _972, _984|F] ;
R = [_948, _960, _972, _984, _996],
X = [_948, _960, _972, _984, _996|F] 
...

The solution is to rearrange the goals in your third clause:

flt([H|L], X):-
    flt(H, R),
    flt(L, F),
    append(R, F, X).

This is a very good example for the fact that Prolog is not purely declarative, since its implementation of resolution by simple chronological backtracking forces procedural features on the language.

---

To illustrate the problem, have a look at this trace (where I skipped a lot in order to just emphasize the loop problem):

[trace]  ?- flt([[a]],X).
   Call: (8) flt([[a]], _680) ? creep
^  Call: (9) not(is_list([a])) ? creep
^  Fail: (9) not(user:is_list([a])) ? creep
   Redo: (8) flt([[a]], _680) ? creep
   Call: (9) lists:append(_904, _906, _680) ? creep
   Exit: (9) lists:append([], _680, _680) ? creep
   Call: (9) flt([a], []) ? skip
   Fail: (9) flt([a], []) ? creep
   Redo: (9) lists:append(_904, _906, _680) ? creep
   Exit: (9) lists:append([_890], _898, [_890|_898]) ? creep
   Call: (9) flt([a], [_890]) ? skip
   Exit: (9) flt([a], [a]) ? creep
   Call: (9) flt([], _898) ? skip
   Exit: (9) flt([], []) ? creep
   Exit: (8) flt([[a]], [a]) ? creep
X = [a] ;
   Redo: (9) flt([a], [_890]) ? skip
   Fail: (9) flt([a], [_890]) ? creep
   Redo: (9) lists:append([_890|_892], _918, [_890|_898]) ? creep
   Exit: (9) lists:append([_890, _902], _910, [_890, _902|_910]) ? creep
   Call: (9) flt([a], [_890, _902]) ? skip
   Fail: (9) flt([a], [_890, _902]) ? creep
   Redo: (9) lists:append([_890, _902|_904], _930, [_890, _902|_910]) ? creep
   Exit: (9) lists:append([_890, _902, _914], _922, [_890, _902, _914|_922]) ? creep
   Call: (9) flt([a], [_890, _902, _914]) ? skip
   Fail: (9) flt([a], [_890, _902, _914]) ? creep
   Redo: (9) lists:append([_890, _902, _914|_916], _942, [_890, _902, _914|_922]) ? creep
   Exit: (9) lists:append([_890, _902, _914, _926], _934, [_890, _902, _914, _926|_934]) ? creep
   Call: (9) flt([a], [_890, _902, _914, _926]) ? skip
   Fail: (9) flt([a], [_890, _902, _914, _926]) ? creep
   Redo: (9) lists:append([_890, _902, _914, _926|_928], _954, [_890, _902, _914, _926|_934]) ? creep
   Exit: (9) lists:append([_890, _902, _914, _926, _938], _946, [_890, _902, _914, _926, _938|_946]) ? creep
   Call: (9) flt([a], [_890, _902, _914, _926, _938]) ? skip
   Fail: (9) flt([a], [_890, _902, _914, _926, _938]) ? creep
   Redo: (9) lists:append([_890, _902, _914, _926, _938|_940], _966, [_890, _902, _914, _926, _938|_946]) ? creep
   Exit: (9) lists:append([_890, _902, _914, _926, _938, _950], _958, [_890, _902, _914, _926, _938, _950|_958]) ? creep
   Call: (9) flt([a], [_890, _902, _914, _926, _938, _950]) ? skip
   Fail: (9) flt([a], [_890, _902, _914, _926, _938, _950]) ? creep
   Redo: (9) lists:append([_890, _902, _914, _926, _938, _950|_952], _978, [_890, _902, _914, _926, _938, _950|_958]) ? 

This drawing shows it graphically. What happens after asking for an additional answer is colored red.

---

Another possible solution is to add cuts:

flt([], []).
flt([H|L], [H|X]):-
    not(is_list(H)),
    flt(L, X),
    !.

flt([H|L], X):-
    append(R, F, X),
    flt(H, R),
    !,
    flt(L, F).