Prolog flatten/2 实现
Prolog flatten/2 implementation
这是我对 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).
给出预期结果:
?- flt([1,[2,3,[4,5],6],7], X).
X = [1, 2, 3, 4, 5, 6, 7]
但是,当我点击 ;
时,超出了堆栈限制。为什么会这样?无限递归在哪里?
谢谢。
问题是您调用 append(R, F, X)
时仅使用 未实例化的 变量。
flt(+List, -Flatlist)
只有一种解法。然而,在回溯中,append(R, F, X)
一次又一次地尝试,却没有找到另一个解决方案...
你可以通过提问来测试
?- 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]
...
解决方案是重新安排第三个子句中的目标:
flt([H|L], X):-
flt(H, R),
flt(L, F),
append(R, F, X).
这是一个很好的例子,说明 Prolog 不是纯粹声明性的,因为它通过简单的时间顺序 回溯来实现解析,从而在语言上强制执行过程特征。
为了说明问题,请查看此跟踪(我 跳过了很多 以强调循环问题):
[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]) ?
这张图以图形方式显示了它。要求额外答案后发生的事情是红色的。
另一种可能的解决方案是添加削减:
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).
这是我对 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).
给出预期结果:
?- flt([1,[2,3,[4,5],6],7], X).
X = [1, 2, 3, 4, 5, 6, 7]
但是,当我点击 ;
时,超出了堆栈限制。为什么会这样?无限递归在哪里?
谢谢。
问题是您调用 append(R, F, X)
时仅使用 未实例化的 变量。
flt(+List, -Flatlist)
只有一种解法。然而,在回溯中,append(R, F, X)
一次又一次地尝试,却没有找到另一个解决方案...
你可以通过提问来测试
?- 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]
...
解决方案是重新安排第三个子句中的目标:
flt([H|L], X):-
flt(H, R),
flt(L, F),
append(R, F, X).
这是一个很好的例子,说明 Prolog 不是纯粹声明性的,因为它通过简单的时间顺序 回溯来实现解析,从而在语言上强制执行过程特征。
为了说明问题,请查看此跟踪(我 跳过了很多 以强调循环问题):
[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]) ?
这张图以图形方式显示了它。要求额外答案后发生的事情是红色的。
另一种可能的解决方案是添加削减:
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).