2

给定的是一个Javascript函数，如

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

这样的功能可能是无稽之谈，但这不是问题所在。

当我试图表达类似 Haskell 的类型注释时，我失败了。同样尝试在 Haskell 中实现类似的功能：

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

这种函数本身不是递归的，但在它们的类型上是递归的，是否有一个术语？这些函数只能用动态类型语言表达吗？

对不起，如果这很明显 - 我的 Haskell 知识（包括严格的类型系统）相当肤浅。

4

2 回答 2

5

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

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

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

付出的代价是T构造函数的包装/解包，但它是可行的。

如果您想模拟类似 Javascript 的无类型世界（AKA unityped 或动态类型），您甚至可以使用

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

（注意一个已知的错误）

原则上，每一个 Javascript 值都可以用上面的巨额类型来表示。例如，应用程序变成类似

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

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

于 2017-09-04T12:09:17.350 回答
3

Chi 展示了如何实现这种无限类型：您需要一个新类型包装器来“隐藏”无限递归。

一个有趣的替代方法是使用定点公式。回想一下，您可以将递归的东西像您的示例伪定义为

isZero = fix $ \f n -> if n == 0 then [] else [f]

同样，类型实际上可以表示为相关函子的固定点，即和的组合(Int ->)（[]在变压器格式塔中是ListT）：

isZero :: Fix (ListT ((->) Int))
isZero = Fix . ListT $ \n -> if n==0 then [] else [isZero]

另外值得注意的是，您可能并不真正想要ListT那里。MaybeT如果你只有零个或一个元素会更自然。更好的是，您可以使用函子固定点与免费 monad 密切相关的事实，这为您提供了“可能微不足道”的替代情况：

isZero' :: Free ((->) Int) ()
isZero' = wrap $ \n -> if n==0 then Pure () else isZero'

Pure ()只是return ()在 monad 实例中，因此您也可以将if构造替换为标准when：

isZero' = wrap $ \n -> when (n/=0) isZero'
于 2017-09-04T12:40:49.847 回答