如何确定一个给定类型的代码是否可以编写总计的终止Haskell函数？

Question

给定类型，确定是否可以编写一个终止的Haskell函数。

对于类似的类型Int -> Int，我们知道有限精度整数类型Int至少覆盖了范围，[-2^29, 2^29-1]因此从Int到Int的映射可能有限，因此我们可以编写一个总的终止函数。

例如，给定以下类型：(a -> b) -> (b -> c) -> (a -> c)，我如何确定我们是否可以编写一个总终止函数以将该类型用作函数签名？还是这种类型(a -> c) -> ((a, b) -> c)。

将不胜感激通过这个问题的指导！这是一个作业问题，所以我只在寻求指导。

Answer 1

鉴于：

(a -> b) -> (b -> c) -> (a -> c)

我们知道，Curry-Howard对应关系并不一定是局部的（解释->为逻辑含义，产品类型为AND，总和类型为OR），我们发现它构成了重言式。但是为了找到实现并知道它是总计，我们需要实际找到证明：

   (a ? b) ? (b ? c) ? a ? c
-- ~~~~~~~~~~~~~~~~~~~~~~~~~
-- currying
-- ~~~~~~~~~~~~~~~~~~~~~~~~~
   (a ? b) ? (b ? c) ? a ? c
--           ~~~~~~~~~~~~~~~
-- currying
--           ~~~~~~~~~~~~~~~
   (a ? b) ? (b ? c) ? a ? c
-- ~~~~~~~~~~~~~~~~~
-- commutativity of AND
-- ~~~~~~~~~~~~~~~~~
   (b ? c) ? (a ? b) ? a ? c
--           ~~~~~~~~~~~
-- modus ponens
--           ~
   (b ? c) ? b ? c
-- ~~~~~~~~~~~
-- modus ponens
-- ~
   c ? c
-- ~~~~~
-- reflexivity of implication
-- ~
   1

（这是一个假设的三段论。）

我们可以使用此证明来实现—跳过此处的繁琐步骤，并使用与功能应用程序相对应的模式ponens：

f ab bc a = bc (ab a)

对于(a -> c) -> ((a, b) -> c)解释(a, b)为a ? b（逻辑AND），该参数类似。