Prolog用差分列表实现队列时追加元素后旧队列无法复用问题
问题核心原因
Prolog的逻辑变量是单次绑定的,一旦完成绑定就无法修改值。你第一次执行queue_last(Q, 999, Q_)时,空队列Q的两个差分端点原本是同一个未绑定的自由变量Hole,匹配queue_last的参数[L|Q0]时,Hole会被直接绑定为[999|NewHole]。此时原Q的内容已经变成queue(0, [999|NewHole], [999|NewHole]),不再是空队列,再次调用queue_last(Q, 888, Q__)时,会尝试把列表的首元素匹配为888,和已绑定的999产生冲突。
差分列表框架下的解决方案
不需要更换队列实现逻辑,只要调整使用方式或者做微小的适配即可解决问题:
方案1:遵循功能式使用规范,仅使用操作返回的新队列
差分队列的所有写操作都会返回新的队列实例,旧的队列实例操作后不再复用即可。你报错的代码只要改成使用前一次返回的队列实例作为输入就能正常运行:
empty_queue(Q), queue_last(Q, 999, Q_), queue_last(Q_, 888, Q__)
执行后得到的Q__为queue(s(s(0)), [999, 888|_], _),是符合预期的双元素队列。
方案2:需要多次从空队列创建不同分支的队列时,重新生成空队列
如果你需要基于空队列生成多个完全独立的队列,不需要复用同一个Q变量,每次调用empty_queue即可生成新的带独立自由洞的空队列,开销为O(1)完全可以忽略:
% 生成两个独立的队列,分别存入999和888 empty_queue(Q1), queue_last(Q1, 999, Q1_res), empty_queue(Q2), queue_last(Q2, 888, Q2_res)
方案3:适配为持久化差分队列
如果业务需要保留所有历史版本的队列、支持任意分支修改,只需要在原实现基础上调整参数合一顺序,保证写操作不会修改输入队列的绑定:
empty_queue(queue(0, H, H)). queue_head(queue(s(Count), [Head|Rest]), Tail, Head, queue(Count, Rest, Tail)). queue_last(queue(Count, Head, [Last|NewTail]), Last, queue(s(Count), Head, NewTail)).
调整后所有操作都不会修改输入队列的自由变量,你可以基于任意历史版本的队列创建新的分支队列,不会产生绑定冲突。
内容的提问来源于stack exchange,提问作者but-why
相关产品推荐
相关产品推荐

