如何在F#中为自定义Queue类型实现判断元素存在的contains方法

问题原因 #

你当前的未完成代码只处理了队列内部第一个出队用的正序列表（front）的遍历逻辑，缺少了第二个存储入队元素的反序列表（back）的检查，因此会漏判存放在back列表中的元素。

实现方案 #

方案1：简洁实现（推荐） #

判断元素是否存在不需要触发队列的平衡反转逻辑，直接检查两个内部列表即可，代码更简洁高效：

// Returns true if the queue contains the given element.
let contains elem (QueueList(front, back)) =
    List.contains elem front || List.contains elem back

方案2：递归遍历实现 #

如果需要按照队列弹出顺序遍历做检查，可以补全缺失的分支：

// Returns true if the queue contains the given element.
let rec contains elem = function
    | QueueList([], []) -> false
    | QueueList(hd::tl, rest) -> 
        if hd = elem then true 
        else contains elem (QueueList(tl, rest))
    | QueueList([], rest) -> 
        // 出队列表为空时，反转入队列表作为新的出队列表继续检查
        contains elem (QueueList(List.rev rest, []))

两种实现都满足要求的签名'a -> 'a Queue -> bool when 'a : equality，可直接使用。

内容的提问来源于stack exchange，提问作者Diego