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

Question

给出的是一个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的无类型世界(AKA统一或动态类型),你甚至可以使用

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

(提防一个已知的bug)

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

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

请注意,静态类型检查如何以这种方式转换为动态检查.同样,静态类型错误也会变成运行时错误.