为什么Haskell中不允许同时使用所有类型的函数定义？

Question

这可能是一个非常基本的问题,但......

一个被定义为的函数

foo :: a -> Integer

表示从任何类型到整数的函数.如果是这样,那么理论上应该能够为任何类型定义它,就像这样

foo 1 = 10
foo 5.3 = 100
foo (x:xs) = -1
foo  _     = 0

但是Haskell只允许一般的定义,比如foo a = 0.

即使您限制a为某类类型之一,例如Show类型类的实例:

foo :: (Show a) => a -> Integer

你仍然不能做类似的事情

foo "hello" = 10
foo   _     = 0

即使"hello" :: [Char]是一个实例Show

为什么会有这样的限制？

Answer 1

这是一个功能,实际上是非常基础的.它归结为编程语言理论中称为参数化的属性.粗略地说,这意味着评估永远不应该依赖于编译时变量的类型.您无法查看静态不了解其具体类型的值.

为什么那么好？它为程序提供了更强大的不变量.例如,您只从类型中知道a -> a必须是身份函数(或分歧).类似的"自由定理"适用于许多其他多态函数.参数化也是更高级的基于类型的抽象技术的基础.例如,ST s aHaskell中的类型(状态monad)以及相应runST函数的类型依赖于s参数化.这确保了运行函数无法弄乱状态的内部表示.

这对于有效实施也很重要.程序不必在运行时(类型擦除)传递昂贵的类型信息,并且编译器可以为不同类型选择重叠表示.作为后者的示例,0和False以及()和[]在运行时都由0表示.如果允许像你这样的功能,这是不可能的.

Answer 2

Haskell享有一种称为"类型擦除"的实现策略:类型没有计算意义,因此您发出的代码不需要跟踪它们.这对性能来说是一个重要的好处.

您为此性能优势支付的价格是类型没有计算意义:函数不能根据传递的参数类型更改其行为.如果你允许这样的话

f () = "foo"
f [] = "bar"

然后该属性将不是真的:遗嘱的行为f确实取决于其第一个参数的类型.

肯定有语言允许这种事情,特别是在依赖类型的语言中,其中类型通常无法被删除.

Answer 3

对于函数a -> Integer,只允许一种行为 - 返回一个常量整数.为什么？因为你不知道是什么类型a.没有指定约束,它可能绝对是任何东西,并且因为Haskell是静态类型的,所以你需要在编译时解决与类型有关的所有事情.在运行时,类型信息不再存在,因此无法查阅 - 所有使用哪些功能的选择都已经完成.

最接近的Haskell允许这种行为是使用类型类 - 如果你Foo使用一个函数调用一个类型类:

class Foo a where
    foo :: a -> Integer

然后,您可以为不同类型定义它的实例

instance Foo [a] where
    foo [] = 0
    foo (x:xs) = 1 + foo xs

instance Foo Float where
    foo 5.2 = 10
    foo _ = 100

然后,只要你能保证一些参数x是Foo你可以调用foo它.你仍然需要 - 然后你不能写一个函数

bar :: a -> Integer
bar x = 1 + foo x

因为编译器不知道那a是一个实例Foo.你必须告诉它,或者省略类型签名并让它自己解决.

bar :: Foo a => a -> Integer
bar x = 1 + foo x

Haskell只能使用编译器有关某事物类型的信息.这可能听起来有限制,但在实践中,类型类和参数多态性是如此强大,我从不错过动态类型.事实上,我经常发现动态类型很烦人,因为我从来都不确定究竟是什么.

Answer 4

当你描述它时,这种类型a -> Integer并不意味着"从任何类型到函数Integer".当定义或表达式具有类型时a -> Integer,意味着对于任何类型T,都可以将此定义或表达式专门化或实例化为类型的函数T -> Integer.

稍微改变符号,一种思考方式foo :: forall a. a -> Integer是实际上是两个参数的函数:类型a和该类型的值a.或者,就currying而言,foo :: forall a. a -> Integer是一个以类型T作为参数的函数,并T -> Integer为此生成类型的专用函数T.使用identity函数作为示例(生成其参数作为结果的函数),我们可以如下所示:

-- | The polymorphic identity function (not valid Haskell!)
id :: forall a. a -> a
id = \t -> \(x :: t) -> x

将多态作为多态函数的类型参数实现的这种想法来自一个名为System F的数学框架,Haskell实际上将其作为其理论来源之一.然而,Haskell完全隐藏了将类型参数作为参数传递给函数的想法.

Answer 5

这个问题是基于一个错误的前提,Haskell可以做到这一点!(虽然它通常只在非常特殊的情况下使用)

{-# LANGUAGE ScopedTypeVariables, NoMonomorphismRestriction #-}

import Data.Generics

q1 :: Typeable a => a -> Int
q1 = mkQ 0 (\s -> if s == "aString" then 100 else 0)

q2 :: Typeable a => a -> Int
q2 = extQ q1 (\(f :: Float) -> round f)

加载它并试验它:

Prelude Data.Generics> q2 "foo"
0
Prelude Data.Generics> q2 "aString"
100
Prelude Data.Generics> q2 (10.1 :: Float)
10

这不一定与声称类型没有计算意义的答案冲突.这是因为这些示例需要Typeable约束,该约束将类型转换为可在运行时访问的数据值.

大多数所谓的泛型函数(例如SYB)依赖于a Typeable或Data约束.一些软件包引入了自己的替代功能,以实现基本相同的目的.没有这些类的东西,就不可能这样做.