-3 
pp :: [a] -> [a]
pp list = case list of
    [] -> []
    (x: _) -> x : (qq list)


qq :: [a] -> [a]
qq list = case list of
    [] -> []
    (x: xs) -> (pp xs) ++ [x]

函数 pp 是否终止有限列表？如果是这样：如果 pp 是用 n 个元素的列表调用的，那么函数 pp 和 qq 总共调用的频率是多少？如果 pp 对于有限列表没有终止，那么为什么不终止。

我认为函数 pp 将终止，如果使用 n 个元素的列表调用 pp ，则 pp 和 q 将总共调用 2n 。

4

1 回答 1

1

如果输入的大小是（a）有限和（b）递减，则证明递归计算将终止的一种方法。

让我们看看pp

pp :: [a] -> [a]
pp list = case list of
    [] -> []
    (x: _) -> x : (qq list)

最后一行返回x:qq list，但输入是list，因此它qq使用相同长度的列表调用。

让我们看看有什么qq作用：

qq :: [a] -> [a]
qq list = case list of
    [] -> []
    (x: xs) -> (pp xs) ++ [x]

在这里，我们调用pp xs，我们list与模式匹配x:xs。这意味着x是头部（第一个元素）和xs尾部（列表的其余部分），所以xs一个元素比输入短list。

这意味着每次调用时输入的长度都会减少 1 qq，并且不会在调用 时减少pp。因此，您是对的，总共有 2n 次调用，这当然是有限的，因此计算终止。

于 2013-06-11T23:30:22.017 回答