haskell - 如何定义仍具有递归类型的非递归函数的函数类型

Question

Given 是一个 Javascript 函数，例如

const isNull = x => x === null ? [] : [isNull];

这样的函数可能是无意义的，但这不是问题所在。

当我尝试表达类似 Haskell 的类型注释时，我失败了。同样，尝试在 Haskell 中实现类似的函数:

let isZero = \n -> if n == 0 then [] else [isZero] -- doesn't compile

是否有一个术语来描述这种本身不递归但其类型递归的函数？这样的函数只能用动态类型语言来表达吗？

抱歉，如果这是显而易见的 - 我的 Haskell 知识(包括严格的类型系统)相当肤浅。

Answer 1

您需要为此定义一个显式递归类型。

newtype T = T (Int -> [T])

isZero :: T
isZero = T (\n -> if n == 0 then [] else [isZero])

付出的代价是T构造函数的包装/展开，但这是可行的。

如果您想模拟类似 Javascript 的无类型世界(又名统一或动态类型)，您甚至可以使用

data Value
   = VInt Int
   | VList [Value]
   | VFun (Value -> Value)
   ...

(小心 known bug )

原则上，每个Javascript值都可以用上面的巨和类型来表示。例如，应用程序变得像

jsApply (VFun f) v = f v
jsApply _        _ = error "Can not apply a non-function value"

请注意静态类型检查是如何通过这种方式转变为动态检查的。同样，静态类型错误会转化为运行时错误。