Prolog flatten/2 implementation

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.

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